Lock-free PRNG

With vital assistance from Sebastiano Vigna, of PRNG shootout fame;


I have rewritten the liblfds PRNG code to be lock-free.

The existing code provided two PRNGs – a xorshift1024* (with a spinlock!) to provide high quality seed values for a xorshift32 or xorshift64* (depending on 32/64 bit platform), where the latter ran on single-threaded PRNG states.

What exists now is a single PRNG, with a 32 bit and 64 bit version (the SplitMix PRNG), which is lock-free, and so can be used by any number of threads in parallel, blah, the usual – and, critically, is now in keeping with the rest of the library and can in fact be offered as a lock-free ‘data structure’, along with all the rest.

I can however think of only two reasons for using a lock-free PRNG.

First, convenience. Per-thread state requires, well, per-thread state. A single PRNG state which is thread-safe removes that problem.

Second, is if seed generation is a problem. If there is no source of seed entropy, then one seed must be provided per thread. If the number of threads is variable, then… well, then you need to have two PRNGs, one to generate seeds from a single original seed, and another to run from those seeds – which brings you back to needing a spinlock on the original PRNG.