Re: pgbench - add pseudo-random permutation function

From: Hironobu SUZUKI <hironobu(at)interdb(dot)jp>
To: PostgreSQL Hackers <pgsql-hackers(at)lists(dot)postgresql(dot)org>
Cc: Fabien COELHO <coelho(at)cri(dot)ensmp(dot)fr>, Thomas Munro <thomas(dot)munro(at)enterprisedb(dot)com>
Subject: Re: pgbench - add pseudo-random permutation function
Date: 2018-10-15 02:03:04
Views: Raw Message | Whole Thread | Download mbox | Resend email
Lists: pgsql-hackers


I reviewed pgbench-prp-func-6.patch.

(1) modular_multiply()
In modular_multiply(), the numbers of digits of inputs are checked in
order to determine using the interleaved modular multiplication
algorithm or not. However, the check condition absolutely depends on the
implementation of pseudorandom_perm() even though modular_multiply() is
a general function.

I think it is better that pseudorandom_perm() directly checks the
condition because it can be worked efficiently and modular_multiply()
can be used in general purpose.

(2) pseudorandom_perm() and
Reading the discussion of __builtin_xxx functions, I remembered another
overflow issue.

pseudorandom_perm() uses the Donald Knuth's linear congruential
generator method to obtain pseudo-random numbers. This method, not only
this but also all linear congruential generator methods, always overflows.

If we do not need to guarantee the portability of this code, we do not
care about the result of this method because we just use *pseudo* random
numbers. (In fact, I ignored it before.) However, since we have to
guarantee the portability, we have to calculate it accurately. I
therefore implemented the function dk_lcg() and rewrote pseudorandom_perm().

Just to be sure, I made a python code to check the algorithm of
pseudorandom_perm() and run it.
Fortunately, my python code and pseudorandom_perm() which I rewrote
returned the same answers, so I rewrote the answers in

I attached the new patch `pgbench-prp-func-7.patch`, the python code
``, and the pr_perm check script file

Best regards,

On 2018/10/01 12:19, Fabien COELHO wrote:
>>     PostgreSQL Hackers <pgsql-hackers(at)lists(dot)postgresql(dot)org>
>> Subject: Re: pgbench - add pseudo-random permutation function
>> On Wed, Sep 26, 2018 at 01:20:49PM +0200, Fabien COELHO wrote:
>>> So, am I right to deducing that you are satisfied with the current
>>> status of
>>> the patch, with the nbits implementation either based on popcount
>>> (v4) or
>>> clz (v5) compiler intrinsics? I think that the clz option is better.
>> Fabien, please note that v5 does not apply,
> Indeed, tests interact with 92a0342 committed on Thursday.
> Here is a rebase of the latest version based on CLZ. According to basic
> test I made, the underlying hardware instruction seems to be more often
> available.
>> so I moved this patch to next CF, waiting on author.
> I'm going to change its state to "Needs review".

Attachment Content-Type Size
pr_perm_check.sql text/plain 346 bytes text/x-python-script 1.6 KB
pgbench-prp-func-7.patch text/plain 17.6 KB

In response to


Browse pgsql-hackers by date

  From Date Subject
Next Message Tom Lane 2018-10-15 03:25:09 Re: "SELECT ... FROM DUAL" is not quite as silly as it appears
Previous Message Andrew Dunstan 2018-10-15 01:11:42 Re: pgsql: Add TAP tests for pg_verify_checksums