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 Hackers <pgsql-hackers(at)lists(dot)postgresql(dot)org>, Thomas Munro <thomas(dot)munro(at)enterprisedb(dot)com>
Subject: Re: pgbench - add pseudo-random permutation function
Date: 2018-10-15 13:02:52
Message-ID: alpine.DEB.2.21.1810150957290.28507@lancre
Views: Raw Message | Whole Thread | Download mbox | Resend email
Lists: pgsql-hackers

Hello Hironobu-san,

> 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.

You moved the shortcut to the caller. Why not, it removes one modulo
operation and avoids the call altogether.

> (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,

ISTM that we do not need such changes: the code is already portable
because standard C unsigned operations overflow consistently and this is
what it really expected for the linear congruential generator.

If an alternate implementation should be provided, given the heavy cost of
the modular multiplication function, it would be only for those
architectures which fails, detected at configure time. I would not go into
this without an actual failing architecture & C compiler.

Also, the alternate implementation should not change the result, so
something looks amiss in your version. Moreover, I'm unclear how to
implement an overflow multiply with the safe no overflow version.

Here is a v8 which:
- moves the shortcut to the caller
- changes the r formula as you did
- does nothing about Knuth's formula, as nothing should be needed
- fixes tests after Peter's exit status changes


Attachment Content-Type Size
pgbench-prp-func-8.patch text/x-diff 17.9 KB

In response to


Browse pgsql-hackers by date

  From Date Subject
Next Message Fabien COELHO 2018-10-15 13:09:38 Re: [HACKERS] pgbench - allow to store select results into variables
Previous Message Amit Kapila 2018-10-15 12:39:45 Re: Undo logs