Bitset Decoding on Apple’s A12
&gt; 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: [...]<p>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. <a href="https:&#x2F;&#x2F;godbolt.org&#x2F;z&#x2F;ah3msM" rel="nofollow">https:&#x2F;&#x2F;godbolt.org&#x2F;z&#x2F;ah3msM</a><p><pre><code>    int bits(unsigned long n, char* b) {
        int retval = 0;
        while(n) {
            *b++ = __builtin_ctzll(n);
            n &amp;= n-1;
            retval++;
        }
        return retval;
    }
</code></pre>
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.<p>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&#x27;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.<p>There&#x27;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: <a href="https:&#x2F;&#x2F;godbolt.org&#x2F;z&#x2F;qWzfHl" rel="nofollow">https:&#x2F;&#x2F;godbolt.org&#x2F;z&#x2F;qWzfHl</a><p><pre><code>    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 &amp;= n-1;
            case 62: b[61] = __builtin_ctzll(n); n &amp;= n-1;
            case 61: b[60] = __builtin_ctzll(n); n &amp;= n-1;
            &#x2F;&#x2F; etc
            case 2: b[1] = __builtin_ctzll(n); n &amp;= n-1;
            case 1: b[0] = __builtin_ctzll(n);
            case 0: return retval;
        }
    }
</code></pre>
Which has its own macabre beauty to it.<p>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.