Hacker News new | ask | show | jobs
by dmitrygr 582 days ago
Your compiler will know the best way to popcount, that is the point of that builtin. It'll use the best method - sometimes this one. GCC does this, MSVC does this, clang does this, i think even rust has some way to do it (EDIT: it does: count_ones()). On archs which lack POPCNT, it will use this method or another, based on knowing the target. On x86 this approach is OK as is. On arm64, for example, it will be suboptimal due to all the literals needed. On armv6m, this method is bad and table lookups are faster.
2 comments
SkiFire13 582 days ago
Note that by default rustc targets x86-64-v1 when compiling for x86-64, and that lacks the popcount instruction. You need to change the target_cpu to at least x86-64-v2 or enable the popcount target_feature. This means that even if your cpu is relatively new and you intend to run your code on relatively new cpus, rustc will still generate older and slower code for count_ones() using bitshifts and masks. That said, I don't see the point in writing them manually if the compiler can generate them for you.
link
vlovich123 582 days ago
It's not unreasonable to think that Rust will change the minimum version and you should always override the target cpu anyway for C++-like toolchains when building production binaries (`-Ctarget-cpu` for rust, `march=` for clang/gcc).
link
Findecanor 582 days ago
I once wrote that algorithm, divided into single lines, intending each line to be a single 64-bit ARM instruction. The compiler did idiom detection, transforming it to "builtin popcnt" and (because 64-bit ARMv8.0 lacks a POPCNT instruction) back to the same algorithm. Only that the emitted code was one instruction larger than my code.

64-bit ARM's actually has a very peculiar encoding of immediates to arithmetic instructions. It supports only recurring bit patterns such as used by this algorithm. For example "add x2, x3, #3333333333333333" is encoded as one four-byte instruction.

link
stassats 582 days ago
> because 64-bit ARMv8.0 lacks a POPCNT instruction

It does have this: https://developer.arm.com/documentation/ddi0596/2021-09/SIMD...

And GCC happily uses it https://godbolt.org/z/dTW46f9Kf

link