Re: Proposal to introduce a shuffle function to intarray extension

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