Lucky Code

Your code is fast - if you're lucky

Recently, while I was working on an optimized Quicksort implementation, I came across a rather interesting quirk. Modern compilers (especially Clang) optimize loops using fast, branch-free instructions - provided you use the right programming style.

sort.h is a branchless quicksort using sorting networks and loop unrolling (MIT, christof.kaser@gmail.com). The hot loop lives in the partition / partition_small functions. test.c sorts 50 million doubles seeded from rand().

// test.c
#define BLQS_CMP(a, b) ((a) < (b))
#define BLQS_TYPE double
#include "sort.h"
#define SIZE 50000000
double data[SIZE];
int main() {
    for (int i = 0; i < SIZE; i++) data[i] = rand() / 1024.0;
    double t0 = ts();
    sort(data, SIZE);
    printf("Time: %.2fs\n", ts() - t0);
}

On macOS/M1 (Clang, -O3): Time: 4.39s. C++ std::sort needs 1.33 seconds for the same input.

A few cosmetic changes

The code is already micro-optimized using sorting networks and loop unrolling. Only a few cosmetic changes remain. The beginner-friendly style, which explicitly shows how the pointers are moved:

if (BLQS_CMP(x, piv)) { *lwr = x; lwr++; }
else { *rwr = x; rwr--; }

is rewritten into a more idiomatic and compact C form:

if (BLQS_CMP(x, piv)) *lwr++ = x;
else *rwr-- = x;

After this change: Time: 0.70s. More than 6 times faster than before, and nearly twice as fast as std::sort.

But what actually happened?

This "small cosmetic" change causes Clang to replace branches with csel.

With branches (AArch64):

loop:
    ldr  d0, [x12], #8
    fcmp d0, d8         ; compare value against pivot
    b.pl ge_case
    str  d0, [x20], #8  ; left++
    b    next
ge_case:
    str  d0, [x9], #-8  ; right--
next:
    cmp  x12, x_end
    b.lt loop

Fast with csel (branchless):

loop:
    ldr d0, [x9], #8
    fcmp  d0, d8            ; compare value against pivot
    csel x11, x0, x20, mi   ; target is left (x0) or right (x20)
    str d0, [x11]           ; store value to the selected destination
    csel  x12, x8, xzr, mi  ; left_step is 8 or 0
    csel  x13, xzr, x10, mi ; right_step is 0 or -8
    add   x0, x0, x12       ; left += left_step
    add   x20, x20, x13     ; right += right_step
    b.ls  loop

On x86, Clang behaves similarly: with the compact if, it generates branchless code using cmov (conditional move). GCC does not exhibit this quirk (different code generation for logically equivalent source). It consistently generates the slower branch-based version.

Links

• blqsort - Fast Quicksort with C and C++ Interface
• "When 'if' slows you down, avoid it"
• Interactive sorting demo

(Source note: the article reproduces the full ~200-line sort.h twice, before and after the change. Only the differing hot-loop lines are transcribed above; the sorting-network macros and partition scaffolding are identical between the two versions.)