The vast majority of my posts about random number generation have focused on looking at the properties of different generation schemes. But, perhaps surprisingly, the performance of your randomized algorithm may hinge not on the generation scheme you chose, but on other factors. In this post (inspired by and building on an excellent recent paper by Daniel Lemire), we'll explore a common source of overhead in random number generation that frequently outweighs PRNG engine performance.
Imagine this scenario:
For their homework, Huan and Sasha both sit down to implement the same randomized algorithm in C++, running it on the same machine at the university on the same data sets. Their code is almost identical except for random number generation. Huan is eager to get to music practice and so just uses the Mersenne Twister. Sasha, on the other hand, spends several extra hours doing lots of investigation. Sasha benchmarks several fast PRNGs that have been touted lately on social media, and picks the fastest. When Huan and Sasha meet up, Huan can't wait to show off, asking Sasha, “What did you use as your PRNG?”
“Oh, I just used the Mersenne Twister—it's built in and it seemed to work well,” says Huan.
“Ha!” says Sasha. “I used jsf32 . It goes much faster than something old and slow like the Mersenne Twister! My program was done in three minutes fifteen seconds!”.
“Hmm, well, mine got done in under a minute,” says Huan and shrugs. “Anyhow, I'm off to a concert. Want to come?”
“No,” says Sasha. “I, uh, want to take another look at my code….”
This embarrassing fictional scenario is not particularly contrived; it is actually based on real-world results. If your randomized algorithm isn't running as fast as you'd like and the bottleneck seems to be generating random numbers, somewhat counterintuitively the problem might not be with your random number generator!
Background: Random Numbers in Practice
Most modern good-quality random number generators produce machine words filled with random bits, thus typically generating numbers in the range [0..232) or [0..264). But in many use cases users need numbers in a particular range—simple examples such as rolling a die or choosing a random playing card require numbers in small fixed ranges, but many algorithms from shuffling to reservoir sampling to randomized BSTs all need numbers drawn from different ranges.
... continue reading