Re: pgbench - add pseudo-random permutation function

On Tue, 30 Mar 2021 at 19:26, Fabien COELHO <coelho(at)cri(dot)ensmp(dot)fr> wrote:
>
> First, I have a thing against erand48.

Yeah, that's probably a fair point. However, all the existing pgbench
random functions are using it, so I think it's fair enough for
permute() to do the same (and actually 2^48 is pretty huge). Switching
to a 64-bit PRNG might not be a bad idea, but I think that's something
we'd want to do across the board, and so I think it should be out of
scope for this patch.

> Second, I have a significant reservation about the very structure of the
> transformation in this version:
>
> loop 4 times :
>
> // FIRST HALF STEER
> m/r = pseudo randoms
> if v in first "half"
> v = ((v * m) ^ r) & mask;
> rotate1(v)
>
> // FULL SHIFT 1
> r = pseudo random
> v = (v + r) % size
>
> // SECOND HALF STEER
> m/r = pseudo randoms
> if v in second "half"
> same as previous on second half
>
> // FULL SHIFT 2
> r = pseudo random
> v = (v + r) % size
>
> I'm really at odds with FULL SHIFT 1, because it means that up to 1/256 of
> values are kept out of STEERING. Whole chunks of values could be kept
> unshuffled because they would only have SHIFTS apply to them and each time
> fall in the not steered half. It should be an essential part of the design
> that at least one steer is applied on a value at each round, and if two
> are applied then fine, but certainly not zero. So basically I think that
> the design would be significantly improved by removing "FULL SHIFT 1".

Ah, that's a good point. Something else that also concerned me there
was that it might lead to 2 consecutive full shifts with nothing in
between, which would lead to less uniform randomness (like the
Irwin-Hall distribution).

I just did a quick test without the first full shift, and the results
do appear to be better, so removing that looks like a good idea.

> Third, I think that the rotate code can be simplified, in particular the
> ?: should be avoided because it may induce branches quite damaging to
> processor performance.

Yeah, I wondered about that. Perhaps there's a "trick" that can be
used to simplify it. Pre-computing the number of bits in the mask
would probably help. I'll give it some thought.

Regards,
Dean