3 ms·

Wow, I spent way too long on this. Instruction counts are not everything. The rust assembly is completely branchless, and on my M2 MacBook I'm benching it at ~

by orf 3y ago

Wow, I spent way too long on this. Instruction counts are not everything. The rust assembly is completely branchless, and on my M2 MacBook I'm benching it at ~2ns per call vs ~10ns per call with the equivalent C++ code (running this: https://godbolt.org/z/nTanvfs76 https://godbolt.org/z/nTanvfs76) ----------------------------------------------------- Benchmark Time CPU Iterations ----------------------------------------------------- BM_cpp 10.1 ns 10.1 ns 69503053 BM_rs 1.74 ns 1.72 ns 393022172 benchmark code: https://gist.github.com/orf/7ce6ef09bde943f788d963e05c94c049 https://gist.github.com/orf/7ce6ef09bde943f788d963e05c94c049 LLVM IR for the benchmark: https://godbolt.org/z/8PaoK4sYz https://godbolt.org/z/8PaoK4sYz These results match a criterion benchmark: https://gist.github.com/orf/6dc9d6dbfdcd0df464c1c0a7274f6286 https://gist.github.com/orf/6dc9d6dbfdcd0df464c1c0a7274f6286 I could be doing something horribly wrong here - this was a nice intro into a few different things I haven't used before. But I ended up taking the rust function and outputting the LLVM IR for it, then compiling and linking that with the C++ benchmark. And it worked, after I realised how to get the optimizer to stop removing everything. Similar results on Intel can be seen here: https://quick-bench.com/q/RxcWefXX5jo77NM-eK8u36W6ohk https://quick-bench.com/q/RxcWefXX5jo77NM-eK8u36W6ohk

menaerus 3y ago
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)

by orf 3y ago

menaerus 3y ago

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)