Re: [9front] [PATCH] libc: replace lrand's algorithm

[qwx@sciops.net]

On Fri Mar 29 09:19:39 +0100 2024, eolien55@disroot.org wrote:

> Hello,
> 
> The current lrand's algorithm is quite suboptimal.
> After benchmarking, we find:
> Current algorithm:
> repeated srand with different values: 820.740000
> repeated lrand: 643.880000
> 
> Proposed algorithm (PCG32-XSH-RR[1]):
> repeated srand with different valudes: 1.920000
> repeated lrand: 600.590000

Hello, 

I'm a bit puzzled by both the results and the implementation.
If I look at the site you point to, the download page [1] has
this snippet:


typedef struct { uint64_t state;  uint64_t inc; } pcg32_random_t;
 
 uint32_t pcg32_random_r(pcg32_random_t* rng)
 {
     uint64_t oldstate = rng->state;
     // Advance internal state
     rng->state = oldstate * 6364136223846793005ULL + (rng->inc|1);
     // Calculate output function (XSH RR), uses old state for max ILP
     uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
     uint32_t rot = oldstate >> 59u;
     return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
 }


Here `state' is 64-bit, whereas in your code, it's a ulong,
ie. 32-bit, which seems to break everything.  Furthermore, your
code seems to have flipped part of the last statement and return
the equivalent of:

	return (xorshifted >> ((-rot) & 31)) | (xorshifted << rot);

Is that intentional?

Moreover, for the benchmark itself, while seeding is significantly
faster, actually calling lrand barely is; the new code is only
1.07x faster than the old.  The scale is also minuscule, around
42 seconds for circa 4.3 billion calls (you're looping on a signed
long from 0 to -1).  Am I misreading?

lrand is used by rand(2) itself and is used throughout the system
and elsewhere, and who knows what impact changing it might have.
Applications which need guarantees about distribution or
performance are not supposed to use rand(2) to begin with.
Therefore, these numbers alone do not justify, in my opinion,
replacing the current implementation.

Cheers,
qwx

[1] https://www.pcg-random.org/download.html