Am 17.07.22 um 08:00 schrieb Thomas Munro:
I went to see what Professor Lemire would have to say about all this,
expecting to find a SIMD rabbit hole to fall down for some Sunday
evening reading, but the main thing that jumped out was this article
about the modulo operation required by textbook Fisher-Yates to get a
bounded random number, the random() % n that appears in the patch. He
talks about shuffling twice as fast by using a no-division trick to
get bounded random numbers[1]. I guess you might need to use our
pg_prng_uint32() for that trick because random()'s 0..RAND_MAX might
introduce bias. Anyway, file that under go-faster ideas for later.
[1] https://lemire.me/blog/2016/06/30/fast-random-shuffling/
Hi Thomas,
the small bias of random() % n is not a problem for my use case, but
might be for others. Its easily replaceable with
(int) pg_prng_uint64_range(&pg_global_prng_state, 0, n-1)
Unfortunately it is a bit slower (on my machine), but thats negligible.
Martin
