rand48 replacement

From: Fabien COELHO <coelho(at)cri(dot)ensmp(dot)fr>
To: PostgreSQL Developers <pgsql-hackers(at)lists(dot)postgresql(dot)org>
Subject: rand48 replacement
Date: 2021-05-24 10:31:29
Message-ID: alpine.DEB.2.22.394.2105241211230.165418@pseudo
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers


Hello pg-devs,

I have given a go at proposing a replacement for rand48.

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.

Thanks for your feedback.

--
Fabien.

Attachment Content-Type Size
prng-1.patch text/x-diff 41.6 KB

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Tomas Vondra 2021-05-24 10:37:18 Re: Performance degradation of REFRESH MATERIALIZED VIEW
Previous Message Magnus Hagander 2021-05-24 09:47:05 Re: Commitfest app vs. pgsql-docs