3 ms·

> 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

by 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

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)