Re:PCG, A Family of Better Random Number Generators
by pbsd on Wednesday July 15, 2015 @06:52AM
(#9890648)
> The drawback however, is that these implementation only get that fast because ChaCha is embarrassingly parallel.
That is my point exactly. Why would you design, in this day and age, a generator that doesn't vectorize well? It will not take full advantage of the CPU. Even with parallel streams, large integer multiplication and variable-length rotation are SIMD-killers. Regarding the 1.5KB of data, I suspect you can get away with less than that if you specialize to this application, but note that this is still around half the state size of mt19937.
The drawback however, is that these implementation only get that fast because ChaCha is embarrassingly parallel. The fastest implementations can be computing 16-24 blocks in parallel efficiently with AVX2. That's 1.5kB of random data generated at once. And it's only this fast in a closed loop, where all code and memory is hot.
For the above reasons and simplicity I've chosen to not do a parallel SIMD implementation in my gist.
But I agree that 'fairly slow' is not really fair to say, at least not in combination with 'Good' statistical quality (rather than Excellent, because the author found faults in ChaCha2). ChaCha8 is blazing fast, and so far no cryptographer has been able to do a successful attack against it. However, before, ChaCha was mentioned as being 'slow', and I attempted to fix that by emailing the author with my implementation.
-
Interestingly, I was (sadly I never got to finish it before the http://competitions.cr.yp.to/caesar.html deadline) working on an AEAD design similar to ChaCha, that was doing 1.5 cpb authenticated encryption on AVX2: http://www.liacs.nl/~opeters/orlein.pdf. SIMD plus embarrassingly parallel ciphers is a strong combination.
-
Thanks for the warning about the alignment. Because I tacked on the SIMD implementation later, I forgot to add the alignment requirement, I did that now.