Re: rand48 replacement - Mailing list pgsql-hackers

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.