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/ff4f6a495428c5c0eaffb3521ad843...

portable results: https://gist.github.com/nkurz/a44d57538d4530362951beb1ea2c4c...

model results: https://gist.github.com/nkurz/2f362185b7fd42889b8bb533ced5f7...

assembly results: https://gist.github.com/nkurz/6e797e8b635931d2a0e4f32af6a12d...