Re: pgbench - add pseudo-random permutation function

From: Fabien COELHO <coelho(at)cri(dot)ensmp(dot)fr>
To: Hironobu SUZUKI <hironobu(at)interdb(dot)jp>
Cc: PostgreSQL Developers <pgsql-hackers(at)lists(dot)postgresql(dot)org>
Subject: Re: pgbench - add pseudo-random permutation function
Date: 2018-09-12 09:26:53
Message-ID: alpine.DEB.2.21.1809121104160.13887@lancre
Views: Raw Message | Whole Thread | Download mbox | Resend email
Lists: pgsql-hackers

Hello Hironobu-san,

> However, the implementation of the scatter operation in this patch overflows
> in many cases if the variable:size is 38 bit integer or greater. Because the
> variable:size and the item of the array:primes[] which stores 27-29 bit
> integers are multiplicated. If overflow occurs, the scatter operation does
> not satisfy bijective.

Indeed. Again, thanks for the debug! As you contributed some code, I added
you as a co-author in the CF entry.

Attached a v3, based on your fix, plus some additional changes:
- explicitly declare unsigned variables where appropriate, to avoid casts
- use smaller 24 bits primes instead of 27-29 bits
- add a shortcut for multiplier below 24 bits and y value below 40 bits,
which should avoid the manually implemented multiplication in most
practical cases (tables with over 2^40 rows are pretty rare...).
- change the existing shortcut to look a the number of bits instead of
using 32 limits.
- add a test for minimal code coverage with over 40 bits sizes
- attempt to improve the documentation
- some comments were updates, hopefully for the better

The main idea behind the smaller primes is to avoid the expensive modmul
implementation on most realistic cases.


Attachment Content-Type Size
pgbench-prp-func-3.patch text/x-diff 15.0 KB

In response to


Browse pgsql-hackers by date

  From Date Subject
Next Message Peter Eisentraut 2018-09-12 10:20:06 Re: pg_dump test instability
Previous Message Konstantin Knizhnik 2018-09-12 08:43:09 Re: [HACKERS] Secondary index access optimizations