4 ms·
One neat trick could be to use a linear congruential generator to iterate through the 32-bit integers without repetition, as long as you choose the right parame
by jffry 5y ago
One neat trick could be to use a linear congruential generator to iterate through the 32-bit integers without repetition, as long as you choose the right parameters. Fortunately, these are relatively simple to pick [1] when we're dealing with powers of two.
This would give you fairly easy-to-generate IDs which still have a period of 2^32 but where subsequent allocations have an ID that shares fewer bits on average with its predecessor.
[1] https://en.wikipedia.org/wiki/Linear_congruential_generator#c_%E2%89%A0_0 https://en.wikipedia.org/wiki/Linear_congruential_generator#...
- nlitened 5y agoI think that’s similar to what the article describes.
- jffry 5y agoThe article hadn't specifically discussed rng period but I see the linked code [1] uses an implementation [2] with a period of 2^128-1 [1] https://github.com/openjdk/jdk/blob/4927ee426aedbeea0f4119bac0a342c6d3576762/src/hotspot/share/runtime/synchronizer.cpp#L760-L798 https://github.com/openjdk/jdk/blob/4927ee426aedbeea0f4119ba... [2] https://en.wikipedia.org/wiki/Xorshift https://en.wikipedia.org/wiki/Xorshift