rand48 replacement

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

Hello Tomas,

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?

Speed can only be near rand48, see below. Quality (eg no trivial cycles,
does not fail too quickly on statistical tests) and soundness (the point
of generating 52-64 bits of data out of 48 bits, which means that only a
small part of the target space is covered, fails me). Also, I like having
a implementation independent interface (current rand48 tells the name of
the algorithm everywhere and the "uint16[3]" state type is hardcoded in
several places).

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

Basically any PRNG should be slower/comparable than rand48 because it only
does 2 arithmetic ops, you cannot do much less when trying to steer bits.
However because of the 16-bits unpacking/packing on 64 bits architecture
there is some room for additional useful ops, so in the end from the end
user the performance is only about 5% loweR.

State is 16 bytes vs 6 bytes for rand48. This is ok for generating 8 bytes
per round and is still quite small.

I'd expect that it produces better random sequence, considering rand48
is a LCG, which is fairly simple decades old design.

Yep, it does not cycle trivially on low bits compared to an LCG (eg odd ->
even -> odd -> even -> ...), e.g. if you have the bad idea to do "% 2" on
an LCG to extract a bool you just alternate.

To summarize:
- better software engineering
- similar speed (slightly slower)
- better statistical quality
- quite small state
- soundness

--
Fabien.

24 мая 2021 г., в 15:31, Fabien COELHO <coelho@cri.ensmp.fr> написал(а):

- NOT to invent a new design!

Radical version of this argument would be to use de-facto standard and ubiquitous MT19937.
Though, I suspect, it's not optimal solution to the date.

Best regards, Andrey Borodin.

Hi Fabien,

To summarize:
- better software engineering
- similar speed (slightly slower)
- better statistical quality
- quite small state
- soundness

Personally, I think your patch is great. Speaking of the speed I
believe we should consider the performance of the entire DBMS in
typical scenarios, not the performance of the single procedure. I'm
pretty sure in these terms the impact of your patch is neglectable
now, and almost certainly beneficial in the long term because of
better randomness.

While reviewing your patch I noticed that you missed
test_integerset.c. Here is an updated patch.

--
Best regards,
Aleksander Alekseev

Hello Andrey,

- NOT to invent a new design!

Radical version of this argument would be to use de-facto standard and
ubiquitous MT19937.

Indeed, I started considering this one for this reason, obviously.

Though, I suspect, it's not optimal solution to the date.

"not optimal" does not do justice to the issues.

The main one is the huge 2.5 KB state of MT19937 which makes it quite
impractical for plenty of internal and temporary uses. In pgbench there
are many PRNG needed for reproducibility (eg one global, 3 per thread, one
per client) plus a temporary one internal to a function call (permute)
which is expected to be reasonably fast, so should not start by
initializing 2.5 KB of data. In postgres there are 2 permanent ones (sql
random, C double random) plus some in a geqo and in sampling internal
structures.

So standard MT19937 is basically out of the equation. It also happens to
fail some statistical tests and not be very fast. It has a insanely huge
cycle, but pg does not need that, and probably nobody does. The only good
point is that it is a standard, which IMO is not enough to fix the other
issues.

--
Fabien.

Hello Aleksander,

- better software engineering
- similar speed (slightly slower)
- better statistical quality
- quite small state
- soundness

Personally, I think your patch is great.

Thanks for having a look!

Speaking of the speed I believe we should consider the performance of
the entire DBMS in typical scenarios, not the performance of the single
procedure.

Sure. I tested a worst-case pgbench script with only "\set i random(1,
100000000)" on a loop, the slowdown was a few percents (IFAICR < 5%).

I'm pretty sure in these terms the impact of your patch is neglectable
now, and almost certainly beneficial in the long term because of better
randomness.

While reviewing your patch I noticed that you missed test_integerset.c.
Here is an updated patch.

Indeed. Thanks for the catch & the v2 patch!

--
Fabien.

Sorry for a duplicate entry on CF web application

The following review has been posted through the commitfest application:
make installcheck-world: tested, passed
Implements feature: tested, passed
Spec compliant: tested, passed
Documentation: tested, passed

Although the patch looks OK I would like to keep the status "Needs review" for now in case someone would like to join the discussion.

The following review has been posted through the commitfest application:
make installcheck-world: tested, passed
Implements feature: tested, passed
Spec compliant: tested, passed
Documentation: tested, passed

Although the patch looks OK I would like to keep the status "Needs review" for now in case someone would like to join the discussion.

Ok, fine with me.

--
Fabien.

Although this patch is marked RFC, the cfbot shows it doesn't
even compile on Windows. I think you missed updating Mkvcbuild.pm.

regards, tom lane

Although this patch is marked RFC, the cfbot shows it doesn't
even compile on Windows. I think you missed updating Mkvcbuild.pm.

Indeed. Here is a blind attempt at fixing the build, I'll check later to
see whether it works. It would help me if the cfbot results were
integrated into the cf app.

--
Fabien.

Fabien COELHO <coelho@cri.ensmp.fr> writes:

Although this patch is marked RFC, the cfbot shows it doesn't
even compile on Windows. I think you missed updating Mkvcbuild.pm.

Indeed. Here is a blind attempt at fixing the build, I'll check later to
see whether it works. It would help me if the cfbot results were
integrated into the cf app.

Hmm, not there yet per cfbot, not sure why not.

Anyway, after taking a very quick look at the patch itself, I've
got just one main objection: I don't approve of putting this in
port.h or src/port/. erand48.c is there because we envisioned it
originally as an occasionally-used substitute for libc facilities.
But this is most certainly not that, so it belongs in src/common/
instead. I'd also be inclined to invent a new single-purpose .h
file for it.

I see that you probably did that because random.c and srandom.c
depend on it, but I wonder why we don't make an effort to flush
those altogether. It's surely pretty confusing to newbies that
what appears to be a call of the libc primitives is no such thing.

regards, tom lane

On Thu, 1 Jul 2021 at 19:41, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Anyway, after taking a very quick look at the patch itself, I've
got just one main objection: I don't approve of putting this in
port.h or src/port/.

I haven't looked at the patch in detail, but one thing I object to is
the code to choose a random integer in an arbitrary range.

Currently, this is done in pgbench by getrand(), which has its
problems. However, this patch seems to be replacing that with a simple
modulo operation, which is perhaps the worst possible way to do it.
There's plenty of research out there on how to do it better -- see,
for example, [1]https://www.pcg-random.org/posts/bounded-rands.html for a nice summary.

Also, I'd say that functions to choose random integers in an arbitrary
range ought to be part of the common API, as they are in almost every
language's random API.

Regards,
Dean

[1]: https://www.pcg-random.org/posts/bounded-rands.html

Hello Tom,

Indeed. Here is a blind attempt at fixing the build, I'll check later to
see whether it works. It would help me if the cfbot results were
integrated into the cf app.

Hmm, not there yet per cfbot, not sure why not.

I'll investigate.

Anyway, after taking a very quick look at the patch itself, I've
got just one main objection: I don't approve of putting this in
port.h or src/port/. erand48.c is there because we envisioned it
originally as an occasionally-used substitute for libc facilities.
But this is most certainly not that, so it belongs in src/common/
instead.

Ok, this would make sense.

I'd also be inclined to invent a new single-purpose .h
file for it.

Hmmm. Why not.

I see that you probably did that because random.c and srandom.c
depend on it, but I wonder why we don't make an effort to flush
those altogether.

Ok for removing them. They are used in contrib where they can be replaced.
I hope that extensions would not depend on that, though.

It's surely pretty confusing to newbies that what appears to be a call
of the libc primitives is no such thing.

I do not understand your point.

If people believe the current random() implementation to be *the* libc
primitive, then my linux doc says "The random() function uses a nonlinear
additive feedback random number generator employing a default table of
size 31 long integers to return successive pseudo-random numbers in the
range from 0 to RAND_MAX. The period of this random number generator is
very large, approximately 16 * ((2^31) - 1).", which is pretty far from
the rand48 implementation provided in port, so ISTM that the confusion is
already there?

--
Fabien.

Hello Dean,

I haven't looked at the patch in detail, but one thing I object to is
the code to choose a random integer in an arbitrary range.

Thanks for bringing up this interesting question!

Currently, this is done in pgbench by getrand(), which has its
problems.

Yes. That is one of the motivation for providing something hopefully
better.

However, this patch seems to be replacing that with a simple
modulo operation, which is perhaps the worst possible way to do it.

I did it knowing this issue. Here is why:

The modulo operation is biased for large ranges close to the limit, sure.
Also, the bias is somehow of the same magnitude as the FP multiplication
approach used previously, so the "worst" has not changed much, it is
really the same as before.

I thought it is not such an issue because for typical uses we are unlikely
to be in these conditions, so the one-operation no branching approach
seemed like a good precision vs performance compromise: I'd expect the
typical largest ranges to be well below 40 bits (eg a key in a pretty
large table in pgbench), which makes the bias well under 1/2**24 and ISTM
that I can live with that. With the initial 48 bits state, obviously the
situation was not the same.

There's plenty of research out there on how to do it better -- see,
for example, [1] for a nice summary.

Rejection methods include branches, thus may cost significantly more, as
show by the performance figures in blog.

Also, it somehow breaks the sequence determinism when using range, which I
found quite annoying: ISTM desirable that when generating a number the
state advances once, and just once.

Also some methods have higher costs depending on the actual range, eg the
bitmask approach: for range 129 the bitmask is 0xff and you have a nearly
50% probability of iterating once, nearly 25% of iterating twice, and so
on… I like performance to be uniform, not to depend on actual values.

Given these arguments I'd be inclined to keep the bias, but I'm open to
more discussion.

Also, I'd say that functions to choose random integers in an arbitrary
range ought to be part of the common API, as they are in almost every
language's random API.

That is a good point.

--
Fabien.

On Thu, 1 Jul 2021 at 22:18, Fabien COELHO <coelho@cri.ensmp.fr> wrote:

However, this patch seems to be replacing that with a simple
modulo operation, which is perhaps the worst possible way to do it.

The modulo operation is biased for large ranges close to the limit, sure.
Also, the bias is somehow of the same magnitude as the FP multiplication
approach used previously, so the "worst" has not changed much, it is
really the same as before.

It may be true that the bias is of the same magnitude as FP multiply,
but it is not of the same nature. With FP multiply, the
more-likely-to-be-chosen values are more-or-less evenly distributed
across the range, whereas modulo concentrates them all at one end,
making it more likely to bias test results.

It's worth paying attention to how other languages/libraries implement
this, and basically no one chooses the modulo method, which ought to
raise alarm bells. Of the biased methods, it has the worst kind of
bias and the worst performance.

If a biased method is OK, then the biased integer multiply method
seems to be the clear winner. This requires the high part of a
64x64-bit product, which is trivial if 128-bit integers are available,
but would need a little more work otherwise. There's some code in
common/d2s that might be suitable.

Most other implementations tend to use an unbiased method though, and
I think it's worth doing the same. It might be a bit slower, or even
faster depending on implementation and platform, but in the context of
the DB as a whole, I don't think a few extra cycles matters either
way. The method recommended at the very end of that blog seems to be
pretty good all round, but any of the other commonly used unbiased
methods would probably be OK too.

Regards,
Dean

Hello Dean,

It may be true that the bias is of the same magnitude as FP multiply,
but it is not of the same nature. With FP multiply, the
more-likely-to-be-chosen values are more-or-less evenly distributed
across the range, whereas modulo concentrates them all at one end,
making it more likely to bias test results.

Yes, that is true.

It's worth paying attention to how other languages/libraries implement
this, and basically no one chooses the modulo method, which ought to
raise alarm bells. Of the biased methods, it has the worst kind of
bias and the worst performance.

Hmmm. That is not exactly how I interpreted the figures in the blog.

If a biased method is OK, then the biased integer multiply method
seems to be the clear winner. This requires the high part of a
64x64-bit product, which is trivial if 128-bit integers are available,
but would need a little more work otherwise. There's some code in
common/d2s that might be suitable.

And yes, modulo is expensive. If we allow 128 bits integers operations, I
would not choose this RNPG in the first place, I'd take PCG with a 128 bits state.
That does not change the discussion about bias, though.

Most other implementations tend to use an unbiased method though, and I
think it's worth doing the same. It might be a bit slower, or even
faster depending on implementation and platform, but in the context of
the DB as a whole, I don't think a few extra cycles matters either way.

Ok ok ok, I surrender!

The method recommended at the very end of that blog seems to be pretty
good all round, but any of the other commonly used unbiased methods
would probably be OK too.

That does not address my other issues with the proposed methods, in
particular the fact that the generated sequence is less deterministic, but
I think I have a simple way around that. I'm hesitating to skip to the the
bitmask method, and give up performance uniformity. I'll try to come up
with something over the week-end, and also address Tom's comments in
passing.

--
Fabien.

Hello Dean & Tom,

Here is a v4, which:

- moves the stuff to common and fully removes random/srandom (Tom)
- includes a range generation function based on the bitmask method (Dean)
but iterates with splitmix so that the state always advances once (Me)

--
Fabien.

Here is a v4, which:

- moves the stuff to common and fully removes random/srandom (Tom)
- includes a range generation function based on the bitmask method (Dean)
but iterates with splitmix so that the state always advances once (Me)

And a v5 where an unused test file does also compile if we insist.

--
Fabien.