Comment by dataflow
2 years ago
Sometimes it's randomized algorithms, sometimes it's performance (e.g. it might be faster not to sort something), sometimes it's time or environment-dependent metadata, sometimes it's thread interleaving, etc.
2 years ago
Sometimes it's randomized algorithms, sometimes it's performance (e.g. it might be faster not to sort something), sometimes it's time or environment-dependent metadata, sometimes it's thread interleaving, etc.
a very common one is pointer values being different from run to run and across different operating systems. Any code that intentionally or accidentally relies on pointer values will be non-deterministic
Would be nice if you could explain how/why this happens, given that normally, pointers aren't persisted.
Languages such as Standard ML and others (Scheme? Lisp? Not sure...) have implementations that can save the current state of the heap into a binary.
This is used in theorem provers, for example, so that you don't have to verify proofs of theorems over and over again (which can be very slow).
Instead, you verify them once, save the state of the heap to disk (as a binary ELF, for instance) and then you can run the binary to continue exactly where you left off (i.e. with all the interesting theorems already in memory, in a proved state).
This is what the HOL4 theorem prover's main `hol` script does, i.e. it runs HOL4 by loading such a memory state from disk, with the core theories and theorems already loaded.
Presumably, to make this reproducible you'd need to make sure that all the memory objects are saved to disk in a deterministic order somehow (e.g. not in memory address order, as it can change from run to run, especially when using multiple threads).
Edit: Presumably you'd also need to make sure that you persist the heap when all threads are idle and in a known state (e.g. with all timers stopped), to avoid random stack states and extraneous temporary allocations from being persisted, which would also affect the resulting binary.
2 replies →
I think they meant if you cast a pointer to an integer, do some math on that and then store that. Then you will a stored result that will likely differ from run to run
3 replies →
That’s runtime behavior