Re: pgbench - add pseudo-random permutation function

Hi,

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 001_pgbench_with_server.pl
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 
001_pgbench_with_server.pl.



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

Best regards,


On 2018/10/01 12:19, Fabien COELHO wrote:
>>     PostgreSQL Hackers <pgsql-hackers@lists.postgresql.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".
>