4 ms·
I recently stumbled across some other ways that random number generation can go wrong. Suppose you want reproducible results from a seed, along with parallelis
by skybrian 2y ago
I recently stumbled across some other ways that random number generation can go wrong.
Suppose you want reproducible results from a seed, along with parallelism. Algorithmic random number generators are usually mutable and generate a sequence of results, limiting parallelism. Rather than a sequence, you want something tree-shaped where you can create an independent random stream for each child task. In higher-level API's, a jump or split operator can be useful.
Counter-based random number generators [1] seem pretty useful in that context. An immutable random number generator works like a hash algorithm that maps each input to an output that's difficult to predict. The problem with this is being careful to avoid using the same input twice. You can think of it as allocating random numbers from a very large address space in a reproducible way. How do you partition the address space, predictably, so that every address is used at most once, and nobody runs out?
Giving each child a unique ID and generating a stream from that is one way. If the tree is deeper, you'll want a unique seed for each path.
When a mutable random number generator is copied to a child task (or maybe just to an iterator), the same random numbers might be generated in two places. Avoiding this is the sort of thing that Rust's borrow checker can prevent - borrowing is okay, but you want to prevent multiple concurrent ownership.
[1] https://en.wikipedia.org/wiki/Counter-based_random_number_generator https://en.wikipedia.org/wiki/Counter-based_random_number_ge...
- londons_explore 2y ago> When a mutable random number generator is copied to a child task When you make a child task, the parent adds one to the internal state of the random number generator and advances the random sequence by one. The child adds two to the internal state and advances the random sequence by one. Now you can make any arbitrary tree of tasks, and those tasks each get their own random stream, there is no shared-between-task state or locking needed, and the whole thing is reproducible, even if parent and child tasks are scheduled arbitrarily. fork-ing and use of random numbers can be arbitrarily intermingled.
- skybrian 2y agoMakes sense. Do you have any particular implementations in mind that work this way? I think this depends on the random number generator. For a counter-based RNG, the "internal state" is just a counter, so adding 1 or 2 would result in reusing random numbers in different streams.
- adgjlsfhk1 2y agoJulia's random number generator does this. See https://github.com/JuliaLang/julia/blob/94a0ee8637b66ab67445aecc5895d79c960ab50d/src/task.c#L853 https://github.com/JuliaLang/julia/blob/94a0ee8637b66ab67445...
- skybrian 2y agoThat split function looks a lot more complicated. Thanks for the reference, though! The SplitMix algorithm looks pretty useful. In Java, this is the built-in SplittableRandom class, and there seems to be an npm for it: https://www.npmjs.com/package/splitmix https://www.npmjs.com/package/splitmix
- londons_explore 2y agoThe complexity is because it is not a cryptographic pseudorandom generator. If you have something cryptographic, than any basic operation on the internal state (ie. Increment by one) is enough to totally change the output stream in a way and outsider cannot predict.
- im3w1l 2y agoYou have to think about how your operations interact with other operations you might also do on the random state. Like what if you add one to the state, but someone else subtracts one from the state back to where you started, ooops! Or what if you create a new rng2 by adding one to the state of rng1. Then later you create rng3 by adding one to the state of rng1. Now rng2==rng3. Oops! That's why I like the orignal idea you described of adding 1 and 2 and advancing each rng. This ensures that both streams are irreversibly altered which should make it very hard to accidentally misuse.
- hansvm 2y agoAnother fun one for reproducibility -- rounding. It can happen when compiled for multiple architectures, compiling a second time with different optimizations, .... Things like normal random numbers are generated through _some_ kind of rejection sampling, and crossing that threshold from different rounding behavior will give you a wildly different result. Even if all your application code is tolerant of small perturbations, the result isn't reasonably reproducible. Another way things go wrong with the prng tree idea (assuming the implementation is correct and you actually have independent streams) is race conditions in other parts of your code. E.g., say you have two workers reading a queue and using fancy tree-based randomness. You don't have "race" conditions (data races) in safe Rust without a compiler bug, but the language doesn't define which worker will read which item from the queue. You wind up using a different part of the stream for different inputs.
- skybrian 2y agoWith the counter-based RNG approach, apparently one idea is that you uniquely identify child nodes in your tree somehow. That is, each work unit is a node with a unique ID that's deterministically assigned and has nothing to do with random number generation at all. Then you use that to pick the random stream. An API that uses split or jump seems a little easier to screw up.
- jerry1979 2y agoYou may want to have a look at how they do Extended Keys over in bitcoin: https://learnmeabitcoin.com/technical/keys/hd-wallets/extended-keys/ https://learnmeabitcoin.com/technical/keys/hd-wallets/extend...