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 – a quicksort with sorting networks
// SPDX-License-Identifier: MIT
// sort.h – Branchless Quicksort
// (c) [email protected]
#ifndef SORT_H
#define SORT_H
#ifndef BLQS_CMP
#define BLQS_CMP(a, b) ((a) < (b))
#endif
#include
#include
#define min(a, b) (((a) = UNROLL) for (int i = UNROLL; i–;) {
BLQS_TYPE x = *left++;
if (BLQS_CMP(x, piv)) { *lwr = x; lwr++; }
else { *sw = x; sw++; }
}
while (left <= right) {
BLQS_TYPE x = *left++;
if (BLQS_CMP(x, piv)) { *lwr = x; lwr++; }
else { *sw = x; sw++; }
}
memcpy(lwr, swbuf, (sw – swbuf) * sizeof(BLQS_TYPE));
lwr -= 1;
*outerleft = *lwr;
*lwr = piv;
return lwr;
}
static BLQS_TYPE* partition(BLQS_TYPE* left, BLQS_TYPE* right) {
BLQS_TYPE* outerleft = left;
BLQS_TYPE* pivp = left + (right – left) / 2;
BLQS_TYPE piv = *pivp;
med5(left[1],left[2],left[3],left[4],left[5]);
med5(left[11],left[12],left[13],left[14],left[15]);
med5(pivp[-2], pivp[-1], piv, pivp[1], pivp[2]);
med5(right[-14], right[-13], right[-12], right[-11], right[-10]);
med5(right[-4], right[-3], right[-2], right[-1], right[0]);
med5(left[3], left[13], piv, right[-12], right[-2]);
left += 1;
*pivp = *outerleft;
BLQS_TYPE swbuf[SWSZ];
BLQS_TYPE *rwr = right, *sw = swbuf;
BLQS_TYPE *lwr = left;
while (UNROLL < SWSZ – (sw – swbuf) && left endp + UNROLL) {
for (int i = UNROLL; i–;) {
BLQS_TYPE x = *right–;
if (BLQS_CMP(x, piv)) { *sw = x; sw++; }
else { *rwr = x; rwr–; }
}
}
}
while (right – left >= UNROLL &&
(rwr – right > UNROLL || left – lwr > UNROLL)) {
while (rwr – right > UNROLL && right – left >= UNROLL) {
for (int i = UNROLL; i–;) {
BLQS_TYPE x = *left++;
if (BLQS_CMP(x, piv)) { *lwr = x; lwr++; }
else { *rwr = x; rwr–; }
}
}
while (left – lwr > UNROLL && right – left >= UNROLL) {
for (int i = UNROLL; i–;) {
BLQS_TYPE x = *right–;
if (BLQS_CMP(x, piv)) { *lwr = x; lwr++; }
else { *rwr = x; rwr–; }
}
}
}
do {
while (rwr > right && left <= right) {
BLQS_TYPE x = *left++;
if (BLQS_CMP(x, piv)) { *lwr = x; lwr++; }
else { *rwr = x; rwr–; }
}
while (lwr < left && left <= right) {
BLQS_TYPE x = *right–;
if (BLQS_CMP(x, piv)) { *lwr = x; lwr++; }
else { *rwr = x; rwr–; }
}
} while ((lwr right) && left <= right);
while (left 11) {
BLQS_TYPE* mid = partition_small(left, right);
smallsort(left, mid – 1);
left = mid + 1;
}
sorting_network(left, right – left);
}
static void sortr(BLQS_TYPE* left, BLQS_TYPE* right) {
while (1) {
ptrdiff_t partszm1 = right – left;
if (partszm1 <= SMALLPART) break;
BLQS_TYPE* mid = partition(left, right);
if (mid – left left) sortr(left, mid – 1);
BLQS_TYPE piv = *mid;
mid += 1;
// collect duplicates
for (BLQS_TYPE* p = mid; p <= right; p++) {
if (!BLQS_CMP(piv, *p)) {
BLQS_TYPE h = *mid;
*mid = *p;
*p = h;
mid++;
}
}
left = mid;
if (right – left < SMALLPART) break;
mid = partition(left, right);
}
if (mid – left < right – mid) {
sortr(left, mid – 1);
left = mid + 1;
}
else {
sortr(mid + 1, right);
right = mid – 1;
}
}
smallsort(left, right);
}
static void sort(BLQS_TYPE* data, int len) {
if (len < 2) return;
sortr(data, data + len – 1);
}
#endif
test.c – sorting 50 million doubles
// SPDX-License-Identifier: MIT
#include
#include
#include
#define BLQS_CMP(a, b) ((a) < (b))
#define BLQS_TYPE double
#include "sort.h"
#define SIZE 50000000
double data[SIZE];
double ts(void) {
struct timeval tv;
gettimeofday(&tv, NULL);
return tv.tv_sec + tv.tv_usec / 1000000.0;
}
int main() {
double t0;
for (int i = 0; i < SIZE; i++) data[i] = rand() / 1024.0;
t0 = ts();
sort(data, SIZE);
printf("Time: %.2fs\n", ts() – t0);
}
On macOS/M1 (Clang, -O3):
Time: 4.39
C++ std::sort needs 1.33 seconds for this.
It is already micro-optimized using sorting networks and loop unrolling. Only a few cosmetic changes remain.
We rewrite this beginner‑friendly style, which explicitly shows how the pointers are moved:
if (BLQS_CMP(x, piv)) { *lwr = x; lwr++; }
else { *rwr = x; rwr–; }
into a more idiomatic and compact C form:
if (BLQS_CMP(x, piv)) *lwr++ = x;
else *rwr– = x;
sort.h – rewritten
// SPDX-License-Identifier: MIT
// blqsort.h – Branchless Quicksort
// (c) [email protected]
#ifndef SORT_H
#define SORT_H
#ifndef BLQS_CMP
#define BLQS_CMP(a, b) ((a) < (b))
#endif
#include
#include
#define min(a, b) (((a) = UNROLL) for (int i = UNROLL; i–;) {
BLQS_TYPE x = *left++;
if (BLQS_CMP(x, piv)) *lwr++ = x;
else *sw++ = x;
}
while (left <= right) {
BLQS_TYPE x = *left++;
if (BLQS_CMP(x, piv)) *lwr++ = x;
else *sw++ = x;
}
memcpy(lwr, swbuf, (sw – swbuf) * sizeof(BLQS_TYPE));
lwr -= 1;
*outerleft = *lwr;
*lwr = piv;
return lwr;
}
static BLQS_TYPE* partition(BLQS_TYPE* left, BLQS_TYPE* right) {
BLQS_TYPE* outerleft = left;
BLQS_TYPE* pivp = left + (right – left) / 2;
BLQS_TYPE piv = *pivp;
med5(left[1],left[2],left[3],left[4],left[5]);
med5(left[11],left[12],left[13],left[14],left[15]);
med5(pivp[-2], pivp[-1], piv, pivp[1], pivp[2]);
med5(right[-14], right[-13], right[-12], right[-11], right[-10]);
med5(right[-4], right[-3], right[-2], right[-1], right[0]);
med5(left[3], left[13], piv, right[-12], right[-2]);
left += 1;
*pivp = *outerleft;
BLQS_TYPE swbuf[SWSZ];
BLQS_TYPE *rwr = right, *sw = swbuf;
BLQS_TYPE *lwr = left;
while (UNROLL < SWSZ – (sw – swbuf) && left endp + UNROLL) {
for (int i = UNROLL; i–;) {
BLQS_TYPE x = *right–;
if (BLQS_CMP(x, piv)) *sw++ = x;
else *rwr– = x;
}
}
}
while (right – left >= UNROLL &&
(rwr – right > UNROLL || left – lwr > UNROLL)) {
while (rwr – right > UNROLL && right – left >= UNROLL) {
for (int i = UNROLL; i–;) {
BLQS_TYPE x = *left++;
if (BLQS_CMP(x, piv)) *lwr++ = x;
else *rwr– = x;
}
}
while (left – lwr > UNROLL && right – left >= UNROLL) {
for (int i = UNROLL; i–;) {
BLQS_TYPE x = *right–;
if (BLQS_CMP(x, piv)) *lwr++ = x;
else *rwr– = x;
}
}
}
do {
while (rwr > right && left <= right) {
BLQS_TYPE x = *left++;
if (BLQS_CMP(x, piv)) *lwr++ = x;
else *rwr– = x;
}
while (lwr < left && left <= right) {
BLQS_TYPE x = *right–;
if (BLQS_CMP(x, piv)) *lwr++ = x;
else *rwr– = x;
}
} while ((lwr right) && left <= right);
while (left 11) {
BLQS_TYPE* mid = partition_small(left, right);
smallsort(left, mid – 1);
left = mid + 1;
}
sorting_network(left, right – left);
}
static void sortr(BLQS_TYPE* left, BLQS_TYPE* right) {
while (1) {
ptrdiff_t partszm1 = right – left;
if (partszm1 <= SMALLPART) break;
BLQS_TYPE* mid = partition(left, right);
if (mid – left left) sortr(left, mid – 1);
BLQS_TYPE piv = *mid;
mid += 1;
// collect duplicates
for (BLQS_TYPE* p = mid; p <= right; p++) {
if (!BLQS_CMP(piv, *p)) {
BLQS_TYPE h = *mid;
*mid = *p;
*p = h;
mid++;
}
}
left = mid;
if (right – left < SMALLPART) break;
mid = partition(left, right);
}
if (mid – left < right – mid) {
sortr(left, mid – 1);
left = mid + 1;
}
else {
sortr(mid + 1, right);
right = mid – 1;
}
}
smallsort(left, right);
}
static void sort(BLQS_TYPE* data, int len) {
if (len < 2) return;
sortr(data, data + len – 1);
}
#endif
A quick test to make sure everything still works.
Time: 0.70
More than 6 times faster than before, and nearly twice as fast as std::sort. That’s quite something.
This “small cosmetic” change causes Clang to replace branches with csel.
With branches
; x20 = left, x9 = right, d8 = pivot
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)
; x9 = current element pointer ; x0 = left destination (grows forwards)
; x20 = right destination (grows backwards); d8 = pivot
; x8 = 8 (positive increment) ; x10 = -8 (negative increment)
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.
blqsort – Fast Quicksort with C and C++ Interface
When ‘if’ slows you down, avoid it
Interactive sorting demo
[email protected]