3 ms·
Okay, wait. Every modern CPU has a popcount instruction, so any hand-coded implementation would use that, meaning the compiler output is actually pretty bad in
by jblow 9y ago
Okay, wait. Every modern CPU has a popcount instruction, so any hand-coded implementation would use that, meaning the compiler output is actually pretty bad in an absolute sense.
But if you find popcount too "magical", the commonly-known fast way to count bits is via masking, shifts and adds, so that you do it in log(n) steps. Which also would perform much better than this solution.
So what you're really saying is "the compiler managed to make a pretty efficient representation of the naive solution" which is fine but it does not mean your code is fast.
- kbenson 9y ago> Okay, wait. Every modern CPU has a popcount instruction What do you consider a "modern CPU"? Atom chips sold less than a decade ago didn't support popcnt. AMD shipped some C-series chips without support for it as recently as 2012. The low-end chips were likely to be sold later without refreshes to newer features in some cases, and those are also likely the ones to be repurposed for small and cheap x86 devices later. I wouldn't want the default compilation settings without specifying CPU extensions to use an extension that might not exist on my target platform.
- jblow 9y agoThis is why you have a fallback to a generic version.
- Lerc 9y agoAs I stated in another reply. I don't actually want to count bits at all. Counting is just the simplest thing I could do with the bits in the test case. Turning a stream of bytes into a stream of bits can be quite useful.
- jblow 9y agoBut if you are reading a stream of bits, you don't want to read one bit at a time either, because that is pathologically slow. You want to read n buts at a time (where n varies each call, probably) at which point you're doing a very standard mask-and-shift with no magic...
- deleted 9y ago[deleted]