3 ms·
I took a quick look at your code on Skylake. Looks reasonable, although your recursive approach to horizontal summation probably isn't what you want. Rather t
by nkurz 10y ago
I took a quick look at your code on Skylake. Looks reasonable, although your recursive approach to horizontal summation probably isn't what you want. Rather than writing and re-reading you probably want to "accumulate" the sums into two YMM registers, then add these, then horizontal sum once. Not all instructions have the same cost, and horizontal addition is more costly than addition or multiplication.
Look at Agner's instruction tables for Broadwell for details: http://agner.org/optimize/instruction_tables.pdf http://agner.org/optimize/instruction_tables.pdf. It's initially hard to figure out what the columns mean, but worth the effort. Going further, you can probably use the "FMA" (Fused Multiply Add) instructions, which are essentially designed for dot products. You can do two of these per cycle, each of which does a multiplication and addition of a YMM vector.
I compiled this code with -mavx2 flag for my Broadwell Xeon CPU.
I can't remember the details of -march for Clang, but I recall that there is some oddity with older versions that -march=native on Broadwell requires -mavx2 in addition. But to get the correct instruction set, I think it needs both flags. In most cases (always for icc and gcc), -march=native is all you need.
when compiling with these flags, does clang actually use those AVX instructions that I tried to do manually
Yes, exactly that. Modern optimizing compilers look at the code you've written, and (when asked politely and all the stars aline) rewrite it to do something equivalent using the vector instructions. In many cases, you can get the same performance with simple scalar code as with vector intrinsics if the compiler cooperates, but it can be tricky to write the scalar code in a manner that the compiler is willing to vectorize.
It's easy and worthwhile to look at the assembly generated by the compiler. It's difficult to understand at first, but it's a great way to learn, and you should be doing it for any loop where the performance really matters. Figure out "objdump -d" use "perf record / perf report", or compile to assembly with -S. Take a look at the fast compiler generated code to see what it's doing, then figure out if you can make it faster.
I'm also not clear what's the difference between aligned and unaligned AVX load/store instructions, in terms of performance.
A deep morass, but worth looking into. Agner covers it pretty well. On current x64, there is essentially no difference in speed between the aligned and unaligned instructions when using aligned data. The aligned instructions crash when they encounter unaligned data, and the unaligned instructions continue but might be slowed down.
My general rule for modern Intel processors would be to try very hard to align your data if you can, but always use the unaligned instructions if they exist. Unaligned stores are typically much worse than unaligned reads. But apart from unaligned stores that cross 4KB boundaries, vector instructions are usually still a win if your algorithm allows them.
- p1esk 10y agoNate, first of all, thank you for your detailed responses. I really appreciate it! Second, your suggestion to use fma instruction for dot product is great - the code is both simpler and much faster. I wasted some time trying to run the code on my work computer, where it compiled fine, however exited without any output. Turned out that CPU is Ivy Bridge and doesn't support AVX2. So it seems that compiling with -mfma will convince the compiler to use non-existing instructions, regardless of the architecture. I'm now wondering if I should upgrade GCC on my Ubuntu box - the default was 4.8, which I upgraded to 4.9, however, the latest is 6.2. Is there a reason they keep it so old? Anyway, Agner guide to optimization is pretty interesting, lots of stuff to learn. My naive original code when compiled with Ofast and march=native is still faster than my AVX code compiled without any optimizations, but hopefully one day that will be able to beat it!