Compiler codegen luck — a cosmetic edit that ran 6x faster

Christof Kaser was tuning a branchless quicksort in C and hit a case where two logically identical versions of the same hot loop ran more than six times apart. Sorting 50 million doubles on an M1 with Clang at -O3 took 4.39 seconds one way and 0.70 seconds the other. The faster version also beat std::sort (1.33s) by almost 2x. The algorithm, the data, and the compiler flags were all the same. The only change was how the partition loop was written.

The change

The partition step walks the array and sends each element to one of two write pointers depending on how it compares to the pivot. The explicit form spells out the pointer bump on its own statement:

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

The idiomatic form folds the store and the increment together:

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

Same effect, same semantics. But Clang compiles them differently. The compact form becomes a branchless loop built on csel on AArch64 (cmov on x86): the comparison feeds a conditional select that picks the destination pointer and the increment, then does one unconditional store. The explicit form keeps a real conditional branch around the store. GCC ignores the distinction and emits the slower branch version both ways.

Why the wording matters to the compiler

The mechanism was pinned down in the HN thread. In the one-statement version, the last operation in each branch of the LLVM IR is the store. LLVM's SimplifyCFG pass looks for stores that are identical except for one operand, hoists them into a shared successor block, and replaces the choice with a select instruction — which later lowers to a conditional move. In the two-statement version, the last operation in each branch is the pointer arithmetic, not the store. The two pointers differ by two operands (different base pointers, one incremented and one decremented), so SimplifyCFG bails out immediately and never reaches the stores. Inspecting the pipeline in Compiler Explorer shows the same split: after conversion to SSA the fast version computes the pointer increment before the store, the slow version does it the other way, and that ordering is enough to defeat the pattern match. Nothing in the source tells you which side of that line you land on.

Why branchless wins here specifically

A conditional move is not automatically faster than a branch. It is faster only when the branch is hard to predict. Quicksort partitioning on random data is close to the worst case for a branch predictor: roughly half the elements go each way with no pattern, so the predictor is wrong about half the time and every misprediction flushes the pipeline. csel/cmov has no branch to mispredict — it always does the same work — so it wins when the data is unpredictable and loses when the branch would have been predictable. The compiler cannot know the data distribution at compile time, so it guesses. On this workload the branchless guess happens to be right, which is where the "luck" comes from: the fast path exists only because a cosmetic edit nudged the compiler into a pattern that suited the runtime data. See conditional-move for the general tradeoff. Clang exposes __builtin_unpredictable() to hint the branch is a coin flip, but that only helps if you already know to reach for it.

The wider point

The takeaways people drew from the thread are the useful part. Compiler optimizers recognize specific IR shapes, so writing idiomatic code raises the odds a pass fires — but the matching is brittle and undocumented, and semantically identical code can land on either side of it. For code that has to be fast, memory locality, vectorization, and branch behavior usually matter more than algorithmic complexity, and none of them are visible in the source. The recurring advice: measure, read the generated assembly (Compiler Explorer, perf), and don't trust superstition about what "should" be fast.

This sits alongside other cases in this vault where two builds of the same code diverge for reasons the source never shows: linux-7-postgres-regression, where dropping a kernel preemption mode let a PostgreSQL spinlock holder get preempted mid-page-fault and halved throughput, and huge-pages, where page size alone changes fault count and TLB pressure by orders of magnitude. In each, the performance lives below the code you wrote.