2 ms·
This list is super-great, except: all modern targets[0] (and many non-modern, including Alpha, Cray, CDC, Stretch) have the POPCOUNT instruction, which does a k
by ncmncm 6y ago
This list is super-great, except: all modern targets[0] (and many non-modern, including Alpha, Cray, CDC, Stretch) have the POPCOUNT instruction, which does a key operation underlying a large portion of the target operations much faster than presented. It provides an order-of-magnitude speedup in numerous algorithms. The list should have a comprehensive treatment.
At the moment, the only ISO Standard way to say "popcount" is in C++, with e.g.
std::bitset<64>(x).count()
But even this is insufficient on MSVC, which targets pre-2002 arm64, which lacked it; and on gcc and clang on amd64, similarly, absent a -fpopcnt or -march=native or related option (which there are numerous other reasons to use).
Given -march=native or =core2 or various other means, optimizers will happily rewrite the Kernighan loop into a straight-up POPCNT instruction. Anyway, all compilers provide it as a non-standard, therefore variously-spelled, intrinsic, but (except on MSVC) only actually produce it if the "-march=" or related commad-line option enables that.
Historically, it is common for instruction sets to start out lacking the instruction, and then getting it in subsequent releases because of customer demand. Also historically, a key such customer has frequently been the US NSA. Thus, initial and64, alpha, POWER, and SPARC lacked it, but soon got it. x86 ("ia32") is perhaps the principal laggard. When a feature is added, at great expense, to a subsequent ISA revision, that says a lot for its importance.
[0] All except RISC-V, to date. Some would say this makes RISC-V non-modern. It appears in the (still) unratified B extension, which (therefore) nobody implements.