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-31T13:06: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.

Attachments

On Wed, 31 Mar 2021 at 09:02, Fabien COELHO <coelho@cri.ensmp.fr> wrote:
>
> >> First, I have a thing against erand48.
> >
> Also, there is a 64 bits seed provided to the function which instantly
> ignores 16 of them, which looks pretty silly to me.
>

Yeah, that was copied from set_random_seed().

> At least, I suggest that two 48-bits prng could be initialized with parts
> of the seed and used in different places, eg for r & m.
>

That could work. I'd certainly feel better about that than
implementing a whole new PRNG.

> Also, the seed could be used to adjust the rotation, maybe.
>

Perhaps. I'm not sure it's really necessary though.

> >> I'm really at odds with FULL SHIFT 1, because it means that up to 1/256 of
> >> values are kept out of STEERING. [...]
> >
> > 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,
>
> Indeed, it makes sense to me.
>

OK, attached is an update making this change and simplifying the
rotate code, which hopefully just leaves the question of what (if
anything) to do with pg_erand48().

> >> 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.
>
> See pg_popcount64().
>

Actually, I used pg_leftmost_one_pos64() to calculate the mask length,
allowing the mask to be computed from that, so there is no longer a
need for compute_mask(), which seems like a neat little
simplification.

Regards,
Dean