Sources of Nondeterminism in Compiled Artifacts and How They Are Removed

Compile the same source twice with the same compiler and compare the outputs byte for byte. The two object files are frequently identical, and just as frequently not. When they differ, the difference is almost never in the machine code: it is in metadata that no one reads during normal operation but that a checksum does. Removing those differences is what reproducible builds means in practice, and the leaks fall into a small number of categories with well-understood mechanisms.

The reason to care is not ideological. A build whose output depends on the clock, on a directory name, or on the iteration order of a hash table cannot be verified by rebuilding it and comparing hashes, which is the cheapest available check that a distributed or cached artifact corresponds to the source that claims to have produced it. Every leak removed widens the set of circumstances under which that check works.

The clock, embedded in three different places

Timestamps enter artifacts through more paths than one might expect.

The first is the archive header. An object archive on Unix systems stores, for each member, a modification time in its header. The archiver writes the member’s file time, which is the time the compiler wrote the object file. Two builds produce archives that differ in those fields even if every member is identical.

The second is the debug information. Debug sections record the compiler’s version and the command line used to produce them, and some also record the working directory and the compilation time. A DW_AT_producer attribute typically contains the compiler name and version string. The debug line program may also embed a directory table whose first entry is the compilation directory, which is an absolute path.

The third is inside the executable format itself. The COFF and PE formats carry a time-date stamp field in the file header, which a linker fills with the time of the link unless it is told to write a fixed value. ELF has no such field, but a linker can still record a build identifier derived from the output, and some toolchains emit a note recording the linker version. None of these need involve the clock, but a build identifier derived from a timestamp does, and so does a version string that includes the date.

The suppression is straightforward in each case, once the leak is identified. For dates, the widely supported convention is an environment variable holding a fixed epoch, which the compiler reads instead of the clock when it expands a date macro and which other tools read instead of the file system’s timestamps. The archiver has a deterministic mode that writes zeroed ownership and timestamps. The linker accepts a build identifier of a chosen form, including one computed from the output rather than from the clock.

# Fix the epoch used for embedded dates, and make archives deterministic
export SOURCE_DATE_EPOCH=1700000000
cc -c -ffile-prefix-map=/build/checkout=/src util.c -o util.o
ar -D -rc libutil.a util.o

Paths that leak the build directory

Absolute paths appear in debug information by design: the debugger must find the source file that produced a line table entry, and the compiler records the path it was given. They also appear in assertion messages, in __FILE__ expansions, and in the strings of a program that reports its own configuration.

The mechanism that removes them is a prefix map, which rewrites a leading path component at the point where the compiler records a path. The mapping is applied to the path as given on the command line and to paths recorded for included files, so a build directory of arbitrary name is recorded as a fixed token. The mapping is a list, applied in order, so nested directories can be mapped separately.

There are two traps. The first is that the mapping applies to the recorded path, not to the file system lookup, so a build that depends on the recorded path matching the actual path, such as a debugger that reads source from the build tree, will need the mapping reversed when debugging. The second is that relative paths and absolute paths are treated differently: a build that invokes the compiler with relative source paths records relative paths, which are stable across directories, while a build that invokes it with absolute paths needs the map. Choosing which form to pass is a decision with consequences beyond the current directory.

Iteration order of hash containers

The subtlest leak is the one that is not visible in any single file. A compiler that walks a hash table to emit symbols, to order sections, or to number anonymous entities will produce different output when the table’s iteration order differs between runs.

The classic case is address-dependent ordering. A hash table keyed on pointers, iterated by bucket, orders entries by the addresses of the objects. If the allocator returns different addresses on two runs, which it can when the environment differs, the emitted order differs, and every downstream offset shifts. Programs that use pointer-keyed sets for interning strings are a common source.

The suppression is either to sort before emitting or to iterate a container with a deterministic order. Sorting is the safer choice because it does not depend on the hash function’s stability across versions, and it is what most compilers that have addressed this have done: collect the set, sort by a stable key, then emit. Where sorting is expensive, an insertion-ordered container gives the same guarantee at the cost of a slightly slower lookup.

This category is the one where “it works on my machine” is not a joke. A build that is deterministic under one allocator, one environment size, and one thread count can differ under another, and the difference is a permutation of otherwise identical content. It is detectable by building the same source with the environment perturbed, which is why reproducibility checks vary the build path and the environment rather than merely repeating the same command. Restricting what the action can observe, so that an accidental dependence on the environment becomes a hard failure instead of a silent difference, is the approach taken in Hermetic Build Actions.

Archive member order and the linker’s input order

An archive stores members in the order they were added. If that order comes from a directory listing, it inherits the file system’s ordering, which differs between file systems and between runs on the same file system when files are created in different orders. A build that adds object files by globbing a directory therefore produces archives whose member order varies.

The archiver’s deterministic mode zeroes the member headers but does not reorder anything: members keep the order in which they were named on the command line. Sorting the file list before the archiver runs is therefore a separate step from the -D flag, and both are needed. The same problem exists one level up: the linker’s output depends on the order of the object files on its command line, because section placement, symbol resolution for weak definitions, and the addresses assigned to functions all follow the input order. A build system that computes its link command from an unordered set produces a different binary when the set’s iteration order changes. Sorting the object list before invoking the linker is the fix, and it is cheap.

There is a related and more annoying case: symbol tables. An object file’s symbol table may be emitted in the order symbols were encountered, which depends on the order of declarations in the source and on the compiler’s internal traversal. Two compilers with identical semantics can produce different symbol table orders and thus different bytes. This affects the object file’s checksum without affecting its meaning, and suppressing it requires sorting the symbol table, which some toolchains do and others do not.

The residual class and the limits of comparison

After the clock, the paths, the iteration order, and the archive metadata are addressed, most builds become byte-identical across runs on the same machine. Across different machines, further differences appear: the compiler binary itself may differ if it was built differently, the C library headers may differ in version, and the CPU’s instruction set extensions may change what the compiler emits when it targets the host. Pinning the toolchain version, the sysroot, and the target flags handles those, which is why reproducible builds are usually described as reproducible given the same inputs rather than reproducible in general.

There is a residual class that cannot be removed by flags because it is a property of the algorithm. A compiler that performs an optimization whose result depends on a work queue processed by multiple threads, without a deterministic merge, produces different but equally valid code. The fix belongs in the compiler’s design: either serialize the phase, or make the merge order deterministic. Both cost performance, and the cost is the reason some compilers expose the choice as an option rather than making it the default.

Finally, byte-identical output is a stronger property than semantic equivalence, and it is the one that matters for verification. A build that is deterministic but wrong is still wrong; a build that is nondeterministic but correct cannot be checked by hashing. Verification therefore needs both: the reproducibility check that the same inputs give the same bytes, and the test suite that the bytes do what they should. The cache key that a build system computes for a compilation is the point where determinism becomes load-bearing, since a key computed over nondeterministic inputs will miss more often than it should and, worse, can collide across genuinely different inputs. Content-Addressed Build Caches works through what such a key has to contain.