4 ms·

It's technically correct that a language specification is rarely precise enough to require compiler output to be deterministic. But it's pragmatically true tha

It's technically correct that a language specification is rarely precise enough to require compiler output to be deterministic. But it's pragmatically true that engineers will want to murder you if your compiler is non-deterministic. All sorts of build systems, benchmark harnesses, supply chain validation tools, and other bits of surrounding ecosystem will shit the bed if the compiler doesn't produce bitwise identical output on the same input and compiler flags.

foobazgt 2y ago
Can vouch for this having fixed non-determinism bugs in a compiler. Nobody is happy if your builds aren't reproducible. You'll also suffer crazy performance problems as everything downstream rebuilds randomly and all your build caches randomly miss.
- SushiHippie 2y ago
  NixOS with its nixpkgs [0] and cache [1] would also not work if compilers weren't reproducible. Though they won't use something like PGO or some specific optimization flags as these would very likely lead to unreproducible builds. For example most distros ship a PGO optimized build of Python while nixos does not. [0] https://github.com/nixos/nixpkgs https://github.com/nixos/nixpkgs [1] https://cache.nixos.org/ https://cache.nixos.org/
  - boomanaiden154 2y ago
    PGO can be used in such situations, but the profile needs to be checked in. Same code + same profile -> same binary (assuming the compiler is deterministic, which is tested quite extensively). There are several big projects that use PGO (like Chrome), and you can get a deterministic build at whatever revision using PGO as the profiles are checked in to the repository.
    - vlovich123 2y ago
      It’s called autofdo although I’ve struggled to get it working well in Rust.
      - boomanaiden154 2y ago
        It's not called AutoFDO. AutoFDO refers to a specific sampling-based profile technique out of Google (https://dl.acm.org/doi/abs/10.1145/2854038.2854044 https://dl.acm.org/doi/abs/10.1145/2854038.2854044). Sometimes people will refer to that as PGO though (with PGO and FDO being somewhat synonymous, but PGO seeming to be the preferred term in the open source LLVM world). Chrome specifically uses instrumented PGO which is very much not AutoFDO. PGO works just fine in Rust and has support built into the compiler (https://doc.rust-lang.org/rustc/profile-guided-optimization.html https://doc.rust-lang.org/rustc/profile-guided-optimization....).
        vlovich123 2y ago
        I wasn’t trying to conflate the two. PGO traditionally meant a trace build but as a term it’s pretty generic, at least to me to the general concept of “you have profile information that replaces generically tuned heuristics that the compiler uses). AutoFDO I’d classify as an extension to that concept to a more general PGO technique; kind of ThinLTO vs LTO. Specifically, it generates the “same” information to supplant compiler heuristics, but is more flexible in that the sample can be fed back into “arbitrary” versions of the code using normal sampling techniques instead of an instrumented trace. The reason sampling is better is that it more easily fits into capturing data from production which is much harder to accomplish for the tracing variant (due to perf overheads). Additionally, because it works across versions the amortized compile cost drops from 2x to 1x because you only need to reseed your profile data periodically. I was under the impression they had switched to AutoFDO across the board but maybe that’s just for their cloud stuff and Chrome continues to run a representative workload since that path is more mature. I would guess that if it’s not being used already, they’re exploring how to make Chrome run AutoFDO for the same reason everyone started using ThinLTO - it brought most of the advantages while fixing the disadvantages that hampered adoption. And yes, while PGO is available natively, AutoFDO isn’t quite as smooth.
  - c0balt 2y ago
    Yeah, and nixpkgs also, last time I checked, does patch GCC/ clang to ensure determinism. Many compilers and toolchain by default want to, e.g., embed build information that may leak from the build env in a non-deterministic/ non-reprodicible manner.
- munificent 2y ago
  Yup. Even so much as inserting the build timestamp into the generated executable (which is strangely common) causes havoc with build caching.
Sophira 2y ago
Plus, these models are entirely black boxes. Even given weights, we don't know how to look at them and meaningfully tell what's happening - and not only that, but training these models is likely not cheap at all. Stable output is how we can verify that attacks like the one described in Reflections on Trusting Trust[0] don't happen. [0] https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_ReflectionsonTrustingTrust.pdf https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_Ref...
a_t48 2y ago
NVCC CUDA builds were nondeterministic last time I checked, it made certain things (trying to get very clever with generating patches) difficult. This was also hampered by certain libraries (maybe GTSAM?) wanting to write __DATE__ somewhere in the build output, creating endlessly changing builds.
- deleted 2y ago
  [deleted]
- sigmoid10 2y ago
  In parallel computing you run into nondeterminism pretty quickly anyways - especially with CUDA because of undetermined execution order and floating point accuracy.
  - a_t48 2y ago
    Yes, at runtime. Compiling CUDA doesn’t require a GPU, though, and doesn’t really use “parallel computing”. I think CUDA via clang gets this right and will produce the same build every time - it was purely an NVCC issue.
dheera 2y ago
LLMs can be deterministic if you set the random seed and pin it to a certain version of the weights. My bigger concern would be bugs in the machine code would be very, very difficult to track down.
azinman2 2y ago
Just fix the random seed :)
skybrian 2y ago
I’m amused by the possibility of a compiler having a flag to set a random seed. (with a fixed default, of course). If you hit a compiler bug, you could try a different seed to see what happens. Or how about a code formatter with a random seed? Tool developers could run unit tests with a different seed until they find a bug - or hide the problem by finding a lucky seed for which you have no provable bugs :) Edit: Or how about this: we write a compiler as a nondeterministic algorithm where every output is correct, but they are optimized differently depending on an input vector of choices. Then use machine learning techniques to find the picks that produce the best output.
skissane 2y ago
> But it's pragmatically true that engineers will want to murder you if your compiler is non-deterministic. All sorts of build systems, benchmark harnesses, supply chain validation tools, and other bits of surrounding ecosystem will shit the bed if the compiler doesn't produce bitwise identical output on the same input and compiler flags. I think that’s rather true nowadays, but hasn’t always been thus. Back in the 20th century, non-deterministic compiler output was very common - even if only due to the common practice of embedding the compilation timestamp in the resulting executable - and very few ever cared. Whereas nowadays, there is a much bigger culture of hermetic/reproducible build processes, in which stuff like embedding compilation timestamps in the executable or object files is viewed as an antipattern.

foobazgt 2y ago

Can vouch for this having fixed non-determinism bugs in a compiler. Nobody is happy if your builds aren't reproducible. You'll also suffer crazy performance problems as everything downstream rebuilds randomly and all your build caches randomly miss.

SushiHippie 2y ago
NixOS with its nixpkgs [0] and cache [1] would also not work if compilers weren't reproducible. Though they won't use something like PGO or some specific optimization flags as these would very likely lead to unreproducible builds. For example most distros ship a PGO optimized build of Python while nixos does not. [0] https://github.com/nixos/nixpkgs https://github.com/nixos/nixpkgs [1] https://cache.nixos.org/ https://cache.nixos.org/
- boomanaiden154 2y ago
  PGO can be used in such situations, but the profile needs to be checked in. Same code + same profile -> same binary (assuming the compiler is deterministic, which is tested quite extensively). There are several big projects that use PGO (like Chrome), and you can get a deterministic build at whatever revision using PGO as the profiles are checked in to the repository.
  - vlovich123 2y ago
    It’s called autofdo although I’ve struggled to get it working well in Rust.
    - boomanaiden154 2y ago
      It's not called AutoFDO. AutoFDO refers to a specific sampling-based profile technique out of Google (https://dl.acm.org/doi/abs/10.1145/2854038.2854044 https://dl.acm.org/doi/abs/10.1145/2854038.2854044). Sometimes people will refer to that as PGO though (with PGO and FDO being somewhat synonymous, but PGO seeming to be the preferred term in the open source LLVM world). Chrome specifically uses instrumented PGO which is very much not AutoFDO. PGO works just fine in Rust and has support built into the compiler (https://doc.rust-lang.org/rustc/profile-guided-optimization.html https://doc.rust-lang.org/rustc/profile-guided-optimization....).
      - vlovich123 2y ago
        I wasn’t trying to conflate the two. PGO traditionally meant a trace build but as a term it’s pretty generic, at least to me to the general concept of “you have profile information that replaces generically tuned heuristics that the compiler uses). AutoFDO I’d classify as an extension to that concept to a more general PGO technique; kind of ThinLTO vs LTO. Specifically, it generates the “same” information to supplant compiler heuristics, but is more flexible in that the sample can be fed back into “arbitrary” versions of the code using normal sampling techniques instead of an instrumented trace. The reason sampling is better is that it more easily fits into capturing data from production which is much harder to accomplish for the tracing variant (due to perf overheads). Additionally, because it works across versions the amortized compile cost drops from 2x to 1x because you only need to reseed your profile data periodically. I was under the impression they had switched to AutoFDO across the board but maybe that’s just for their cloud stuff and Chrome continues to run a representative workload since that path is more mature. I would guess that if it’s not being used already, they’re exploring how to make Chrome run AutoFDO for the same reason everyone started using ThinLTO - it brought most of the advantages while fixing the disadvantages that hampered adoption. And yes, while PGO is available natively, AutoFDO isn’t quite as smooth.
- c0balt 2y ago
  Yeah, and nixpkgs also, last time I checked, does patch GCC/ clang to ensure determinism. Many compilers and toolchain by default want to, e.g., embed build information that may leak from the build env in a non-deterministic/ non-reprodicible manner.
munificent 2y ago
Yup. Even so much as inserting the build timestamp into the generated executable (which is strangely common) causes havoc with build caching.

Sophira 2y ago

Plus, these models are entirely black boxes. Even given weights, we don't know how to look at them and meaningfully tell what's happening - and not only that, but training these models is likely not cheap at all. Stable output is how we can verify that attacks like the one described in Reflections on Trusting Trust[0] don't happen. [0] https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_ReflectionsonTrustingTrust.pdf https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_Ref...

a_t48 2y ago

NVCC CUDA builds were nondeterministic last time I checked, it made certain things (trying to get very clever with generating patches) difficult. This was also hampered by certain libraries (maybe GTSAM?) wanting to write __DATE__ somewhere in the build output, creating endlessly changing builds.

deleted 2y ago
[deleted]
sigmoid10 2y ago
In parallel computing you run into nondeterminism pretty quickly anyways - especially with CUDA because of undetermined execution order and floating point accuracy.
- a_t48 2y ago
  Yes, at runtime. Compiling CUDA doesn’t require a GPU, though, and doesn’t really use “parallel computing”. I think CUDA via clang gets this right and will produce the same build every time - it was purely an NVCC issue.

dheera 2y ago

LLMs can be deterministic if you set the random seed and pin it to a certain version of the weights. My bigger concern would be bugs in the machine code would be very, very difficult to track down.

azinman2 2y ago

Just fix the random seed :)

skybrian 2y ago

I’m amused by the possibility of a compiler having a flag to set a random seed. (with a fixed default, of course). If you hit a compiler bug, you could try a different seed to see what happens. Or how about a code formatter with a random seed? Tool developers could run unit tests with a different seed until they find a bug - or hide the problem by finding a lucky seed for which you have no provable bugs :) Edit: Or how about this: we write a compiler as a nondeterministic algorithm where every output is correct, but they are optimized differently depending on an input vector of choices. Then use machine learning techniques to find the picks that produce the best output.

skissane 2y ago

> But it's pragmatically true that engineers will want to murder you if your compiler is non-deterministic. All sorts of build systems, benchmark harnesses, supply chain validation tools, and other bits of surrounding ecosystem will shit the bed if the compiler doesn't produce bitwise identical output on the same input and compiler flags. I think that’s rather true nowadays, but hasn’t always been thus. Back in the 20th century, non-deterministic compiler output was very common - even if only due to the common practice of embedding the compilation timestamp in the resulting executable - and very few ever cared. Whereas nowadays, there is a much bigger culture of hermetic/reproducible build processes, in which stuff like embedding compilation timestamps in the executable or object files is viewed as an antipattern.