undefined | Better HN

0 pointsDylan168072y ago0 comments

No, I'm not saying that.

I'm saying that if you have one PRNG, then you have global state no matter how it's designed. This is true whether you write it so that you get decent statistics, or you write it so you get tons of duplicate values.

And many of the fixes remove global state. Per-thread PRNGs are one option, but so are PRNGs that are used by specific batches of objects.

So, the straightforward broken option has global state, and the non-broken options might or might not have global state.

Which means I have no idea what you're talking about when you use the phrase "need to have global state". What is the PRNG API where that need exists, and what does the version without global state look like?

0 comments

3 comments · 1 top-level

pclmulqdq2y ago· 2 in thread

Every PRNG algorithm has state that is shared among all of its consumers. That is basically true by definition. Put another way, a PRNG is an iterative algorithm that compresses a very long random-looking (the mathematical term is "equidistributed") sequence. That iterative algorithm needs to maintain its position in the sequence, and there's no alternative. There is no algorithm for a PRNG that does not have state that is shared among all of its consumers.

The only way to make a PRNG that does not share state between its consumers is to shard per-consumer. The PRNG in libc doesn't do that, it just uses a lock internal to the PRNG to keep things safe.

You could attempt to make a concurrent PRNG that has atomic-sized state and use CAS loops when generating numbers to keep the consumers in sync, but that's probably worse than using a lock.

Dylan16807OP2y ago

> Every PRNG algorithm has state that is shared among all of its consumers. That is basically true by definition.

Right, but again why did you say it needs to have global state "if you want to get decent statistics"?

What is the alternative to having global state that doesn't have decent statistics?

That "if" is the part I'm confused about.

The part of your comment directly after that sounds like you're describing the situation where clients are data-racing the PRNG and generating repeat numbers and other problems. But that's a problem specifically because of global state being used incorrectly, not something that happens as an alternative to global state.

pclmulqdq2y ago

The alternative is not being random, and "decent statistics" means "being pseudorandom" - the statistics are inseparable from the randomness. You can make a PRNG that has data races, but from a randomness perspective, that is equivalent to just using /dev/null as your random number generator.

1 more reply

j / k navigate · click thread line to collapse