Sufficiently Smart

The translation of higher-level software logic into the language understood by a computer's processor is done by compilers. With knowledge of the quirks and capabilities of the CPU architecture being used, a compiler can recognize patterns and idioms in the input program and emit low-level instructions to play to the strengths of the hardware.

The phrase "a sufficiently smart compiler" is often used to express the idea that the high-level software instructions needn't take into account the details of the underlying hardware, but rather focus solely on describing logic. Letting the human make the abstract decisions and a tireless compiler turn those abstractions into high-performing, concrete machine code will enable each party to use their skills to the greatest effect.

Whether or not a given compiler measures up to "sufficiently smart", or if any compiler meets this standard, is a subject of debate. Software authors generally do need to keep performance in mind to some degree, but the authors of these tools spend immense effort into ensuring their compilers emit the highest-performing machine code possible.

While comparing various implementations of the population count operation in my previous post, I encountered a result which I first assumed was an error in my methods. When instructed to use more aggressive optimization settings, the execution gap between a thoughtful, but still high-level implementation and a version using the purpose-built, single hardware popcnt instruction narrowed very quickly.

This is the code in question being compiled, the "better" pure-software version of the population count operation:

int popcount(uint64_t n) {
    int count = 0;
    while (n > 0) {
        n &= (n - 1);
        count++;
    }
    return count;
}

Note that I'm not using the __builtin_popcount directive (or variants), but spelling the entire method out as if I were writing a textbook.

I performed the following experiment with GCC 14.2.0 on a virtual core claiming to be an Intel Xeon of the Broadwell vintage.

• The code
• A Makefile to build the two versions with make all.

Here's the assembly when compiled without enabling any optimizations:

<+0>:     push   %rbp
<+1>:     mov    %rsp,%rbp
<+4>:     mov    %rdi,-0x18(%rbp)
<+8>:     movl   $0x0,-0x4(%rbp)
<+15>:    jmp    0x1197 <popcount+33>
<+17>:    mov    -0x18(%rbp),%rax
<+21>:    sub    $0x1,%rax
<+25>:    and    %rax,-0x18(%rbp)
<+29>:    addl   $0x1,-0x4(%rbp)
<+33>:    cmpq   $0x0,-0x18(%rbp)
<+38>:    jne    0x1187 <popcount+17>
<+40>:    mov    -0x4(%rbp),%eax
<+43>:    pop    %rbp
<+44>:    ret

A perfectly reasonable translation of the C source, you can see the same while-looping structure with the return to +17 at +38.

Here's the same method compiled with -O3:

<+0>:     xor    %eax,%eax
<+2>:     popcnt %rdi,%rax
<+7>:     ret

Here the code is collapsed completely into three steps:

• Set a register to zero, showing the CPU that there's no possible state left in this register to depend on.
• Call the CPU popcnt instruction and store the result in our register. As %eax refers to the 32-bit, lower half of 64-bit %rax, we are safely dropping our result in the same place we just cleared out.
• Return our result.

With the more aggressive settings, the compiler chose to replace the entirety of the method with the single hardware popcnt call. As it turns out, GCC (and many other modern compilers) recognize a few varieties of population count, even the non-obvious SWAR technique I also used in the previous post.

Sufficiently smart, indeed!