5 ms·

Are modern compilers truly that deterministic when processing arbitrarily complex code, shoot-yourself-in-the-foot example aside? In the reconfigurable world,

Are modern compilers truly that deterministic when processing arbitrarily complex code, shoot-yourself-in-the-foot example aside? In the reconfigurable world, place and route engines run metaheuristics[1][2] to find good-enough solutions in an intractable search space. I'm imagining if there's a compiler stage which implements even a single optimization heuristic, any prospect of hash-wise reproducibility goes out the window? [1] https://en.wikipedia.org/wiki/Simulated_annealing https://en.wikipedia.org/wiki/Simulated_annealing [2] https://en.wikipedia.org/wiki/Genetic_algorithm https://en.wikipedia.org/wiki/Genetic_algorithm

qwename 10y ago
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 https://github.com/qwename/quirky-protector
- throwaway7767 10y ago
  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.
BuuQu9hu 10y ago
If you call GCC modern, then yes: https://tests.reproducible-builds.org/debian/ https://tests.reproducible-builds.org/debian/
johntb86 10y ago
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.
- metaphor 10y ago
  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/ https://reproducible-builds.org/docs/ [2] http://www.dwheeler.com/trusting-trust/ http://www.dwheeler.com/trusting-trust/ [3] https://www.youtube.com/watch?v=4XpnKHJAok8&feature=youtu.be&t=1664 https://www.youtube.com/watch?v=4XpnKHJAok8&feature=youtu.be...
CJefferson 10y ago
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!
- metaphor 10y ago
  > 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?
  - CJefferson 10y ago
    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
    - metaphor 10y ago
      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/ http://danluu.com/3c-conflict/
krona 10y ago
In theory, no. For practical purposes, mostly yes. See: Buridan's Principle. Also: http://research.microsoft.com/en-us/um/people/lamport/pubs/buridan.pdf http://research.microsoft.com/en-us/um/people/lamport/pubs/b... This was a real issue in hardware design in the 60's.
- metaphor 10y ago
  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_digital_logic:_metastability https://en.wikipedia.org/wiki/Buridan's_ass#Application_to_d...
jameshart 10y ago
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.
- metaphor 10y ago
  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.

qwename 10y ago

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 https://github.com/qwename/quirky-protector

throwaway7767 10y ago
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.

BuuQu9hu 10y ago

If you call GCC modern, then yes: https://tests.reproducible-builds.org/debian/ https://tests.reproducible-builds.org/debian/

johntb86 10y ago

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.

metaphor 10y ago
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/ https://reproducible-builds.org/docs/ [2] http://www.dwheeler.com/trusting-trust/ http://www.dwheeler.com/trusting-trust/ [3] https://www.youtube.com/watch?v=4XpnKHJAok8&feature=youtu.be&t=1664 https://www.youtube.com/watch?v=4XpnKHJAok8&feature=youtu.be...

CJefferson 10y ago

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!

metaphor 10y ago
> 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?
- CJefferson 10y ago
  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
  - metaphor 10y ago
    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/ http://danluu.com/3c-conflict/

krona 10y ago

In theory, no. For practical purposes, mostly yes. See: Buridan's Principle. Also: http://research.microsoft.com/en-us/um/people/lamport/pubs/buridan.pdf http://research.microsoft.com/en-us/um/people/lamport/pubs/b... This was a real issue in hardware design in the 60's.

metaphor 10y ago
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_digital_logic:_metastability https://en.wikipedia.org/wiki/Buridan's_ass#Application_to_d...

jameshart 10y ago

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.

metaphor 10y ago
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.