11–20 of 38 posts
[1] https://github.com/scala-js/scala-js/blob/v1.3.1/linker-priv...
[2] https://lampwww.epfl.ch/~doeraene/thesis/doeraene-thesis-201...
At the moment, the only ISO Standard way to say "popcount" is in C++, with e.g.
std::bitset(x).count()
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.
My favorite thing about these is how they come full circle - programmers find convoluted ways to outsmart the compiler in some primitive operation, but then CPU manufacturers add dedicated instructions for those operations, and eventually the compilers outsmart the programmer by deleting their smartass method and emitting a single instruction instead https://godbolt.org/z/nPdrcz
Compilers failing to generate POPCNT cause sometimes 10x slowdowns in key operations.
I once had to count the number of set bits (the Hamming weight) for an assignment. It had to be done in under 40 bitwise ops, without loops and with constants of up to 8 bits. The naive approach took way too many ops! I was stumped until I found the linked page, in particular 'Counting bits set, in parallel'[1]. Parallelism at the bit level?! That is when I realized low level programming was completely badass. [1]: h…
My favorite thing about these is how they come full circle - programmers find convoluted ways to outsmart the compiler in some primitive operation, but then CPU manufacturers add dedicated instructions for those operations, and eventually the compilers outsmart the programmer by deleting their smartass method and emitting a single instruction instead https://godbolt.org/z/nPdrcz
This of course refers to the POPCNT instruction, that is still quite tricky to get compilers to generate reliably, and which RISC-V specifications and all implementations to date mysteriously lack. Compilers failing to generate POPCNT cause sometimes 10x slowdowns in key operations.
Portability is an issue though, that works on GCC/Clang but you need a different intrinsic for MSVC
At my last job interview I had to implement popcount and explain how to optimise it (amongst other things). I was able to jot down a naïve implementation and the obvious optimisation based on a lookup tables. I only vaguely remembered the Bit Twiddling treatment of the subject but, with a bit of nudging from the interviewer, I managed to implement and explain the variant that runs in O(set bits) (“Brian Kernighan's w…
At my last job interview I had to implement popcount and explain how to optimise it (amongst other things). I was able to jot down a naïve implementation and the obvious optimisation based on a lookup tables. I only vaguely remembered the Bit Twiddling treatment of the subject but, with a bit of nudging from the interviewer, I managed to implement and explain the variant that runs in O(set bits) (“Brian Kernighan's w…
At my last job interview I had to implement popcount and explain how to optimise it (amongst other things). I was able to jot down a naïve implementation and the obvious optimisation based on a lookup tables. I only vaguely remembered the Bit Twiddling treatment of the subject but, with a bit of nudging from the interviewer, I managed to implement and explain the variant that runs in O(set bits) (“Brian Kernighan's w…
I’ve had that question twice in google phone screen interviews, and iirc, the best answer has changed from the hash table thing to just use the hardware instruction.
Nobody should ask this anyway, this has become the fizzbuzz type of question.