Re: pgbench - add pseudo-random permutation function

Hi,

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.

> +# PGAC_C_BUILTIN_CLZLL
> +# -------------------------
> +# Check if the C compiler understands __builtin_clzll(),
> +# and define HAVE__BUILTIN_CLZLL if so.
> +# Both GCC & CLANG seem to have one.
> +AC_DEFUN([PGAC_C_BUILTIN_CLZLL],
> +[AC_CACHE_CHECK(for __builtin_clzll, pgac_cv__builtin_clzll,
> +[AC_COMPILE_IFELSE([AC_LANG_SOURCE(
> +[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
> +AC_DEFINE(HAVE__BUILTIN_CLZLL, 1,
> + [Define to 1 if your compiler understands __builtin_clzll.])
> +fi])# PGAC_C_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.

Greetings,

Andres Freund