Why is rand() much faster than arc4random()?

Question

I'm writing a game AI which requires fast integer random number generation. This game is for Mac OS, so there are two choices rand() (the plain C) and arc4random() (BSD). I didn't find any comparison in speed for these two functions, so I wrote a small program to test:

long i;

// Record timestamp here.
srand((unsigned int)time(NULL));
for (i = 0; i < 999999999; ++i) {
    rand();
}
// Record timestamp here.
for (i = 0; i < 999999999; ++i) {
    arc4random();
}
// Record timestamp here and print all three.

I tested several times. Results are quite stable: srand() and 999999999 iterations of rand() takes around 6 s, while arc4random() takes much longer (around 30 s).

Is there any reason that arc4random() takes much longer time? Or is there any flaw in my testing. Thank you!

Here is detailed answer on your question [LINK](https://stackoverflow.com/questions/23685920/performance-of-concurrent-code-using-dispatch-group-async-is-much-slower-than-si) — Motorpark Rustavi, May 28 '17 at 19:24
@MotorparkRustavi Oh, thank you! I didn't find the answer if search for why arc4random is slow. So the latency is caused by thread safety, right? — Zhigang An, May 28 '17 at 19:29
That's probably only half of it. Also, `rand` itself is veery simple compared to arc4random — Antti Haapala -- Слава Україні, May 28 '17 at 19:40
In a game, do you really need a "good" random algorithm? My technique, was to use additional data such as the length of time between the player's keyboard/mouse actions, which practically would be impossible to replicate. — Weather Vane, May 28 '17 at 20:11
I seriously doubt that here the culprit is thread safety, given that, at least from what we gather from this question, no threading and contention is involved. It's just that `arc4random()` uses a much more complicated algorithm. If you don't need the "better quality" random numbers it yields you can just use a good old LCG (which is as fast as a PRNGs can get), such as the one from `rand()`. If threading is involved, implement your own LCG and use a separate state for each thread to avoid both contention and race conditions. — Matteo Italia, May 28 '17 at 20:25
@MatteoItalia You are right. I just wrote a thread unsafe version of `arc4random()`, and call it in a similar testing code. Thread unsafe version runs faster (for sure), 15 s on average. But it is still 2.5 times slower than `rand`. Maybe there is still latency introduced by file io. And yes, the game may not need a very sound randomness, so `rand()` should be enough, or using @weather 's method. — Zhigang An, May 28 '17 at 20:33
`rand` and other PRNGs generate a fixed sequence. The user events happen relatively slowly, but if you build their event time into the RNG that will disturb its predictable sequence. — Weather Vane, May 28 '17 at 20:37
ARC4 (or RC4) is a cryptographic algorithm. It trades time for security. If you don't need the security, which you probably don't for a game, then don't use ARC4. — rossum, May 29 '17 at 08:56

plasmacel · Accepted Answer · 2017-05-29T15:34:32.123

Your results are reasonable.

The two functions are designed for different purposes and they are based on completely different class of pseudorandom number generators.

rand() is a pseudorandom number generator (PRNG), generally implemented as a linear congruential generator (LCG), which is reasonably fast but generally it has notoriously bad statistical properties.

arc4random() is a cryptographically secure pseudorandom number generator (CSPRNG), which is generally slower but also suitable for cryptographical use, which implies it has higher statistical quality of randomness than a PRNG. According to the documentations here, here and here:

The function when originally implemented in OpenBSD, used the RC4 cipher to produce the output stream. OpenBSD now uses a ChaCha20 stream cipher.

and

RC4 has been designed by RSA Data Security, Inc. It was posted anonymously to the USENET and was confirmed to be equivalent by several sources who had access to the original cipher. Since RC4 used to be a trade secret, the cipher is now referred to as ARC4.

It is important to understand what is the difference between the two class of pseudorandom number generators.

A PRNG is designed for purposes where all you care about is (ideally) high amount of statistical randomness: fields where you want simulate randomness.

A CSPRNG is designed for purposes where the latter is simply not enough, but high amount of unpredictability (even when the generator algorithm is exactly known) is also required: the field of cryptography.

So you don't need a CSPRNG to generate numbers with high quality of statistical randomness. All you need is a high quality PRNG. rand() is nowhere to that and arc4random() is an overshoot.

See this page for simple, modern, high quality random number generators.

This is a great answer. It turns out even a fixed random sequence is good enough. So absolutely no need for arc4random. — Zhigang An, May 29 '17 at 18:45
I mean the same sequence hard coded in the game is good enough. So it is like using rand without srand. :-) — Zhigang An, May 29 '17 at 19:32
@ZhigangAn If you want you can seed `rand()` with some type of hardware entropy like `std::time()` or `std::clock()`. So the sequence will be different each time you run the program. — plasmacel, May 29 '17 at 19:33

Why is rand() much faster than arc4random()?

1 Answers1