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

[Eolien55 <eolien55@disroot.org>]

qwx@sciops.net wrote:
> On Fri Mar 29 09:19:39 +0100 2024, eolien55@disroot.org wrote:
> Here `state' is 64-bit, whereas in your code, it's a ulong,
> ie. 32-bit, which seems to break everything.

I've appeared to make a rookie mistake. It should obviously be
a u64int.

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

Well it is a right rotate instead of a left rotate. I don't believe
it changes anything relevant. Maybe it does, but I'm not sure.
Anyway it should probably indeed be changed to avoid such "puzzled
moments" (code is more often read than written).

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

You are not misreading. The main issues of the current algorithm are
not so much ones of speed (von Neumann's middle square algorithm is
incredibly fast but has extremely poor quality), but ones of state
size and statistical quality. Additive Lagged Fibonacci Generators
(ALFG) such as this one, have bad statistical properties, uncovered by
both mathematical analysis and empirical testing.

The scale is indeed miniscule, and the performance benefit arguably
small, but I do not think that performance alone should decide.

> lrand is used by rand(2) itself and is used throughout the system
> and elsewhere, and who knows what impact changing it might have.

I looked through every usage of lrand-related functions in the codebase,
and it seems that all programs use it simply as "a uniform pseudo-random
number generator", without other expectations on the output (things
that would vary from algorithm to algorithm). However the manpage should
be changed to reflect the algorithm change.

However, through looking at the full source tree, it appears there
are at least 3 lrand duplicates in the source tree, each with its
own algorithm: one for the kernel, in /sys/src/9/port/random.c, which
uses xoroshiro128+, which is quite good; one for normal userspace in
/sys/src/libc/lrand.c, which uses the aforementioned ALFG, which is
quite suboptimal; and one for ape in /sys/src/lib/v/rand.c, which
seemingly points to this[1] article. The algorithm is not in common
use, so maybe it should be changed to one whose properties are
better-known?

Given that kernel's lrand is xoroshiro128+, it would make sense to
either change kernel's lrand to PCG too, or change the proposed
algorithm to xoroshiro128+.

> Applications which need guarantees about distribution or
> performance are not supposed to use rand(2) to begin with.

Well in that case, some code in /sys/src/cmd needs to be changed
to not use rand, like spin and venti.

Cheers,
Elie Le Vaillant

[1] https://dl.acm.org/doi/pdf/10.1145/63039.63042