5 ms·

On many platforms it's several orders of magnitude slower than a fast, dead simple PRNG with very good distributional properties, like xorshift1024* [1]. [1]:

On many platforms it's several orders of magnitude slower than a fast, dead simple PRNG with very good distributional properties, like xorshift1024* [1]. [1]: http://xorshift.di.unimi.it http://xorshift.di.unimi.it

tedunangst 11y ago
Let's return to the top. How many random bytes do you need per second? Rounded to the nearest billion, of course.
- pcwalton 11y ago
  If your product is in a competitive environment and is being compared against others in benchmarks of random number generation, the answer is "as many as you can possibly generate". This scenario corresponds to JavaScript engines of major Web browsers.
  - tedunangst 11y ago
    In other words, bullshit breeds bullshit.
    - pcwalton 11y ago
      I can't blame V8 engineers for not wanting to regress SunSpider. Sad or not—and, let me tell you, nobody who works on browsers likes this state of affairs when it comes to that benchmark—doing well on the popular benchmarks has to be an engineering goal in the environment browsers find themselves in.
      - mmalone 11y ago
        FWIW xorshift1024* would almost certainly be faster than MWC1616 and it has no systematic failures on BigCrush. The only downside is that it uses more memory, but I think we can afford it. If not xorshift64* is also faster than MWC1616 and miles ahead of it in quality.
- johncolanduoni 11y ago
  For large simulations, this can easily become a bottleneck, which is why those generally use a good non-CS PRNG. In addition, CSPRNGs actually have slightly worse distributional properties than some much faster PRNGs, because the CSPRNG is more focused on being unpredictable. CSPRNGs aren't the end-all be-all of PRNGs, they have their appropriate and inappropriate applications even if we ignore speed.
  - tedunangst 11y ago
    That's not a number. > CSPRNGs actually have slightly worse distributional properties than some much faster PRNGs, because the CSPRNG is more focused on being unpredictable. What does this even mean? Non-uniform distribution for CSRNG is fatal. What is an RNG that has "better" distribution than CSRNG?
    - johncolanduoni 11y ago
      > That's not a number. The actually relevant aspect is what percentage of a simulation's time is spent generating random numbers if it's using a CSPRNG. I have had this become a bottleneck in my work, and it's very rare to use CSPRNGs in scientific simulations for this reason. > What does this even mean? Non-uniform distribution for CSRNG is fatal. What is an RNG that has "better" distribution than CSRNG? There are distributional properties other than uniformity, and depending on how you use these numbers (e.g. Monte Carlo kernel form) these can be far more important than linear uniformity. The author briefly mentioned this in the article ("CSPRNGs emphasize unpredictability over all other measures of quality, some of which might be more important for your use case"). Look into the work of George Marsaglia, he wrote the test suites that generate the quality numbers most engineers use to evaluate both CSPRNG and normal PRNGs.
      - pbsd 11y ago
        I find it disingenuous to see properties such as equidistribution or low discrepancy being described as 'quality' of a generator. Yes, they make certain Monte Carlo algorithms converge quicker. No, they are not closer to a truly random sequence than a CSPRNG is. The goal of a CSPRNG is to be indistinguishable from true randomness, and a predictor is quite obviously a distinguisher. But so is a statistical test, or any 'nice' property that makes some algorithm behave better. By the way, I think I've said this before, but I'll say it again. I really dislike the usage of the term 'CSPRNG' in these discussions. A CSPRNG is typically understood to be /dev/urandom---an algorithm that not only generates a long sequence of numbers, but also harvests entropy and tries to achieve forward and backward security. But it is also sometimes overloaded to mean a stream cipher, which is a conceptually simpler construct, and also able to be much faster. Stream ciphers can definitely compete in performance with things like Xorshift.

tedunangst 11y ago

Let's return to the top. How many random bytes do you need per second? Rounded to the nearest billion, of course.

pcwalton 11y ago
If your product is in a competitive environment and is being compared against others in benchmarks of random number generation, the answer is "as many as you can possibly generate". This scenario corresponds to JavaScript engines of major Web browsers.
- tedunangst 11y ago
  In other words, bullshit breeds bullshit.
  - pcwalton 11y ago
    I can't blame V8 engineers for not wanting to regress SunSpider. Sad or not—and, let me tell you, nobody who works on browsers likes this state of affairs when it comes to that benchmark—doing well on the popular benchmarks has to be an engineering goal in the environment browsers find themselves in.
    - mmalone 11y ago
      FWIW xorshift1024* would almost certainly be faster than MWC1616 and it has no systematic failures on BigCrush. The only downside is that it uses more memory, but I think we can afford it. If not xorshift64* is also faster than MWC1616 and miles ahead of it in quality.
johncolanduoni 11y ago
For large simulations, this can easily become a bottleneck, which is why those generally use a good non-CS PRNG. In addition, CSPRNGs actually have slightly worse distributional properties than some much faster PRNGs, because the CSPRNG is more focused on being unpredictable. CSPRNGs aren't the end-all be-all of PRNGs, they have their appropriate and inappropriate applications even if we ignore speed.
- tedunangst 11y ago
  That's not a number. > CSPRNGs actually have slightly worse distributional properties than some much faster PRNGs, because the CSPRNG is more focused on being unpredictable. What does this even mean? Non-uniform distribution for CSRNG is fatal. What is an RNG that has "better" distribution than CSRNG?
  - johncolanduoni 11y ago
    > That's not a number. The actually relevant aspect is what percentage of a simulation's time is spent generating random numbers if it's using a CSPRNG. I have had this become a bottleneck in my work, and it's very rare to use CSPRNGs in scientific simulations for this reason. > What does this even mean? Non-uniform distribution for CSRNG is fatal. What is an RNG that has "better" distribution than CSRNG? There are distributional properties other than uniformity, and depending on how you use these numbers (e.g. Monte Carlo kernel form) these can be far more important than linear uniformity. The author briefly mentioned this in the article ("CSPRNGs emphasize unpredictability over all other measures of quality, some of which might be more important for your use case"). Look into the work of George Marsaglia, he wrote the test suites that generate the quality numbers most engineers use to evaluate both CSPRNG and normal PRNGs.
    - pbsd 11y ago
      I find it disingenuous to see properties such as equidistribution or low discrepancy being described as 'quality' of a generator. Yes, they make certain Monte Carlo algorithms converge quicker. No, they are not closer to a truly random sequence than a CSPRNG is. The goal of a CSPRNG is to be indistinguishable from true randomness, and a predictor is quite obviously a distinguisher. But so is a statistical test, or any 'nice' property that makes some algorithm behave better. By the way, I think I've said this before, but I'll say it again. I really dislike the usage of the term 'CSPRNG' in these discussions. A CSPRNG is typically understood to be /dev/urandom---an algorithm that not only generates a long sequence of numbers, but also harvests entropy and tries to achieve forward and backward security. But it is also sometimes overloaded to mean a stream cipher, which is a conceptually simpler construct, and also able to be much faster. Stream ciphers can definitely compete in performance with things like Xorshift.