pub fn popcnt(mut x: u32) -> u32 {
x.count_ones()
}
example::popcnt:
popcnt eax, edi
ret
32 bits is not large enough, and the code Rust produces is indeed comically bad.
[1]: https://github.com/llvm/llvm-project/blob/08a6968127f04a40d7... [2]: https://llvm.org/docs/LangRef.html#llvm-ctpop-intrinsic
It's dramatically different, C++ compiles down to 10 or so instructions even without the vectorization turned on.
Rust OTOH compiles down to 188 or 129 instructions with the vectorization. This is pretty bad.
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)
-----------------------------------------------------
Benchmark Time CPU Iterations
-----------------------------------------------------
BM_cpp 10.1 ns 10.1 ns 69503053
BM_rs 1.74 ns 1.72 ns 393022172
LLVM IR for the benchmark: https://godbolt.org/z/8PaoK4sYz
These results match a criterion benchmark: 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
.L4:
mov edx, edi
and edx, 1
cmp edx, 1
sbb eax, -1
shr edi
jne .L4
ret
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-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.
> 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
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
(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)
Not relevant to this example, which is `popcount`ing only a single number, but AVX512 did also introduce SIMD popcount instructions for getting many inputs at a time. Also true for other useful bit-funs like leading or trailing zeros. So if you're using zmm registers, you can do way better than that godbolt example.