Horton

Re: pgbench - add pseudo-random permutation function

Dean Rasheed <dean.a.rasheed@gmail.com>

View thread
From: Dean Rasheed <dean.a.rasheed@gmail.com>
To: Fabien COELHO <coelho@cri.ensmp.fr>
Cc: Alvaro Herrera <alvherre@2ndquadrant.com>, Thomas Munro <thomas.munro@gmail.com>, David Steele <david@pgmasters.net>, Peter Eisentraut <peter.eisentraut@2ndquadrant.com>, Tomas Vondra <tomas.vondra@2ndquadrant.com>, Hironobu SUZUKI <hironobu@interdb.jp>, PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Date: 2021-03-30T19:31:13Z
Lists: pgsql-hackers

Commits

Same data as JSON: GET /api/v1/messages/:b64id/commits the thread's linked commits as JSON, with link sources. API reference →

  1. pgbench: Function to generate random permutations.

  2. Add basic support for using the POPCNT and SSE4.2s LZCNT opcodes

  3. Further improve code for probing the availability of ARM CRC instructions.

On Tue, 30 Mar 2021 at 19:26, Fabien COELHO <coelho@cri.ensmp.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