4 ms·

Interesting article! Right at the start, the first example of a non-vectorized popcnt implementation is said to produce “comically bad code, frankly”, but in re

• saagarjha 3y ago
  I mean ideally you’d probably want this to be lowered to a popcnt instruction.
  • celrod 3y ago
    Yes, just because you see SIMD instructions doesn't mean the code is fast. You need the correct instructions. 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.
• eesmith 3y ago
  The following should produce equivalent output: pub fn popcnt(mut x: u32) -> u32 { x.count_ones() } which gets compiled to: example::popcnt: popcnt eax, edi ret For large bit vectors, an AVX2 implementation can outperform POPCNT. See "Faster Population Counts Using AVX2 Instructions" at https://academic.oup.com/comjnl/article/61/1/111/3852071 https://academic.oup.com/comjnl/article/61/1/111/3852071 32 bits is not large enough, and the code Rust produces is indeed comically bad.
  • 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
  • rwaksmunski 3y ago
    TIL: https://doc.rust-lang.org/std/primitive.usize.html#method.count_ones https://doc.rust-lang.org/std/primitive.usize.html#method.co...
• the8472 3y ago
  autovectorization is hit and miss. I recently wrote this which has to count the bits in a result mask of vector operations and it turns into popcnt just fine. https://godbolt.org/z/zT9Whcnco https://godbolt.org/z/zT9Whcnco