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@alvh.no-ip.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