The biggest offender is timestamps - compiled binaries, documentation, archives, etc. often contain the time at which the file was built.

Other problems include non-deterministic filesystem order, randomized hash algorithms, and even the fact that Markdown processors mangle email addresses randomly. A highly vexing problem that I'm currently trying to solve is that libxslt implements the XSLT generate-id() function by taking the memory address of the XML node struct, which makes documentation generated with XSLT non-reproducible (memory addresses are non-deterministic because of address space randomization and randomized hash tables).

(I'm the author of strip-nondeterminism, a tool in our custom toolchain that attempts to normalize files after they're built.)

strip-nondeterminism "is a Perl module for stripping bits of non-deterministic information, such as timestamps and file system order, from files such as gzipped files, ZIP archives, and Jar files. It can be used as a post-processing step to make a build reproducible, when the build process itself cannot be made deterministic. It is used as part of the Reproducible Builds project."

Browse source @ https://anonscm.debian.org/cgit/reproducible/strip-nondeterm...

PS. non-deterministic filesystem order .. doesn't this go away if you use tmpfs?

Maybe you could fix the libxslt problem by using a pool allocator for the nodes. The pool would contain only the nodes, and you could use the offset in the pool as their ID, rather than the full virtual address. Just some food for thought.

That's a very interesting idea. It's possible to tell libxml2 to use a custom allocator, but unfortunately it will use that allocator for all objects, not just nodes, and thus would probably be affected by hash table randomization. The architecture dependence is also a problem.

My current solution is a patch that uses a hash table to map the memory address of a node to a counter that increments in a deterministic order. It's a massive hack and I hate it. I'm currently trying to assess what its performance impact is.

The proper solution would be for libxml2 to maintain a counter and assign every node a deterministic ID, but that would require extending the _xmlNode struct, which would break ABI compatibility because the struct is not opaque.

That probably isn't architecture independent.

Thanks for your work!

I've been wondering -- why do compiled binaries actually include timestamps? For human-readable stuff, I sort of understand, but for binaries I don't see we'd want to include timestamps.

I guess it's related to debugging purposes. If you know when a binary was built, you know that a source file X with a changetime later than the build is different to the source file used for building the binary.

For a few examples, see the third paragraph of the article. Things like filesystem ordering, system time, ...

Also, the goal is to make it reproducible across machines, since one of the motivations is to enable everybody to verify that the binary distribution matches the source.

From memory windows binary format supposedly contains a compilation timestamp, but I've never developed for windows. And I know ELF doesn't contain a timestamp.

You can blame the compiler random number seed for much non-determinism. I googled for this and found at good explanation at:

http://blog.mindfab.net/2013/12/on-way-to-deterministic-bina...

The summary is anonymous namespaces actually have a name, that being a big integer, and they're all distinct so each has a different one and gcc just picks a psuedorandom number for each anon namespace. They're anonymous to you, but not to the compiler LOL crazy but true. Some folklore that once every 50 trillion years (maybe less often) linking two compiled files will fail at runtime not compile time because two namespaces randomly were assigned the same number so they "crossed the streams".

Supposedly everyone knows some versions of GCC sometimes pick specific optimizations pseudorandomly. This is one of those "everyone knows and nobody has evidence" things. I'd welcome a link to actual evidence, like to actual code that sometimes compiles differently based on phase of moon or whatever. If I were more bored I'd make a github project specifically to manipulate gcc for fun, sounds amusing.

If you're compiling up static libraries, AR is just a generic, although crude and ancient, file archiver and therefore contains timestamps as explained in the link below. I don't think that's necessary for static library operation its just an artifact of the file format.

http://en.wikipedia.org/wiki/Ar_%28Unix%29

There is also a funny failure mode where two systems with somewhat different libraries (perhaps one upgraded after the other, or a security patch, or got owned), when compiling a statically linked binary with the same code and compiler will obviously have different static linked result. This is of the same class as optimizations getting a little too personal for your specific CPU family such that two generic amd64 intel boxes are not quite so identical as you'd think in both optimizations and runtimes. (oh edited to add what if your virtualization is funky such that GCC didn't think a certain instruction set was present in the virtual image, so bare metal compiles would have different optimizations than images running on the same bare metal, although this is totally theoretical and probably doesn't exist in reality)