4 ms·
It's been over a decade since I looked at this, but in real-time Monte Carlo path tracing the speed of your RNG is material. In simple enough scenes, probably s
by boulos 3y ago
It's been over a decade since I looked at this, but in real-time Monte Carlo path tracing the speed of your RNG is material. In simple enough scenes, probably something like 5-10% IIRC when using MT.
I appreciate that you had a note about performance, but you were pretty quick to dismiss that there's a large quality difference between rand() and any modern PRNG. Plenty of these are fine enough and paying for a CSPRNG with 4x or more the perf hit may be a mistake.
I do agree that if you don't know what you're going to use them for or don't know if you have a performance problem that you should just use a CSPRNG. The potential for someone to accidentally cause a security bug is not worth it. If they decide to do so intentionally, that's on them.
tl;dr: maybe "Need a PRNG? Start with one that's cryptographically secure"?
- nullc 3y agoThere are things with rand() like performance but much better properties. for randomized search I'm a fan of xoshiro256++ periodically reseeded by rdrand. Obviously if performance isn't a concern, a CSPRNG should be the default. But it often is a concern. Traditional 'fast' PRNGs have simple algebraic structure that is absolutely known to cause wrong results, they're not worth it compared to modern fast PRNGs. (I wouldn't ever use MT today, it's not on the pareto-frontier of performance vs quality and has a bad cache footprint) > tl;dr: maybe "Need a PRNG? Start with one that's cryptographically secure"? I agree but: I think if people do that, they'll often find that their whole process is now 20% slower than when they used rand() and then go back to rand. So I think it's also important to make people aware of fast generators with better properties.
- fanf2 3y agoThere are several PRNGs that are faster and more random than Mersenne Twister.
- nurandal 3y agoSome example benchmarks which compare MT against other newer algorithms in a couple of blog posts here: https://nullprogram.com/blog/2017/09/21/ https://nullprogram.com/blog/2017/09/21/ https://pixelesque.net/blog/2020/08/prng-evaluation-and-benchmarks-for-monte-carlo-simulations/ https://pixelesque.net/blog/2020/08/prng-evaluation-and-benc...
- loeg 3y agoThe other big nuisance of the MT is that its state is huge -- the most common version, MT19937, has ~2500 bytes of state and generates 32-bit numbers. A very good 64-bit PRNG only needs 16 bytes of state and a very good 32-bit PRNG only needs 8 bytes of state. That's >300x smaller. This is somewhat related to it being slow, of course, but also somewhat orthogonal.
- tczajka 3y agoI can just about believe that this kind of scenario might be a very rare exception where the performance difference is relevant and you might want to do something else. Still, color me skeptical. "In simple enough scenes"? OK perhaps, but we don't want to only run ray tracing for very simple scenes. Simple scenes are those cases where you probably don't need much calculation, so does it really matter that 5-10% of that simple calculation is RNG? It's the complicated computation-heavy scenes that matter! Also, one would have to see the code to judge this. For instance, maybe that code was wasting random bits a lot?
- nullc 3y agoIn the sorts of searches I often do, like fitting integer solutions to fast function approximations, searching for error correcting codes, and randomized SAT-like problems, or simulating usage of data structures for benchmarking them chacha is slow enough to meaningfully influence (even dominate) the runtime. I wouldn't want to use rand() because it's extremely likely that it will produce actually bad results. I agree one should use a CSPRNG like chacha (or rdrand) if its runtime is insignificant but then the question is: whats the best choice when it's not insignificant? Using rand is a bad idea.