5 ms·

SIMD Perlin Noise: Beating the Compiler with SSE (2014)

62 points by homarp 1y ago

jesse__ 1y ago
Author here, AMA :)
- jackmottatx 1y ago
  [dead]
- 0points 1y ago
  Nice write-up, and congratulations on the result! Since it's about perlin and performance, have you had a look at opensimplex? PS. bonsai looks really cool! Checking it out right now
  - jesse__ 1y ago
    I haven't looked at opensimplex. I will when I get around to doing a simplex implementation. And thanks for the kind words!
- Keyframe 1y ago
  pretty sweet! I'm mostly interested in how / what did you do to measure the performance and focus on a function. Is it perf pretty much with hist or visualizer or what?
  - jesse__ 1y ago
    I just called _rdtsc() before and after the noise gen once every iteration, and pushed the sample onto a fixed size buffer .. after some N iterations (4k maybe, can't remember) of samples, computed min/max/avg. There's a little project here that I used to benchmark in part 4 https://github.com/scallyw4g/bonsai_noise_bench https://github.com/scallyw4g/bonsai_noise_bench
- jokoon 1y ago
  you should post the result at the end and yes, make a benchmark (although I would not know how to make one, or what reference point to use) what do you think about the fastnoiselite implementation used in godot?
  - jesse__ 1y ago
    I kinda did post results at the end of part 4 .. I beat the SOTA by 1.8x There's a benchmark utility here: https://github.com/scallyw4g/bonsai_noise_bench https://github.com/scallyw4g/bonsai_noise_bench Fastnoise2 is a high quality library. Can't speak to fastnoiselite .. never looked at it.
- vlovich123 1y ago
  Which compiler & optimization settings did you use? Out of curiosity, any idea why the compiler failed to auto-vectorize the loops?
  - jesse__ 1y ago
    Clang -O2 .. -O3 didn't seem to make any appreciable difference. Re. the auto-vectorization, I really don't know. I didn't even read the assembly the compiler generated until at least halfway through the process. Generally I've found that you basically can't rely on the compiler auto vectorizing anything, ever, if it actually matters.
addaon 1y ago
Memories. As a personal project back in... 2003?... I decided to do something similar, implement 4D Perlin Noise in Altivec assembly. The only problem was that I had a G3 iBook; so I would write one instruction of assembly, then write a C function to interpret that assembly, building an interpreter for a very selective subset of PPC w/ Altivec that ran (slooooowly) on the G3. As I recall I got it down to ~200 instructions, and it worked perfectly the first time I ran it on a G4, which was pretty rewarding. Took me more than half a day, though. On an unrelated note, I got an intership with Apple's performance team that summer.
- deleted 1y ago
  [deleted]
KingLancelot 1y ago
[dead]
rincebrain 1y ago
Did you profile the results with different compilers? The last time I tried doing this kind of microoptimization for fun, I ended up bundling actual assembly files, because the generated assembly for intrinsics was so variable in performance across compilers it was the only way to get consistent results on many platforms.
- jesse__ 1y ago
  I only build the project this is embedded in with clang, so that's the only compiler I tested.
llm_nerd 1y ago
HN loves SIMD, and there is a "how I hand crafted a SIMD optimization" post doing numbers on here regularly. They're fun posts, and it absolutely speaks to the fact that writing code that optimizing compilers can robustly and comprehensively turn into good SIMD branches is somewhat of a black art. Which is why you, generally, shouldn't be doing either. You shouldn't rely upon the compiler to figure out your intentions, and you shouldn't be writing SIMD instructions directly unless you're writing a SIMD library or an optimizing compiler. Instead you should reach for one of the many available libraries that not only force you into appropriately structuring your data and calls for SIMD goodness, they're massively more portable and powerful. Google's Highway, for instance, will let you use their abstracted SIMD functions and it provides the optimization whether your target is SSE2-4, AVX, AVX2, AVX512, AVX10, or if you build for ARM NEON or SVE, for any conceivable vector size, or WASM's weird SIMD functions, or RISC-V's RVV, and several more, and when new widths and new options come out, the library adds the support and you might not have to change your code at all. There are loads of libraries like this (xsimd, EVE, SIMDe, etc). They all force you into thinking about structuring your code in a manner that is SIMDable -- instead of hoping the optimizing compiler will figure it out on its own -- and provide targeting for a vast trove of SIMD options without hand-writing for every option. I was going to quickly rewrite the example in Highway just to demonstrate but the Perlin stuff seems to be missing or significantly restructured. "But that is obvious and I'm mad that you commented this" - no, it isn't obvious whatsoever, and this "I hand-rolled some SSE now my app is super awesome look at the microbenchmark results on a very narrow, specific machine" content appears on here regularly, betraying a pretty big influence of beginners who don't know that it's almost certainly the wrong approach.
- 63 1y ago
  This is a valuable viewpoint that lines up somewhat with some other discussion I've seen on the topic [0]. I'd like to see more posts about structuring code for the auto vectorizor (with libraries or otherwise) rather than writing simd by hand. Do you have any documentation you'd recommend? [0] https://matklad.github.io/2023/04/09/can-you-trust-a-compiler-to-optimize-your-code.html https://matklad.github.io/2023/04/09/can-you-trust-a-compile...
- jesse__ 1y ago
twoodfin 1y ago
The year on this article should be (2024).
dragontamer 1y ago
SSE? It makes sense for 2014 when AVX was not too widely deployed. Today you can double the throughput with AVX and probably get 4x improvement with AVX512. GPU SIMD is also popular but perlin noise seems too 'small' a problem to be worth traversing PCIe over. But if you had a GPU shader that needed perlin noise as an input, I'd expect GPU to easily use this methodology. It is worth revisiting how different techniques worked out over the last decade. Strangely enough, CUDA code from 2014 would likely be still workable today (perlin noise doesn't need the new GPU instructions of 4x4 Float16 or Raytracing). OpenCL IMO is the wrong path though, which is what many would have picked from 2014 era for GPU.
- jesse__ 1y ago
  There are 4 parts. Spoiler: I went to AVX and beat the state of the art by 1.8x Also, doing it on the GPU is worth it, if you do large batches.
  - dragontamer 1y ago
    As far as fast RNGs available, Imma just plug an old, incomplete, weekend project for ya.... https://github.com/dragontamer/AESRand https://github.com/dragontamer/AESRand Especially because you are already in the AVX domain, a fast AVX RNG that uses like 3 registers should be useful to ya. .... Yeah I'm pretty sure aesenc these days has more throughout than multiply. (Edit: aesenc, at least a singular round, is largely a 32-bit operation and this has less complexity than a 64-bit multiply. Yeah I know it's over 128-bits but seriously, it's surprising how 'little' AES actually shuffles bits around per round). If you are fine with an inferior RNG, you probably can skip one or two instructions I did there. But the 'two rounds of AES' seems to be the minimum to pass PractRand or BigCrush. ------- Today, AES on AVX512 can perform 4x AES in parallel over all 512 bits. But the overall technique I did back then should allow for arbitrary skipping ahead as well. (Ex: thread#0 starts with iteration #0. Thread#1 starts with iteration #1000000. Etc. etc. with consistency because my increment function is simple 64-bit adds, a 64-bit multiply will skip forward easily) Alas, I don't think AESENC was ever ported to ymm registers and this your choices are 128-bit AESRAND vs 512-bit AESRAND.

62 points by homarp 1y ago

jesse__ 1y ago

Author here, AMA :)

jackmottatx 1y ago
[dead]
0points 1y ago
Nice write-up, and congratulations on the result! Since it's about perlin and performance, have you had a look at opensimplex? PS. bonsai looks really cool! Checking it out right now
- jesse__ 1y ago
  I haven't looked at opensimplex. I will when I get around to doing a simplex implementation. And thanks for the kind words!
Keyframe 1y ago
pretty sweet! I'm mostly interested in how / what did you do to measure the performance and focus on a function. Is it perf pretty much with hist or visualizer or what?
- jesse__ 1y ago
  I just called _rdtsc() before and after the noise gen once every iteration, and pushed the sample onto a fixed size buffer .. after some N iterations (4k maybe, can't remember) of samples, computed min/max/avg. There's a little project here that I used to benchmark in part 4 https://github.com/scallyw4g/bonsai_noise_bench https://github.com/scallyw4g/bonsai_noise_bench
jokoon 1y ago
you should post the result at the end and yes, make a benchmark (although I would not know how to make one, or what reference point to use) what do you think about the fastnoiselite implementation used in godot?
- jesse__ 1y ago
  I kinda did post results at the end of part 4 .. I beat the SOTA by 1.8x There's a benchmark utility here: https://github.com/scallyw4g/bonsai_noise_bench https://github.com/scallyw4g/bonsai_noise_bench Fastnoise2 is a high quality library. Can't speak to fastnoiselite .. never looked at it.
vlovich123 1y ago
Which compiler & optimization settings did you use? Out of curiosity, any idea why the compiler failed to auto-vectorize the loops?
- jesse__ 1y ago
  Clang -O2 .. -O3 didn't seem to make any appreciable difference. Re. the auto-vectorization, I really don't know. I didn't even read the assembly the compiler generated until at least halfway through the process. Generally I've found that you basically can't rely on the compiler auto vectorizing anything, ever, if it actually matters.

addaon 1y ago

Memories. As a personal project back in... 2003?... I decided to do something similar, implement 4D Perlin Noise in Altivec assembly. The only problem was that I had a G3 iBook; so I would write one instruction of assembly, then write a C function to interpret that assembly, building an interpreter for a very selective subset of PPC w/ Altivec that ran (slooooowly) on the G3. As I recall I got it down to ~200 instructions, and it worked perfectly the first time I ran it on a G4, which was pretty rewarding. Took me more than half a day, though. On an unrelated note, I got an intership with Apple's performance team that summer.

deleted 1y ago
[deleted]

KingLancelot 1y ago

[dead]

rincebrain 1y ago

Did you profile the results with different compilers? The last time I tried doing this kind of microoptimization for fun, I ended up bundling actual assembly files, because the generated assembly for intrinsics was so variable in performance across compilers it was the only way to get consistent results on many platforms.

jesse__ 1y ago
I only build the project this is embedded in with clang, so that's the only compiler I tested.

llm_nerd 1y ago

HN loves SIMD, and there is a "how I hand crafted a SIMD optimization" post doing numbers on here regularly. They're fun posts, and it absolutely speaks to the fact that writing code that optimizing compilers can robustly and comprehensively turn into good SIMD branches is somewhat of a black art. Which is why you, generally, shouldn't be doing either. You shouldn't rely upon the compiler to figure out your intentions, and you shouldn't be writing SIMD instructions directly unless you're writing a SIMD library or an optimizing compiler. Instead you should reach for one of the many available libraries that not only force you into appropriately structuring your data and calls for SIMD goodness, they're massively more portable and powerful. Google's Highway, for instance, will let you use their abstracted SIMD functions and it provides the optimization whether your target is SSE2-4, AVX, AVX2, AVX512, AVX10, or if you build for ARM NEON or SVE, for any conceivable vector size, or WASM's weird SIMD functions, or RISC-V's RVV, and several more, and when new widths and new options come out, the library adds the support and you might not have to change your code at all. There are loads of libraries like this (xsimd, EVE, SIMDe, etc). They all force you into thinking about structuring your code in a manner that is SIMDable -- instead of hoping the optimizing compiler will figure it out on its own -- and provide targeting for a vast trove of SIMD options without hand-writing for every option. I was going to quickly rewrite the example in Highway just to demonstrate but the Perlin stuff seems to be missing or significantly restructured. "But that is obvious and I'm mad that you commented this" - no, it isn't obvious whatsoever, and this "I hand-rolled some SSE now my app is super awesome look at the microbenchmark results on a very narrow, specific machine" content appears on here regularly, betraying a pretty big influence of beginners who don't know that it's almost certainly the wrong approach.

63 1y ago
This is a valuable viewpoint that lines up somewhat with some other discussion I've seen on the topic [0]. I'd like to see more posts about structuring code for the auto vectorizor (with libraries or otherwise) rather than writing simd by hand. Do you have any documentation you'd recommend? [0] https://matklad.github.io/2023/04/09/can-you-trust-a-compiler-to-optimize-your-code.html https://matklad.github.io/2023/04/09/can-you-trust-a-compile...
jesse__ 1y ago

twoodfin 1y ago

The year on this article should be (2024).

dragontamer 1y ago

SSE? It makes sense for 2014 when AVX was not too widely deployed. Today you can double the throughput with AVX and probably get 4x improvement with AVX512. GPU SIMD is also popular but perlin noise seems too 'small' a problem to be worth traversing PCIe over. But if you had a GPU shader that needed perlin noise as an input, I'd expect GPU to easily use this methodology. It is worth revisiting how different techniques worked out over the last decade. Strangely enough, CUDA code from 2014 would likely be still workable today (perlin noise doesn't need the new GPU instructions of 4x4 Float16 or Raytracing). OpenCL IMO is the wrong path though, which is what many would have picked from 2014 era for GPU.

jesse__ 1y ago
There are 4 parts. Spoiler: I went to AVX and beat the state of the art by 1.8x Also, doing it on the GPU is worth it, if you do large batches.
- dragontamer 1y ago
  As far as fast RNGs available, Imma just plug an old, incomplete, weekend project for ya.... https://github.com/dragontamer/AESRand https://github.com/dragontamer/AESRand Especially because you are already in the AVX domain, a fast AVX RNG that uses like 3 registers should be useful to ya. .... Yeah I'm pretty sure aesenc these days has more throughout than multiply. (Edit: aesenc, at least a singular round, is largely a 32-bit operation and this has less complexity than a 64-bit multiply. Yeah I know it's over 128-bits but seriously, it's surprising how 'little' AES actually shuffles bits around per round). If you are fine with an inferior RNG, you probably can skip one or two instructions I did there. But the 'two rounds of AES' seems to be the minimum to pass PractRand or BigCrush. ------- Today, AES on AVX512 can perform 4x AES in parallel over all 512 bits. But the overall technique I did back then should allow for arbitrary skipping ahead as well. (Ex: thread#0 starts with iteration #0. Thread#1 starts with iteration #1000000. Etc. etc. with consistency because my increment function is simple 64-bit adds, a 64-bit multiply will skip forward easily) Alas, I don't think AESENC was ever ported to ymm registers and this your choices are 128-bit AESRAND vs 512-bit AESRAND.