3 ms·

> After some minor optimizing, on my laptop here are benchmarks on filling a 1kb byte array: > > Mwc-256-X-X-A-64 (This algorithm): 100.98 ns That comes to 10

> After some minor optimizing, on my laptop here are benchmarks on filling a 1kb byte array: > > Mwc-256-X-X-A-64 (This algorithm): 100.98 ns That comes to 10 GB/s. For comparison, I think ChaCha8 implemented with AVX-512 should run at a similar speed. Maybe a bit faster in short-ish, single-threaded benchmarks. To be clear, there are plenty of caveats in making this comparison: ChaCha8 won't hit that throughput on any output size smaller than 1 KiB. AVX-512 requires a very recent processor. Most library implementations don't include AVX-512 support. Power usage will be high. Downclocking will be an issue, especially with multithreading. Etc. etc. But in exchange, you get all the security properties. I think one takeaway here is that the gap between cryptographic and non-cryptographic is smaller than many people think, which argues in favor of secure defaults. (Though to be clear, I don't think OP or anyone in this thread is opposed to secure defaults.) Another takeaway is that a lot of these blockers, like hardware and library support, will continue to improve over time. So if you find that a CSPRNG isn't fast enough for your use case today, make sure to check again in a few years. And of course, as always, it's important to benchmark your specific use case if you're worried about performance.

loeg 5y ago
Chacha generates much bigger outputs (64 byte blocks vs 8 byte) and has somewhat bigger state (512 bits vs 256 or 128 bits). And AVX-512 is Intel-only. To make spinning up the AVX units worth it, you probably need to generate quite a lot of output in larger batches (ie, even bigger state required). It’s still interesting, but less competitive than looking at the GB/s for MB-sized outputs makes it seem.
- kevingadd 5y ago
  If you actually care about performance you should be generating batches of output and pulling entropy out of it, not invoking the PRNG every time you need a random byte. The icache and dcache impact of running all that prng code is going to eat into the performance of your actual software in a way that microbenchmarks won't show. So the need to do that with chacha isn't necessarily a problem, it may be pushing you towards a better design.
  - comex 5y ago
    Dcache impact? Of accessing the state which, for a non-cryptographically-secure PRNG, is often 128 bits? I'm not seeing it. Even CSPRNGs don't usually have state that's all that much larger. Surely there would be much higher dcache impact from storing and loading the batches of output. On the other hand, I can buy icache, along with function call overhead and lack of parallelism...
    - kevingadd 5y ago
      Depends on the algorithm, I suppose? Many algorithms that consume randomness in a way that is performance sensitive, like audio or image synthesis, are going to be processing streams of data and in that context being able to just stream random bits out of a cache line and into registers and through operations without making a bunch of calls is going to produce some advantages, even if a modern out of order processor can hide a lot of that. TBH I doubt the function call overhead even matters so much as the overall structure being something that will approach the maximum throughput of your hardware. It's a big advantage that the internal state of some PRNGs is very small, but you're still mutating the internal state, which means now you're creating dependency chains and dirtying a cache line, etc. Someone who's actually built chips before would know far better than me whether all of that adds up to a 1% hit to throughput or a 10% hit, though.
  - loeg 5y ago
    MCG (like pcg64_fast) is like a single 128-bit mul and a mask. There’s not a lot of icache impact.
- deleted 5y ago
  [deleted]

loeg 5y ago

Chacha generates much bigger outputs (64 byte blocks vs 8 byte) and has somewhat bigger state (512 bits vs 256 or 128 bits). And AVX-512 is Intel-only. To make spinning up the AVX units worth it, you probably need to generate quite a lot of output in larger batches (ie, even bigger state required). It’s still interesting, but less competitive than looking at the GB/s for MB-sized outputs makes it seem.

kevingadd 5y ago
If you actually care about performance you should be generating batches of output and pulling entropy out of it, not invoking the PRNG every time you need a random byte. The icache and dcache impact of running all that prng code is going to eat into the performance of your actual software in a way that microbenchmarks won't show. So the need to do that with chacha isn't necessarily a problem, it may be pushing you towards a better design.
- comex 5y ago
  Dcache impact? Of accessing the state which, for a non-cryptographically-secure PRNG, is often 128 bits? I'm not seeing it. Even CSPRNGs don't usually have state that's all that much larger. Surely there would be much higher dcache impact from storing and loading the batches of output. On the other hand, I can buy icache, along with function call overhead and lack of parallelism...
  - kevingadd 5y ago
    Depends on the algorithm, I suppose? Many algorithms that consume randomness in a way that is performance sensitive, like audio or image synthesis, are going to be processing streams of data and in that context being able to just stream random bits out of a cache line and into registers and through operations without making a bunch of calls is going to produce some advantages, even if a modern out of order processor can hide a lot of that. TBH I doubt the function call overhead even matters so much as the overall structure being something that will approach the maximum throughput of your hardware. It's a big advantage that the internal state of some PRNGs is very small, but you're still mutating the internal state, which means now you're creating dependency chains and dirtying a cache line, etc. Someone who's actually built chips before would know far better than me whether all of that adds up to a 1% hit to throughput or a 10% hit, though.
- loeg 5y ago
  MCG (like pcg64_fast) is like a single 128-bit mul and a mask. There’s not a lot of icache impact.
deleted 5y ago
[deleted]