[kbolino]

While a CSPRNG would have solved this problem, it also would've created a new one: much slower chunk loading and random item placement, which would have greatly slowed down the game simulation, and thus tanked framerate and playability. As it turns out, the right solution is to use multiple, isolated non-cryptographic random number generators with distinct state. That way, even though you can guess the state of one of them, it doesn't give you any insight into the others.

[Retr0id]

Modern CSPRNGs can generate numbers at GB/s, I find it hard to believe it would slow the game down in a measurable way.

The "right" solution you describe sounds overcomplicated and error-prone (now you need to think carefully about which domains are separated) compared to just using a CSPRNG.

[kibwen]

> The "right" solution you describe sounds overcomplicated and error-prone

It's not particularly. At program start-up, you seed the original PRNG. Then, you generate N numbers from the original PRNG and use those to seed N other PRNGs, then throw away the original PRNG. You don't need to think carefully about domains, you just create a new PRNG for everything you need a random number for. This makes your game easier to debug in a deterministic way, because now reproducing the behavior of one specific action that involves randomness no longer depends on every other action that involves randomness.

[kbolino]

We may be at the point where CSPRNGs are viable for video game randomness, but that wasn't the case 10+ years ago especially when factoring in compatibility with 20-year-old hardware (high-end PCs from ca 2004 could play Minecraft).

Even so, a non-crypto PRNG can generally compute a new random number in 2-4 ALU ops. With SIMD optimization, that can amortize to under 1 cycle per byte, which means it takes under a nanosecond to generate a new 32-bit number. I'm not sure even the best hardware-accelerated CSPRNG on modern hardware can quite say the same just yet.

[Retr0id]

chacha12, a construction that's been around in one form or another since the '00s, runs at well under 1 cycle per byte on good hardware and still plenty fast on "bad" hardware https://bench.cr.yp.to/results-stream.html (iiuc just using SIMD, no special acceleration)

But it doesn't really matter what things were like when the code was first written, it's about how it could be fixed in the present.

[kbolino]

Video games do not generate large streams of data, they generate individual values on demand. Your link says, to generate 8 bytes, chacha12 on modern hardware needs 24-45 cpb. That's 192-360 cycles to generate enough bits for a pseudorandom double-precision floating-point number. Xoshiro256+ [1], a relatively high-quality generator for this purpose, can do it with 11 single-cycle ALU ops. So unoptimized xoshiro256+ should be 17 times faster than optimized chacha12 on the best hardware. This is a classic latency vs. throughput issue.

Now, maybe you could optimize the use of a CSPRNG here by filling large buffer(s) and sampling values from them. Some warm-up time could go a long way. However, I fear that you would run into one or more of the following problems:

- stop-the-world pause to refill the buffer (e.g. single buffer, no threading)

- synchronization delays from mutex locks (e.g. ring buffer refilled from a background thread)

- high memory usage (e.g. rotating pool of buffers, atomically swapped)

Needless to say, none of these solutions is anywhere near as simple to implement as a non-cryptographic PRNG.

Now let's consider determinism. Video games generally use a lot of differently seeded instances of the same PRNG algorithm to provide random numbers in different parts of the simulation. Since each part may demand random numbers at different rates, it's hard to replace several independent PRNGs with a single PRNG without compromising determinism. In the 4096 bytes necessary to run one instance of chacha12 at its maximum efficiency, you can fit 128 instances of xoshiro256+ or 512 instances of splitmix64 [2].

[1] = https://prng.di.unimi.it/xoshiro256plus.c

[2] = https://github.com/svaarala/duktape/blob/master/misc/splitmi...

[Retr0id]

Generating random numbers into a refillable buffer is the standard for high-performance RNG, whether you're doing CSPRNG or not (it's how V8 uses xorshift, for example). "stop the world" is not a problem when the time to refill the buffer is still measured in nanoseconds.

There's nothing stopping you from having multiple CSPRNG instances, with deterministic seeds, if that's a design requirement.

[kbolino]

I ran a microbenchmark with Go 1.22, which ships with both ChaCha8 (a little faster than ChaCha12) and PCG (a little slower than xoshiro256+). On my M1 Mac, I'm seeing 2.3 ns/uint64 for PCG and 4.5 ns/uint64 for ChaCha8. Assuming 3.2 GHz clock speed, that puts them at about 1 and 2 cpb respectively. With a floating-point conversion in the mix, they ran at 4.0 and 4.5 (!) ns/float64 respectively. That's far better than I would have thought.

So yes, a good, slightly buffered (internal state seems to be 300 bytes) implementation of a (quasi-?)CSPRNG is pretty damn close to a decent quality non-cryptographic PRNG and likely fast enough for most video games on most hardware. Though, very few people write games in Go.

[pclmulqdq]

There are CSPRNG constructions based on AES that would probably be appropriate, but they are still a huge performance hit. PCG, Xorshift, Xoshiro, and the like are all about 50x faster than the fastest CSPRNGs in sustained throughput, and also have smaller state and much less spinup time.

[pclmulqdq]

The problem of dealing with randomness is about figuring out how to use CSPRNGs (and TRNGs) as little as possible, but not too little. CSPRNGs can get to a couple of GB/sec on a core, so they're not all that bad, but non-secure PRNGs are over an order of magnitude faster. I would assume that most of those things (eg chunk generation/loading) don't need secure RNG at all.

Sharding your RNGs by player is also an option for some games, and can be easier.