If your random numbers are generated with a fixed seed and the algorithm runs for a deterministic number of steps (e.g. not using a wall-clock timeout) then the output should be deterministic.

One potential for nondeterminism is if the compiler or linker is multithreaded, and multiple threads could update a shared data structure in no fixed order.

OP actually pointed to an interesting reference[1] which briefly touches on the impact of pseudo-random number generation, amongst other things.

Diving a little bit deeper down the same rabbit hole, David A. Wheeler[2] (as he emphatically insists on being cited) also made note of threads with non-deterministic scheduling. Lots of notes on hardware-centric implications as well.

Definitely turns my perspective around on what it means to trust software. I suppose the effort is a proper graduation from masturbating[3] to safe sex, so to speak.

[1] https://reproducible-builds.org/docs/

[2] http://www.dwheeler.com/trusting-trust/

[3] https://www.youtube.com/watch?v=4XpnKHJAok8&feature=youtu.be...

If you call GCC modern, then yes:

https://tests.reproducible-builds.org/debian/

In theory, no. For practical purposes, mostly yes.

See: Buridan's Principle. Also: http://research.microsoft.com/en-us/um/people/lamport/pubs/b...

This was a real issue in hardware design in the 60's.

Thanks for the paper link...I feel like I've encountered it before somewhere, maybe here or back in uni as an undergrad. Wiki[1] noted its relation to metastability in digital architectures. That's a phenomena I'm very much familiar with.

[1] https://en.wikipedia.org/wiki/Buridan's_ass#Application_to_d...

As long as the heuristic is run the same way, you will get the same output.

Most compilers aim for reproducibility (except for things like timestamps) anyway, as your customers would rightly complain if compiling their programming produced different speed executables each time, and debugging compiler problems would become even harder!

> Most compilers aim for reproducibility...

I suppose that's what I was seeking to gain clarity on.

The remark on execution speed is a bit confusing though, considering most software applications do not operate in a strict cycle-accurate, real-time environment, which is further exacerbated by the caching schemes of modern processors.

From your perspective, given the same repeatable test input, what threshold qualifies an executable's speed as being different?

It's common for small changes in code, or even the alignment of code (moving it all up/down memory) to have surprising results in the performance of the resulting code, due to things like page alignment.

Here is a random example (you can find lots of others):

    http://stackoverflow.com/questions/17896714/why-would-introducing-useless-mov-instructions-speed-up-a-tight-loop-in-x86-64-a

Hmmm...perhaps a rephrasing of the question given this particular example.

Which would you consider to be the surprising part: ~0.75% average execution speed slowdown, or on the order of tens of milliseconds slowdown?

W.r.t. page alignment, thought you may find this to be an interesting counter example[1].

[1] http://danluu.com/3c-conflict/

Last year I reversed engineered a (36KiB) Windows PE binary[1] to obtain C++ source code that compiled to almost the exact same bytes. What stumped me was an undocumented section that contained metadata, which I gave up on figuring out.

Assuming you compile with the same options and in the same environment, the machine instructions should be the same.

EDIT: The compiler in question though is whatever Visual Basic 6.0 uses, so I wouldn't call it modern today.

[1] https://github.com/qwename/quirky-protector

One of the longstanding issues the Tor project had with their reproducible builds was that the windows builds, built with Visual Studio, would always have a small piece of data in the same place that differed for each build. It took months to figure it out, but it turned out to be a bug in the MS compiler where they were including some uninitialized memory from the compiler into the resulting binary. IIRC it was fixed after being reported to Microsoft.

Could be the same or similar issue you are facing, given the age of the compiler.

I don't have a reference to link to though, Roger Dingledine told me this in person at a conference when discussing issues related to reproducible builds. But there should be an issue in the tor bug tracker.

The fact that best practices when building an application don't suggest running the build multiple times, benchmarking the results and choosing the fastest, suggest that compilers are generally assumed to be deterministic.

Best practices are not universal.

The build-benchmark-repeat process is effectively what place and route metaheuristics in the FPGA world automatically do.

I'm imagining not all compilers are created equally, so I threw all handwaving general assumptions on determinism out the window.