Hi,
On 5/24/21 12:31 PM, Fabien COELHO wrote:
Hello pg-devs,
I have given a go at proposing a replacement for rand48.
So what is the motivation for replacing rand48? Speed, quality of
produced random numbers, features rand48 can't provide, or what?
POSIX 1988 (?) rand48 is a LCG PRNG designed to generate 32 bits
integers or floats based on a 48 bits state on 16 or 32 bits
architectures. LCG cycles on the low bits, which can be quite annoying.
Given that we run on 64 bits architectures and that we need to generate
64 bits ints or doubles, IMHO it makes very little sense to stick to that.
We should (probably) want:
- one reasonable default PRNG for all pg internal uses.
- NOT to invent a new design!
- something fast, close to rand48 (which basically does 2 arithmetic
ops, so it is hard to compete)
no need for something cryptographic though, which would imply slow
- to produce 64 bits integers & doubles with a 52 bits mantissa,
so state size > 64 bits.
- a small state though, because we might generate quite a few of them
for different purposes so state size <= 256 or even <= 128 bits
- the state to be aligned to whatever => 128 bits
- 64 bits operations for efficiency on modern architectures,
but not 128 bits operations.
- not to depend on special hardware for speed (eg MMX/SSE/AES).
- not something with obvious known and relevant defects.
- not something with "rights" attached.
These constraints reduce drastically the available options from
https://en.wikipedia.org/wiki/List_of_random_number_generators
The attached patch removes "rand48" and adds a "pg_prng" implementation
based on xoroshiro128ss, and replaces it everywhere. In pgbench, the non
portable double-relying code is replaced by hopefully portable ints. The
interface makes it easy to replace the underlying PRNG if something else
is desired.
xoroshiro seems reasonable. How does it compare to rand48? Does it need
much less/more state, is it faster/slower, etc.? I'd expect that it
produces better random sequence, considering rand48 is a LCG, which is
fairly simple decades old design.
regards
--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
