4 ms·

Instruction count is not everything but when something is 10x larger, unless the 1x is extremely complicated, I think it is safe to expect that the 10x version

Instruction count is not everything but when something is 10x larger, unless the 1x is extremely complicated, I think it is safe to expect that the 10x version will run slower. This 1x version is extremely trivial despite that one branch. .L4: mov edx, edi and edx, 1 cmp edx, 1 sbb eax, -1 shr edi jne .L4 ret In the first run, jne might be mispredicted (equating to a pipeline flush, ~15 cycles) but in all the other consecutive runs it will be predicted correctly. This means that the larger the amount of iterations is, cost of the first misprediction becomes more and more negligible. Vectorized execution OTOH is not cheap and does not necessarily result in faster code so purely seeing it in assembly would not mean much without actually measuring it. Scalar versions of the same code may be faster than the compiler-generated auto-vectorization code. Each SIMD instruction has a latency attached to it (see https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#techs=SSE_ALL,AVX_ALL https://www.intel.com/content/www/us/en/docs/intrinsics-guid...) and the majority of those SIMD latencies are in between 1 and 7 CPU cycles so definitely not free as in a free beer. That said, I am surprised by the results - in my mental model of how things work this does not add up. Rust assembly is ~50 instructions, roughly ~30 of them being vector (SIMD) instructions and the rest of ~20 instructions being the superset of (only) 6 instructions used in C++ assembly. I cannot see how those 6 instructions, even with the branch mispredict cost of ~15 cycles, can run ~2.5x slower than the pretty much convoluted version of the SIMD popcnt.

orf 3y ago
> That said, I am surprised by the results - in my mental model of how things work this does not add up. Rust assembly is ~50 instructions, roughly ~30 of them being vector (SIMD) instructions and the rest of ~20 instructions being the superset of (only) 6 instructions used in C++ assembly. I cannot see how those 6 instructions, even with the branch mispredict cost of ~15 cycles, can run ~2.5x slower than the pretty much convoluted version of the SIMD popcnt. > I cannot see how those 6 instructions, even with the branch mispredict cost of ~15 cycles, can run ~2.5x slower than the pretty much convoluted version of the SIMD popcnt. I fleshed out the benchmarks a bit, to compare `popcnt` itself and a no-op baseline: https://quick-bench.com/q/Bb36LyruJ1r8pzm8o_hjckU-xcI https://quick-bench.com/q/Bb36LyruJ1r8pzm8o_hjckU-xcI The quick-bench tool gives some nice assembly-level timing information[1] but I couldn't get it to work with my janky inline-copy-paste-assembly, and I blew past my curiosity time budget for this. You seem pretty experienced and I'd love to know more about this, so maybe if you know how to get the "popcnt_rs" extern assembly function to be inlined in the quick-bench link below we could take a look in more detail? 1. Click "assembly" and select "BM_cpp" from here: https://quick-bench.com/q/Bb36LyruJ1r8pzm8o_hjckU-xcI https://quick-bench.com/q/Bb36LyruJ1r8pzm8o_hjckU-xcI
- menaerus 3y ago
  There's a data dependency between those 6 instructions so out-of-order execution unit won't be able to kick in as much but still ... each of those 6 instructions takes only 1-2 cycles to execute. Perhaps a better question to ask then is: how many loops there need to be so that 6x {1, 2} cycles outweigh the SIMD version? (I wrote this initially as an EDIT in my response above but since you replied at about the same time, I am copying it here)

orf 3y ago

> That said, I am surprised by the results - in my mental model of how things work this does not add up. Rust assembly is ~50 instructions, roughly ~30 of them being vector (SIMD) instructions and the rest of ~20 instructions being the superset of (only) 6 instructions used in C++ assembly. I cannot see how those 6 instructions, even with the branch mispredict cost of ~15 cycles, can run ~2.5x slower than the pretty much convoluted version of the SIMD popcnt. > I cannot see how those 6 instructions, even with the branch mispredict cost of ~15 cycles, can run ~2.5x slower than the pretty much convoluted version of the SIMD popcnt. I fleshed out the benchmarks a bit, to compare `popcnt` itself and a no-op baseline: https://quick-bench.com/q/Bb36LyruJ1r8pzm8o_hjckU-xcI https://quick-bench.com/q/Bb36LyruJ1r8pzm8o_hjckU-xcI The quick-bench tool gives some nice assembly-level timing information[1] but I couldn't get it to work with my janky inline-copy-paste-assembly, and I blew past my curiosity time budget for this. You seem pretty experienced and I'd love to know more about this, so maybe if you know how to get the "popcnt_rs" extern assembly function to be inlined in the quick-bench link below we could take a look in more detail? 1. Click "assembly" and select "BM_cpp" from here: https://quick-bench.com/q/Bb36LyruJ1r8pzm8o_hjckU-xcI https://quick-bench.com/q/Bb36LyruJ1r8pzm8o_hjckU-xcI

menaerus 3y ago
There's a data dependency between those 6 instructions so out-of-order execution unit won't be able to kick in as much but still ... each of those 6 instructions takes only 1-2 cycles to execute. Perhaps a better question to ask then is: how many loops there need to be so that 6x {1, 2} cycles outweigh the SIMD version? (I wrote this initially as an EDIT in my response above but since you replied at about the same time, I am copying it here)