6 ms·

Author here. I am embarrassed and surprised to find this article on the front page of HN. I think it isn't well-written, and I never intended it to appeal to a

by nayuki 10y ago

Author here. I am embarrassed and surprised to find this article on the front page of HN. I think it isn't well-written, and I never intended it to appeal to a wide audience. The only fact this article really proves is that I can write an x86 AVX implementation of FFT, such that it has reasonable performance and reasonably readable code. I threw together the C code quickly - the portable version is basically the result of "what if I implement FFT in a relatively naive way?", and the AVX model version is the result of "what if I simulate the computation order and memory access pattern of the AVX code in pure C?". You wouldn't be wrong to say that I created strawmen C code as comparisons to the AVX code. I view the article as a non-thorough wrapper around a proof-of-concept AVX code. I failed on a lot of fronts - comparing performance against well-known high-performance libraries like FFTW, explaining why I designed my AVX code the way it is, elaborating on the memory access patterns, et cetera. For these I apologize to the reader who had their hopes up.

nkurz 10y ago
No need to be embarrassed. I think it's useful article, both as a pedagogical "proof of concept" and as a way of evaluating the ability of current compilers to vectorize code. I used a shell script to compile your code with a variety of compilers (gcc-4.8, gcc-4.9, gcc-5, gcc-6, icc-16, icc-17, and clang-4.0) each with a variety of compilation options (-O0, -O1, -O2, -O3, -Ofast, -march=native, -flto/-ipo) to see how they fared on a recent Intel Skylake machine. Across all combinations, I got results that mostly matched what you found. Some takeaways (highly influenced by my own opinions): Avoid -O0 for production code. It no longer means "without optimization", and should be understood as "put everything on the stack for easy debugging". The difference between -O1, -O2, -O3, and -Ofast can be large, but in this case the spread was small (about 10%). Higher numbers usually mean faster performance, but not always. If it really matters, measure. If you have to guess, use -Ofast (which for GCC is approximately -O3 plus -ffast-math). The flag that makes the biggest positive difference here is "-march=native", which tells the compiler it can use all the instructions supported by the machine you are compiling on. If you are running the software yourself rather than distributing it to others, this should probably be your default. If you don't specify it (or another architecture baseline) your code will run on much older machines, but at the cost of missing many of the vectorization improvements made over the last decade. Link time optimization (-flto for gcc and clang) or interprocedural optimization (-ipo in icc) lets the compiler optimize across compilation units rather than only within them. Approximately, it makes everything a candidate for inlining, thus giving many more opportunities for optimization. It doesn't make a big difference here (since almost all the work is done in one function) but you should likely be using it more than you are. Overall, the "portable" version is slower than the "model", which in turn is slower than the "assembly". One read of this is that we don't yet have a "sufficiently clever compiler": the "naive" C version is slower than the "explicitly vectorizable" one, and both are beaten by "naive assembly". This is definitely interesting, and often true, and counters the refrain of "don't bother trying to beat the compiler", but I think it's worth digging deeper and asking why the simplistic assembly is faster than the complicated compiler. I think the main reason here is that the C code is not sufficiently precise, and doesn't actually reflect the programmer's intent. The compiler fails to vectorize because the code as written isn't safe to vectorize: legally, there could be "aliasing" between the different arrays. The assembly is written to take advantage of the absence of aliasing, but the compiler wasn't given enough information to do this. Some of this information can be provided by a liberal sprinkling of "restrict" keywords: "void fft_transform(const void * tables, double * restrict real, double * restrict imag)". But I don't think it's fair to put the blame on the programmer for skipping these. Rather than being safe and assuming that the arrays for "real" and "imag" might overlap, in this case it would clearly be more helpful for the compiler to ask the programmer for more guidance rather than silently giving up. Intel's been doing a fairly good job of giving icc (and icpc) the ability to explain why loops cannot be vectorized. "-qopt-report" and "-guide-vec" give useful hints about what to be changed to allow vectorization. But it still requires significant expertise to figure out what the hints mean, which pragmas to add, and whether it's safe to add them. In this case, the hand written assembly is faster not because the compiler is generating bad code, but because it incorporates the programmer's silent assumptions. It would be nice if compilers were able to give better feedback to the programmer, as a means of making these assumptions (or their absence) more explicit. Do gcc and clang have options to provide this guidance? Are there outside tools that can? compilation script: https://gist.github.com/nkurz/ff4f6a495428c5c0eaffb3521ad8439b https://gist.github.com/nkurz/ff4f6a495428c5c0eaffb3521ad843... portable results: https://gist.github.com/nkurz/a44d57538d4530362951beb1ea2c4cad https://gist.github.com/nkurz/a44d57538d4530362951beb1ea2c4c... model results: https://gist.github.com/nkurz/2f362185b7fd42889b8bb533ced5f7d5 https://gist.github.com/nkurz/2f362185b7fd42889b8bb533ced5f7... assembly results: https://gist.github.com/nkurz/6e797e8b635931d2a0e4f32af6a12d1a https://gist.github.com/nkurz/6e797e8b635931d2a0e4f32af6a12d...
- user5994461 10y ago
  IMO. The article shows two things. 1) The author is much better at writing ASM code than at writing C code and optimizing it for performances. 2) Even people who read blogs, write blogs and try pretty hard are still struggling with advanced optimizations. Guess that's why I could make a living out of that and why there are so few of us.
- p1esk 10y ago
  Thanks! Can you point to some guides on C code optimization?
  - nkurz 10y ago
    There's a lot of information out there, but what's most useful depends on your goals and current level of knowledge. If you haven't read them yet, Agner Fog's guides are an excellent place to start: http://agner.org/optimize/ http://agner.org/optimize/. Intel's Software Development Manuals are enormous, but contain a lot of great information: https://software.intel.com/en-us/articles/intel-sdm https://software.intel.com/en-us/articles/intel-sdm. Their "Software Optimization Reference Manual" might be the best place to jump in: https://software.intel.com/sites/default/files/managed/9e/bc/64-ia-32-architectures-optimization-manual.pdf https://software.intel.com/sites/default/files/managed/9e/bc....
    - p1esk 10y ago
      Wow, great resources! Do you have any suggestions about learning parallelization techniques? Like which one is better: MPI, OpenMP, Cilk, pthreads? My field is machine learning, and I've been using high level libraries until now, but I'd like to learn how to write something in C that does not suck in terms of speed.
      - nkurz 10y ago
        I'm less knowledgeable about parallelization, so wouldn't want to make a recommendation. But I've used each of those a little bit, and would gently suggest that OpenMP might be a good starting point for exploration. I was impressed by how easy it was to incorporate, and the performance seemed good to the extent that I used it. My naive first impressions were that MPI was clunky, required expertise to get good results, and should be reserved for when you need to run on multiple machines; Cilk was slick, had a nice syntax, but as of two years ago was still for early adopters; and OpenMP was a happy medium of syntax, support, and performance, making it a good default if you were trying to utilize multiple cores and processors on a single machine. pthreads is the underlying thread implementation used on Linux, and the others are higher level interfaces that run on top of this. You should understand the basics of how pthreads works for intuition on how the others will perform, but unless you need something out-of-the-ordinary you probably shouldn't implement anything with it directly.
user5994461 10y ago
Indeed. The code is a disappointment. The various AVX.c versions don't use any AVX instructions. That is deceptive.
- nayuki 10y ago
  Sorry about that naming confusion. As the description says: fft-x8664-avx.s: FFT core implementation for x86-64 AVX fft-x8664-avx-aux.c: Auxiliary FFT functions for x86-64 AVX fft-model-of-x8664-avx.c: C code illustrating how the x86-64 AVX code works
  - user5994461 10y ago
    I understood what the programs are. I am complaining that you don't have a C program using the AVX instructions (in C). All the AVX functions are directly accessible from C (see: intrinsics). For a valid comparison, I would expect a C program using AVX instructions against an assembly program using AVX. Your comparison has C-without-AVX against ASM-with-AVX. Of course, it's faster with AVX ;)

by nayuki 10y ago

nkurz 10y ago

No need to be embarrassed. I think it's useful article, both as a pedagogical "proof of concept" and as a way of evaluating the ability of current compilers to vectorize code. I used a shell script to compile your code with a variety of compilers (gcc-4.8, gcc-4.9, gcc-5, gcc-6, icc-16, icc-17, and clang-4.0) each with a variety of compilation options (-O0, -O1, -O2, -O3, -Ofast, -march=native, -flto/-ipo) to see how they fared on a recent Intel Skylake machine. Across all combinations, I got results that mostly matched what you found. Some takeaways (highly influenced by my own opinions): Avoid -O0 for production code. It no longer means "without optimization", and should be understood as "put everything on the stack for easy debugging". The difference between -O1, -O2, -O3, and -Ofast can be large, but in this case the spread was small (about 10%). Higher numbers usually mean faster performance, but not always. If it really matters, measure. If you have to guess, use -Ofast (which for GCC is approximately -O3 plus -ffast-math). The flag that makes the biggest positive difference here is "-march=native", which tells the compiler it can use all the instructions supported by the machine you are compiling on. If you are running the software yourself rather than distributing it to others, this should probably be your default. If you don't specify it (or another architecture baseline) your code will run on much older machines, but at the cost of missing many of the vectorization improvements made over the last decade. Link time optimization (-flto for gcc and clang) or interprocedural optimization (-ipo in icc) lets the compiler optimize across compilation units rather than only within them. Approximately, it makes everything a candidate for inlining, thus giving many more opportunities for optimization. It doesn't make a big difference here (since almost all the work is done in one function) but you should likely be using it more than you are. Overall, the "portable" version is slower than the "model", which in turn is slower than the "assembly". One read of this is that we don't yet have a "sufficiently clever compiler": the "naive" C version is slower than the "explicitly vectorizable" one, and both are beaten by "naive assembly". This is definitely interesting, and often true, and counters the refrain of "don't bother trying to beat the compiler", but I think it's worth digging deeper and asking why the simplistic assembly is faster than the complicated compiler. I think the main reason here is that the C code is not sufficiently precise, and doesn't actually reflect the programmer's intent. The compiler fails to vectorize because the code as written isn't safe to vectorize: legally, there could be "aliasing" between the different arrays. The assembly is written to take advantage of the absence of aliasing, but the compiler wasn't given enough information to do this. Some of this information can be provided by a liberal sprinkling of "restrict" keywords: "void fft_transform(const void * tables, double * restrict real, double * restrict imag)". But I don't think it's fair to put the blame on the programmer for skipping these. Rather than being safe and assuming that the arrays for "real" and "imag" might overlap, in this case it would clearly be more helpful for the compiler to ask the programmer for more guidance rather than silently giving up. Intel's been doing a fairly good job of giving icc (and icpc) the ability to explain why loops cannot be vectorized. "-qopt-report" and "-guide-vec" give useful hints about what to be changed to allow vectorization. But it still requires significant expertise to figure out what the hints mean, which pragmas to add, and whether it's safe to add them. In this case, the hand written assembly is faster not because the compiler is generating bad code, but because it incorporates the programmer's silent assumptions. It would be nice if compilers were able to give better feedback to the programmer, as a means of making these assumptions (or their absence) more explicit. Do gcc and clang have options to provide this guidance? Are there outside tools that can? compilation script: https://gist.github.com/nkurz/ff4f6a495428c5c0eaffb3521ad8439b https://gist.github.com/nkurz/ff4f6a495428c5c0eaffb3521ad843... portable results: https://gist.github.com/nkurz/a44d57538d4530362951beb1ea2c4cad https://gist.github.com/nkurz/a44d57538d4530362951beb1ea2c4c... model results: https://gist.github.com/nkurz/2f362185b7fd42889b8bb533ced5f7d5 https://gist.github.com/nkurz/2f362185b7fd42889b8bb533ced5f7... assembly results: https://gist.github.com/nkurz/6e797e8b635931d2a0e4f32af6a12d1a https://gist.github.com/nkurz/6e797e8b635931d2a0e4f32af6a12d...

user5994461 10y ago
IMO. The article shows two things. 1) The author is much better at writing ASM code than at writing C code and optimizing it for performances. 2) Even people who read blogs, write blogs and try pretty hard are still struggling with advanced optimizations. Guess that's why I could make a living out of that and why there are so few of us.
p1esk 10y ago
Thanks! Can you point to some guides on C code optimization?
- nkurz 10y ago
  There's a lot of information out there, but what's most useful depends on your goals and current level of knowledge. If you haven't read them yet, Agner Fog's guides are an excellent place to start: http://agner.org/optimize/ http://agner.org/optimize/. Intel's Software Development Manuals are enormous, but contain a lot of great information: https://software.intel.com/en-us/articles/intel-sdm https://software.intel.com/en-us/articles/intel-sdm. Their "Software Optimization Reference Manual" might be the best place to jump in: https://software.intel.com/sites/default/files/managed/9e/bc/64-ia-32-architectures-optimization-manual.pdf https://software.intel.com/sites/default/files/managed/9e/bc....
  - p1esk 10y ago
    Wow, great resources! Do you have any suggestions about learning parallelization techniques? Like which one is better: MPI, OpenMP, Cilk, pthreads? My field is machine learning, and I've been using high level libraries until now, but I'd like to learn how to write something in C that does not suck in terms of speed.
    - nkurz 10y ago
      I'm less knowledgeable about parallelization, so wouldn't want to make a recommendation. But I've used each of those a little bit, and would gently suggest that OpenMP might be a good starting point for exploration. I was impressed by how easy it was to incorporate, and the performance seemed good to the extent that I used it. My naive first impressions were that MPI was clunky, required expertise to get good results, and should be reserved for when you need to run on multiple machines; Cilk was slick, had a nice syntax, but as of two years ago was still for early adopters; and OpenMP was a happy medium of syntax, support, and performance, making it a good default if you were trying to utilize multiple cores and processors on a single machine. pthreads is the underlying thread implementation used on Linux, and the others are higher level interfaces that run on top of this. You should understand the basics of how pthreads works for intuition on how the others will perform, but unless you need something out-of-the-ordinary you probably shouldn't implement anything with it directly.

user5994461 10y ago

Indeed. The code is a disappointment. The various AVX.c versions don't use any AVX instructions. That is deceptive.

nayuki 10y ago
Sorry about that naming confusion. As the description says: fft-x8664-avx.s: FFT core implementation for x86-64 AVX fft-x8664-avx-aux.c: Auxiliary FFT functions for x86-64 AVX fft-model-of-x8664-avx.c: C code illustrating how the x86-64 AVX code works
- user5994461 10y ago
  I understood what the programs are. I am complaining that you don't have a C program using the AVX instructions (in C). All the AVX functions are directly accessible from C (see: intrinsics). For a valid comparison, I would expect a C program using AVX instructions against an assembly program using AVX. Your comparison has C-without-AVX against ASM-with-AVX. Of course, it's faster with AVX ;)