3 ms·

Xorshift is like 10 cycles. AES-NI can take hundreds, depending on the number of rounds. In the case of brute force Monte Carlo path tracing, the speed of the

Xorshift is like 10 cycles. AES-NI can take hundreds, depending on the number of rounds. In the case of brute force Monte Carlo path tracing, the speed of the RNG is important, because you have dozens or hundreds of rays per pixel, each with multiple bounces, and every bounce samples from your RNG. When your render times are 6 hours per frame to begin with, you really don't want to mess around.

e12e 7y ago
Cycles pr what? Not bit, byte? If you generate a gig of random data (repeat when you read to the end) - is ares still too slow?
wolf550e 7y ago
AES-128-CTR on my laptop is 4.8GB/sec per core. I'm sure something producing random enough output for simulation can be built that is as fast as memcpy, but would anything real be affected by the difference?
- dragontamer 7y ago
  https://github.com/dragontamer/AESRand https://github.com/dragontamer/AESRand Yes, it is possible but its difficult to do it right. I ran into at least 3 or 4 "roadblocks" while designing this algorithm, fortunately I managed to get through all of them. I've got an unrolled dual-stream going at 37.1 GBps on Threadripper 1950x (which has 2x AES pipelines). ~29.2 GBps for more "typical" usage (but still impractical). The issue with this is that random-bits of this speed are almost useless. A division or modulus operation takes 80-cycles (~20 nanoseconds) so as soon as you do "rand() % 6" (assuming you wanted a 6-sided dice roll), you've completely wreaked the bit-generator. A branch-misprediction is like 15-cycles, so that singular if-statement in your code that uses the RNG-number would be 5x slower than the generator itself. Its fast, but I don't know how practical it is. There's no practical way to use all of these random bits that I'm aware of. I did get a bit-compatible POWER9 version running by the way. So its portable across systems (at least, systems with an AES-encoder. ARM, Power9, and 2010-era x86.). Rasp. Pi doesn't have a CPU-AES engine however (its outside of the core), so Rasp. Pi can't use this methodology. -------------- If I were to actually push forward with this project more, I'd need to study on whole-program optimization, so that the (rarely used) XMM registers can be pragmatically used in a lot of code. The entirety of this RNG fits inside a single XMM register, so it'd benefit grossly from whole-program optimization. The XMM-data should also be fed into SIMD somehow, some kind of engine into ispc or OpenMP SIMD code. A bunch of raw-bits coming in through assembly commands is somewhat impractical, no matter how you look at it. Dan Lemire informed me of an amazing algorithm (that does work with AES XMM registers) that creates uniform random numbers out of a few multiply instructions. So I can get XMM-registers full of arbitrary integers with very low bias. (ex: numbers between 0 and 100) out of the bitstream. I also managed to convert the numbers into single-precision floats and double-precision floats between 0 and 1.0 uniformly. Still, this only really seems practical if you have SIMD-code that actually consumes all of these bits. Converting from XMM-registers into RAX registers has quite a bit of slowdown. I don't think the typical simulation code is actually limited by the speed of RNGs at all.
clarry 7y ago
> When your render times are 6 hours per frame Ok, let's say we're rendering at 8K (32 megapixels), 200 rays per pixel, 20 bounces per ray. And rendering that frame takes 6 hours. How many (mega)bytes of random data do we need per second? ; (32*10^6) * 200 * 20 / (6*60*60) / (1024^2) ~5.65140335648148148148 Six whopping megabytes per second, for the entire job, across all cores! Well, that assumed you only need one byte per bounce. Maybe you need a few bytes? And here I can pull an order of magnitude more and then some (180 megabytes/s) via /dev/urandom on OpenBSD (i.e. Chacha20, no hardware accel), using a single core of a few-years-old fanless mini PC (some Intel Celeron with "U" postfix). I generally don't buy the argument that your PRNG needs to be super duper fast, because usually the simulation is doing much more than just generating random data, and all that work is so much more expensive than even a relatively expensive CSPRNG. At least my ray tracers are. Generating rays is actually trivial compared to traversing, intersecting and shading the scene.. goodness gracious if I need to do actual texture & normal map lookups at a high resolution, so many cache misses :( That said, a simple and fast PRNG with little internal state can make life easier if you want reproducibility.. and it might be easier to build a reproducible simulation if your RNG gives exactly one word the size you need, instead of requiring you to generate a big block (and then extract things out of it somehow). This is especially the case with threaded sims. So yeah. But in this case, I wouldn't be looking at something like XorShift, I'd be looking at a random map that allows me to use (e.g.) the pixel's coordinates and a frame & bounce counter as the input and get matching (constant) output. Now it no longer matters which thread renders which pixel and when, the result will be all the same. It's not hard to build such functions, but they will be slower than XorShift if you want comparable quality. Speed should be no problem though.
- littlestymaar 7y ago
  It's amazing how much efforts people are willing to invest to contradict others' experience on the Internet. The GP is giving a real-life example (people having complained about something being too slow compared to xorshift) and yet you try to do the math to prove it couldn't happen…
  - clarry 7y ago

e12e 7y ago

Cycles pr what? Not bit, byte? If you generate a gig of random data (repeat when you read to the end) - is ares still too slow?

wolf550e 7y ago

AES-128-CTR on my laptop is 4.8GB/sec per core. I'm sure something producing random enough output for simulation can be built that is as fast as memcpy, but would anything real be affected by the difference?

dragontamer 7y ago
https://github.com/dragontamer/AESRand https://github.com/dragontamer/AESRand Yes, it is possible but its difficult to do it right. I ran into at least 3 or 4 "roadblocks" while designing this algorithm, fortunately I managed to get through all of them. I've got an unrolled dual-stream going at 37.1 GBps on Threadripper 1950x (which has 2x AES pipelines). ~29.2 GBps for more "typical" usage (but still impractical). The issue with this is that random-bits of this speed are almost useless. A division or modulus operation takes 80-cycles (~20 nanoseconds) so as soon as you do "rand() % 6" (assuming you wanted a 6-sided dice roll), you've completely wreaked the bit-generator. A branch-misprediction is like 15-cycles, so that singular if-statement in your code that uses the RNG-number would be 5x slower than the generator itself. Its fast, but I don't know how practical it is. There's no practical way to use all of these random bits that I'm aware of. I did get a bit-compatible POWER9 version running by the way. So its portable across systems (at least, systems with an AES-encoder. ARM, Power9, and 2010-era x86.). Rasp. Pi doesn't have a CPU-AES engine however (its outside of the core), so Rasp. Pi can't use this methodology. -------------- If I were to actually push forward with this project more, I'd need to study on whole-program optimization, so that the (rarely used) XMM registers can be pragmatically used in a lot of code. The entirety of this RNG fits inside a single XMM register, so it'd benefit grossly from whole-program optimization. The XMM-data should also be fed into SIMD somehow, some kind of engine into ispc or OpenMP SIMD code. A bunch of raw-bits coming in through assembly commands is somewhat impractical, no matter how you look at it. Dan Lemire informed me of an amazing algorithm (that does work with AES XMM registers) that creates uniform random numbers out of a few multiply instructions. So I can get XMM-registers full of arbitrary integers with very low bias. (ex: numbers between 0 and 100) out of the bitstream. I also managed to convert the numbers into single-precision floats and double-precision floats between 0 and 1.0 uniformly. Still, this only really seems practical if you have SIMD-code that actually consumes all of these bits. Converting from XMM-registers into RAX registers has quite a bit of slowdown. I don't think the typical simulation code is actually limited by the speed of RNGs at all.

clarry 7y ago

> When your render times are 6 hours per frame Ok, let's say we're rendering at 8K (32 megapixels), 200 rays per pixel, 20 bounces per ray. And rendering that frame takes 6 hours. How many (mega)bytes of random data do we need per second? ; (32*10^6) * 200 * 20 / (6*60*60) / (1024^2) ~5.65140335648148148148 Six whopping megabytes per second, for the entire job, across all cores! Well, that assumed you only need one byte per bounce. Maybe you need a few bytes? And here I can pull an order of magnitude more and then some (180 megabytes/s) via /dev/urandom on OpenBSD (i.e. Chacha20, no hardware accel), using a single core of a few-years-old fanless mini PC (some Intel Celeron with "U" postfix). I generally don't buy the argument that your PRNG needs to be super duper fast, because usually the simulation is doing much more than just generating random data, and all that work is so much more expensive than even a relatively expensive CSPRNG. At least my ray tracers are. Generating rays is actually trivial compared to traversing, intersecting and shading the scene.. goodness gracious if I need to do actual texture & normal map lookups at a high resolution, so many cache misses :( That said, a simple and fast PRNG with little internal state can make life easier if you want reproducibility.. and it might be easier to build a reproducible simulation if your RNG gives exactly one word the size you need, instead of requiring you to generate a big block (and then extract things out of it somehow). This is especially the case with threaded sims. So yeah. But in this case, I wouldn't be looking at something like XorShift, I'd be looking at a random map that allows me to use (e.g.) the pixel's coordinates and a frame & bounce counter as the input and get matching (constant) output. Now it no longer matters which thread renders which pixel and when, the result will be all the same. It's not hard to build such functions, but they will be slower than XorShift if you want comparable quality. Speed should be no problem though.

littlestymaar 7y ago
It's amazing how much efforts people are willing to invest to contradict others' experience on the Internet. The GP is giving a real-life example (people having complained about something being too slow compared to xorshift) and yet you try to do the math to prove it couldn't happen…
- clarry 7y ago