Re: pgbench - add pseudo-random permutation function

From: Andres Freund <andres(at)anarazel(dot)de>
To: Hironobu SUZUKI <hironobu(at)interdb(dot)jp>
Cc: PostgreSQL Hackers <pgsql-hackers(at)lists(dot)postgresql(dot)org>, Fabien COELHO <coelho(at)cri(dot)ensmp(dot)fr>, Alvaro Herrera <alvherre(at)2ndquadrant(dot)com>
Subject: Re: pgbench - add pseudo-random permutation function
Date: 2019-02-14 17:59:58
Views: Raw Message | Whole Thread | Download mbox
Lists: pgsql-hackers


On 2019-02-10 17:46:15 +0000, Hironobu SUZUKI wrote:
> I updated the patch. And also I added some explanations and simple examples
> in the modular_multiply function.

It'd be good to update the commitfest entry to say 'needs review' the
next time.

> +# -------------------------
> +# Check if the C compiler understands __builtin_clzll(),
> +# and define HAVE__BUILTIN_CLZLL if so.
> +# Both GCC & CLANG seem to have one.
> +[AC_CACHE_CHECK(for __builtin_clzll, pgac_cv__builtin_clzll,
> +[static unsigned long int x = __builtin_clzll(0xaabbccddeeff0011);]
> +)],
> +[pgac_cv__builtin_clzll=yes],
> +[pgac_cv__builtin_clzll=no])])
> +if test x"$pgac_cv__builtin_clzll" = xyes ; then
> + [Define to 1 if your compiler understands __builtin_clzll.])

I think this has been partially superceded by

commit 711bab1e4d19b5c9967328315a542d93386b1ac5
Author: Alvaro Herrera <alvherre(at)alvh(dot)no-ip(dot)org>
Date: 2019-02-13 16:10:06 -0300

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

could you make sur eit's integrated appropriately?

> <para>
> + Function <literal>pr_perm</literal> implements a pseudo-random permutation.
> + It allows to mix the output of non uniform random functions so that
> + values drawn more often are not trivially correlated.
> + It permutes integers in [0, size) using a seed by applying rounds of
> + simple invertible functions, similarly to an encryption function,
> + although beware that it is not at all cryptographically secure.
> + Compared to <literal>hash</literal> functions discussed above, the function
> + ensures that a perfect permutation is applied: there are no collisions
> + nor holes in the output values.
> + Values outside the interval are interpreted modulo the size.
> + The function errors if size is not positive.
> + If no seed is provided, <literal>:default_seed</literal> is used.
> + For a given size and seed, the function is fully deterministic: if two
> + permutations on the same size must not be correlated, use distinct seeds
> + as outlined in the previous example about hash functions.
> + </para>

This doesn't really explain why we want this in pgbench.


Andres Freund

In response to


Browse pgsql-hackers by date

  From Date Subject
Next Message Andres Freund 2019-02-14 18:07:58 Re: libpq host/hostaddr/conninfo inconsistencies
Previous Message Andrew Dunstan 2019-02-14 17:42:51 Re: Ryu floating point output patch