# Lucky Code — Your code is fast, if you're lucky

# 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()`.

```c
// 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:

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

is rewritten into a more idiomatic and compact C form:

```c
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):

```asm
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):

```asm
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.)*