Horton

Re: pgbench - add pseudo-random permutation function

David Bowen <dmb0317@gmail.com>

View thread
From: David Bowen <dmb0317@gmail.com>
To: Dean Rasheed <dean.a.rasheed@gmail.com>
Cc: Bruce Momjian <bruce@momjian.us>, Fabien COELHO <coelho@cri.ensmp.fr>, Alvaro Herrera <alvherre@2ndquadrant.com>, David Steele <david@pgmasters.net>, Peter Eisentraut <peter.eisentraut@2ndquadrant.com>, Tomas Vondra <tomas.vondra@2ndquadrant.com>, Thomas Munro <thomas.munro@gmail.com>, Hironobu SUZUKI <hironobu@interdb.jp>, PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Date: 2021-03-11T19:06:06Z
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.

The algorithm for generating a random permutation with a uniform
distribution across all permutations is easy:
for (i=0; i<n; i++) {
   swap a[n-i] with a[rand(n-i+1)]
}

where 0 <= rand(x) < x and a[i] is initially i (see Knuth, Section 3.4.2
Algorithm P)

David Bowen

On Thu, Mar 11, 2021 at 9:32 AM Dean Rasheed <dean.a.rasheed@gmail.com>
wrote:

> On Thu, 11 Mar 2021 at 00:58, Bruce Momjian <bruce@momjian.us> wrote:
> >
> > Maybe Dean Rasheed can help because of his math background --- CC'ing
> him.
> >
>
> Reading the thread I can see how such a function might be useful to
> scatter non-uniformly random values.
>
> The implementation looks plausible too, though it adds quite a large
> amount of new code. The main thing that concerns me is justifying the
> code. With this kind of thing, it's all too easy to overlook corner
> cases and end up with trivial sequences in certain special cases. I'd
> feel better about that if we were implementing a standard algorithm
> with known pedigree.
>
> Thinking about the use case for this, it seems that it's basically
> designed to turn a set of non-uniform random numbers (produced by
> random_exponential() et al.) into another set of non-uniform random
> numbers, where the non-uniformity is scattered so that the more/less
> common values aren't all clumped together.
>
> I'm wondering if that's something that can't be done more simply by
> passing the non-uniform random numbers through the uniform random
> number generator to scatter them uniformly across some range -- e.g.,
> given an integer n, return the n'th value from the sequence produced
> by random(), starting from some initial seed -- i.e., implement
> nth_random(lb, ub, seed, n). That would actually be pretty
> straightforward to implement using O(log(n)) time to execute (see the
> attached python example), though it wouldn't generate a permutation,
> so it'd need a bit of thought to see if it met the requirements.
>
> Regards,
> Dean
>