4 ms·

Would the equivalent c++ code run through LLVM generate a different output?

by orf 3y ago

asb 3y ago
LLVM has a LoopIdiomRecognize pass which will, amongst other patterns, try to detect a loop implementing popcount [1] and convert it to the llvm.ctpop.* intrinsic [2]. I've not looked at why it's not matching this loop, but the sibling comment suggesting to just use `.count_ones` seems like the right answer for Rust. In C or C++ I'd strongly recommend using `__builtin_popcount` (provided by both Clang and GCC). [1]: https://github.com/llvm/llvm-project/blob/08a6968127f04a40d767bf3fe296bc36667c89eb/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp#L1557 https://github.com/llvm/llvm-project/blob/08a6968127f04a40d7... [2]: https://llvm.org/docs/LangRef.html#llvm-ctpop-intrinsic https://llvm.org/docs/LangRef.html#llvm-ctpop-intrinsic
- celrod 3y ago
  `std::popcount` was added to the stl in C++20 https://en.cppreference.com/w/cpp/numeric/popcount https://en.cppreference.com/w/cpp/numeric/popcount
  - asb 3y ago
    Thanks for pointing that out - definitely a better choice for C++.
menaerus 3y ago
That's easy to check, and the answer is yes it would. See https://godbolt.org/z/eqseqxhca https://godbolt.org/z/eqseqxhca 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.
- 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.

Would the equivalent c++ code run through LLVM generate a different output?

by orf 3y ago

Would the equivalent c++ code run through LLVM generate a different output?

asb 3y ago

LLVM has a LoopIdiomRecognize pass which will, amongst other patterns, try to detect a loop implementing popcount [1] and convert it to the llvm.ctpop.* intrinsic [2]. I've not looked at why it's not matching this loop, but the sibling comment suggesting to just use `.count_ones` seems like the right answer for Rust. In C or C++ I'd strongly recommend using `__builtin_popcount` (provided by both Clang and GCC). [1]: https://github.com/llvm/llvm-project/blob/08a6968127f04a40d767bf3fe296bc36667c89eb/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp#L1557 https://github.com/llvm/llvm-project/blob/08a6968127f04a40d7... [2]: https://llvm.org/docs/LangRef.html#llvm-ctpop-intrinsic https://llvm.org/docs/LangRef.html#llvm-ctpop-intrinsic

celrod 3y ago
`std::popcount` was added to the stl in C++20 https://en.cppreference.com/w/cpp/numeric/popcount https://en.cppreference.com/w/cpp/numeric/popcount
- asb 3y ago
  Thanks for pointing that out - definitely a better choice for C++.

menaerus 3y ago

That's easy to check, and the answer is yes it would. See https://godbolt.org/z/eqseqxhca https://godbolt.org/z/eqseqxhca 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.

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.