> On recent x64 processors, we find that it is beneficial to decode in bulk: e.g., assume that there are at least 4 set bits, decode them without checking wheth

> On recent x64 processors, we find that it is beneficial to decode in bulk: e.g., assume that there are at least 4 set bits, decode them without checking whether there are four of them. The code might look as follow: [...] I find this assertion surprising, and so I decided to test it. I wrote a naive algorithm, and found the generated assembly even more surprising. https://godbolt.org/z/ah3msM https://godbolt.org/z/ah3msM int bits(unsigned long n, char* b) { int retval = 0; while(n) { *b++ = __builtin_ctzll(n); n &= n-1; retval++; } return retval; } First of all, the business with incrementing retval is discarded entirely. It simply performs popcnt on n and returns that. Second, it performs the calculation in two sections. First it does the naive, simple loop until the remaining bits are a multiple of 8. Then it unrolls the loop into groups of 8. It unrolled the loop even with just -O2 set. In essence, the compiler does precisely what his code does, but with groups of 8 instead of 4. Clang seems to have changed behavior between versions 6 and 7; version 6 and below use the naive loop, as does GCC. Clang 7 and 8 unroll it. I'm curious if this had any effect on his results; his results for the A12 presumably are using Clang, while his linux box presumably uses GCC. There's not really a whole lot of room for improvement in that unless you go whole hog and unroll the entire thing and table jump into it: https://godbolt.org/z/qWzfHl https://godbolt.org/z/qWzfHl int bits(unsigned long n, char* b) { const int retval = __builtin_popcountll(n); switch(retval) { default: for(char i = 64; i--;) b[i] = i; return 64; case 63: b[62] = __builtin_ctzll(n); n &= n-1; case 62: b[61] = __builtin_ctzll(n); n &= n-1; case 61: b[60] = __builtin_ctzll(n); n &= n-1; // etc case 2: b[1] = __builtin_ctzll(n); n &= n-1; case 1: b[0] = __builtin_ctzll(n); case 0: return retval; } } Which has its own macabre beauty to it. Interesting distinction between Intel CPUs and AMD: the blsr instruction has a latency of 1 on Intel, and 2 on AMD, while tzcnt has a latency of 3 on Intel, and 2 on AMD. But the performance is limited by the blsr instruction, so Intel processes 1 bit per cycle, but AMD can only manage 1 bit per two cycles.