Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

PCG, A Family of Better Random Number Generators

pcg-random.org

Post reply on HN
Print view View original

31–40 of 57 posts

Re: PCG, A Family of Better Random Number Generators

#31

Post by pbsd »

nightcracker wrote: post #12
daurnimator wrote: post #10

Earlier quoted context omitted.

How does it compare to the libsodium implementation: https://github.com/jedisct1/libsodium/blob/master/src/libsod... Btw, libsodium prefers salsa20 instead of chacha20, I don't know why; but I trust they made a good decision.

It's essentially the same, except for the API. However, you linked to the reference implementation. My implementation also contains a SIMD implementation, if your CPU supports it. I assume that libsodium has a similar implementation in its codebase somewhere too. My SIMD implementation can be made to run a bit faster, but this would mean computing more blocks in parallel, and thus increase the state size of the RNG e…

'A bit faster' is an understatement. On the benchmarking machine used by the PCG author, you would get a ~2.5x speedup over that implementation, which would put Chacha20 roughly at (amortized) 5 cycles per 32-bit word. If you go Chacha8, which is still cryptographically secure, that becomes 2-3 amortized cycles per word. The flagship PCG generator from the paper, 'PCG XSL RR RR 128', runs at 1.81 nanoseconds per word on the same machine. This converts to ~6 cycles per word. So I am not inclined to believe the claim, right on the frontpage, that Chacha20 is 'fairly slow' .

Unless you're hurting for space---and in a Haswell machine you probably aren't---the case for using a cryptographic generator everywhere is strong. If you're hurting for space, or are on a less desktop-oriented architecture, you probably are not going to like 64-bit integer multiplications and variable rotation counts either.

By the way, you're using the aligned _mm_load_si128 and _mm_store_si128 intrinsics to load and store the block: https://gist.github.com/orlp/32f5d1b631ab092608b1#file-chach.... But there's no guarantee that block is aligned to 16 bytes, so that code may crash in some compiler/platform combination.

Re: PCG, A Family of Better Random Number Generators

#32

Post by danieltillett »

LoSboccacc wrote: post #30
danieltillett wrote: post #21

Wow talk about a coincidence - I just implemented this algorithm today as the RNG for some bootstrapped statistic code. One thing I can say is it very fast, but the code for seeding is not great on any platform without /dev/random.

I implemented the mersenne twister to generate 2d planets in a galaxy of a game I am working on a while ago.. I didn't know about this pcg and it's an interesting read! I had been limited in selection on the random number generator reproducibility (so that each planet is only stored as the seed for the generator) I'll have a try later on, it'd be interesting how a sampling of planets turn out from both rngs, if they…

Give it a try - I just used the minimum C code function and implemented my own seeding function.

Re: PCG, A Family of Better Random Number Generators

#33

Post by jacobolus »

ufo wrote: post #5

There is a seminar about PCG from its author available on youtube. https://www.youtube.com/watch?v=45Oet5qjlms Its a bit long but I highly recommend it. I learned a lot about RNGs from it.

Great talk! The video is also linked from the site, under 'Video' in the banner: http://www.pcg-random.org/posts/stanford-colloquium-talk.htm...

For those who didn’t bother poking around and are interested in random number generation and C++, the blog also great: http://www.pcg-random.org/blog/

Re: PCG, A Family of Better Random Number Generators

#35

Post by nightcracker »

netheril96 wrote: post #20
nightcracker wrote: post #9

Earlier quoted context omitted.

I wrote a standalone C++11 (compatible with the standard RNG library) implementation of ChaCha (with the number of rounds as a parameter), available here: https://gist.github.com/orlp/32f5d1b631ab092608b1 This is also the implementation used for the benchmark at the pcg-random.org homepage.

What is the stream parameter in the constructor `explicit ChaCha(uint64_t seedval, uint64_t stream = 0);`?

It allows you to make multiple parallel streams of random data with the same seed.

If you prefer, you can see the seed + stream as a combined 128 bit seed.

Re: PCG, A Family of Better Random Number Generators

#37

Post by nightcracker »

pbsd wrote: post #31
nightcracker wrote: post #12

Earlier quoted context omitted.

It's essentially the same, except for the API. However, you linked to the reference implementation. My implementation also contains a SIMD implementation, if your CPU supports it. I assume that libsodium has a similar implementation in its codebase somewhere too. My SIMD implementation can be made to run a bit faster, but this would mean computing more blocks in parallel, and thus increase the state size of the RNG e…

'A bit faster' is an understatement. On the benchmarking machine used by the PCG author, you would get a ~2.5x speedup over that implementation, which would put Chacha20 roughly at (amortized) 5 cycles per 32-bit word. If you go Chacha8, which is still cryptographically secure, that becomes 2-3 amortized cycles per word. The flagship PCG generator from the paper, 'PCG XSL RR RR 128', runs at 1.81 nanoseconds per word…

The fastest ChaCha20 implementation available (from http://bench.cr.yp.to/results-stream.html) on a modern Intel processor is 1.2 cycles / byte (cpb) for ChaCha20 and 0.6 cpb for ChaCha8. ChaCha is very fast.

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.

Re: PCG, A Family of Better Random Number Generators

#38

Post by pbsd »

nightcracker wrote: post #37
pbsd wrote: post #31

Earlier quoted context omitted.

'A bit faster' is an understatement. On the benchmarking machine used by the PCG author, you would get a ~2.5x speedup over that implementation, which would put Chacha20 roughly at (amortized) 5 cycles per 32-bit word. If you go Chacha8, which is still cryptographically secure, that becomes 2-3 amortized cycles per word. The flagship PCG generator from the paper, 'PCG XSL RR RR 128', runs at 1.81 nanoseconds per word…

The fastest ChaCha20 implementation available (from http://bench.cr.yp.to/results-stream.html ) on a modern Intel processor is 1.2 cycles / byte (cpb) for ChaCha20 and 0.6 cpb for ChaCha8. ChaCha is very fast. 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…

> 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.

Re: PCG, A Family of Better Random Number Generators

#40

Post by echaozh »

vtsrh wrote: post #28
ufo wrote: post #5

There is a seminar about PCG from its author available on youtube. https://www.youtube.com/watch?v=45Oet5qjlms Its a bit long but I highly recommend it. I learned a lot about RNGs from it.

Speaker mentions[0] that it is possible to get a different statistically random value every time you run the program, without any input to the program, apparently by using some tricks, but she refuses to elaborate for the camera. Can anyone explain how that works? Has this something to do with address space randomization? [0]: https://youtu.be/45Oet5qjlms?t=1h3m3s

> (This last one relies on the operating system placing myRNG at a different address every time the program is run. It's not as strong as the other techniques.)

from: http://www.pcg-random.org/useful-features.html#id2

Post reply on HN