[Cryptography] An interesting little pseudorandom number generator

[John-Mark Gurney]

Ray Dillinger wrote this message on Sun, Aug 01, 2021 at 00:49 +0000:
> > While I'm no fan of creeping it to the absolute minimum, 2 kB of state
> > for an rng might be a bit excessive.
> 
> If I recall correctly, 4kB is one cache line on modern hardware; if it
> fits in cache at all, then making it smaller can't make it faster.  That
> said, it could go down to 1kB with int32s, or even to 1/2kB with int16s.

It depends upon what cache you're talking about.  L1 cache lines are
often 64 bytes, and it's been shown that even the first 8 bytes of
an L1 cache line is accessed more quickly than the remaining bytes...
Here's a reference to the issue:
https://bugzilla.mozilla.org/show_bug.cgi?id=868948#c4

I can't find a link to the presentation mentioned in the comment
though...

And a number of years ago, I ran the sample code (don't remember where
it is now), and proved it on the machine(s?) I had at the time that
the results were correct.

So, even at a minimum, the table needs to be striped across L1 cache
lines, and the either masked or combined, such that each table access
always accesses every cache line that the table spans...

-- 
  John-Mark Gurney				Voice: +1 415 225 5579

     "All that I will do, has been done, All that I have, has not."