Horton

Re: pgbench - add pseudo-random permutation function

Alvaro Herrera <alvherre@2ndquadrant.com>

View thread
From: Alvaro Herrera <alvherre@2ndquadrant.com>
To: Fabien COELHO <coelho@cri.ensmp.fr>
Cc: 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-14T14:54:46Z
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 2021-Mar-14, Fabien COELHO wrote:

> +	/*-----
> +	 * Apply 4 rounds of bijective transformations using key updated
> +	 * at each stage:
> +	 *
> +	 * (1) whiten: partial xors on overlapping power-of-2 subsets
> +	 *     for instance with v in 0 .. 14 (i.e. with size == 15):
> +	 *     if v is in 0 .. 7 do v = (v ^ k) % 8
> +	 *     if v is in 7 .. 14 do v = 14 - ((14-v) ^ k) % 8
> +	 *     note that because of the overlap (here 7), v may be changed twice.
> +	 *     this transformation if bijective because the condition to apply it
> +	 *     is still true after applying it, and xor itself is bijective on a
> +	 *     power-of-2 size.
> +	 *
> +	 * (2) scatter: linear modulo
> +	 *     v = (v * p + k) % size
> +	 *     this transformation is bijective is p & size are prime, which is
> +	 *     ensured in the code by the while loop which discards primes when
> +	 *     size is a multiple of it.
> +	 *
> +	 */

My main question on this now is, do you have a scholar reference for
this algorithm?

-- 
Álvaro Herrera       Valdivia, Chile
"Someone said that it is at least an order of magnitude more work to do
production software than a prototype. I think he is wrong by at least
an order of magnitude."                              (Brian Kernighan)