Your code is fast – if you're lucky

# Lucky Code Source: [https://tiki.li/blog/lucky_code.html](https://tiki.li/blog/lucky_code.html) ## 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 \- 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 <stddef.h> #include <string.h> #define min(a, b) (((a) < (b)) ? (a) : (b)) #define SMALLPART 1024 #define SWSZ 512 #define UNROLL 16 #define sort2(a, b) do { \ unsigned m = BLQS_CMP(a, b); \ BLQS_TYPE x = a; \ a = m ? a : b; \ b = m ? b : x; \ } while(0) #define sort3(a, b, c) do { \ sort2(a, b); sort2(b, c); sort2(a, b); \ } while(0) #define sort4(a, b, c, d) do { \ sort2(a, b); sort2(c, d); sort2(a, c); \ sort2(b, d); sort2(b, c); \ } while(0) #define sort5(a, b, c, d, e) do { \ sort2(b, c); sort2(d, e); sort2(b, d); \ sort2(a, c); sort2(a, d); sort2(c, e); \ sort2(a, b); sort2(c, d); sort2(b, c); \ } while(0) #define sort6(a, b, c, d, e, f) do { \ sort2(a, b); sort2(c, d); sort2(e, f); \ sort2(a, c); sort2(b, d); sort2(e, f); \ sort2(a, e); sort2(b, f); sort2(c, e); \ sort2(d, f); sort2(b, c); sort2(d, e); \ sort2(c, d); \ } while(0) #define sort7(a, b, c, d, e, f, g) do { \ sort2(a, b); sort2(c, d); sort2(a, c); \ sort2(b, d); sort2(b, c); sort2(e, f); \ sort2(e, g); sort2(f, g); sort2(a, e); \ sort2(b, f); sort2(c, g); sort2(b, e); \ sort2(d, g); sort2(c, e); sort2(b, c); \ sort2(d, f); sort2(d, e); \ } while(0) #define sort8(a,b,c,d,e,f,g,h) do { \ sort2(a,b); sort2(c,d); sort2(e,f); sort2(g,h); \ sort2(a,c); sort2(b,d); sort2(e,g); sort2(f,h); \ sort2(b,c); sort2(f,g); \ sort2(a,e); sort2(b,f); sort2(c,g); sort2(d,h); \ sort2(c,e); sort2(d,f); \ sort2(b,c); sort2(d,e); sort2(f,g); \ } while (0) #define sort9(a,b,c,d,e,f,g,h,i) do { \ sort2(a,d); sort2(b,h); sort2(c,f); sort2(e,i); \ sort2(a,h); sort2(c,e); sort2(d,i); sort2(f,g); \ sort2(a,c); sort2(b,d); sort2(e,f); sort2(h,i); \ sort2(b,e); sort2(d,g); sort2(f,h); \ sort2(a,b); sort2(c,e); sort2(d,f); sort2(g,i); \ sort2(c,d); sort2(e,f); sort2(g,h); \ sort2(b,c); sort2(d,e); sort2(f,g); \ } while (0) #define sort10(a,b,c,d,e,f,g,h,i,j) do { \ sort2(a,i); sort2(b,j); sort2(c,h); sort2(d,f); sort2(e,g); \ sort2(a,c); sort2(b,e); sort2(f,i); sort2(h,j); \ sort2(a,d); sort2(c,e); sort2(f,h); sort2(g,j); \ sort2(a,b); sort2(d,g); sort2(i,j); \ sort2(b,f); sort2(c,d); sort2(e,i); sort2(g,h); \ sort2(b,c); sort2(d,f); sort2(e,g); sort2(h,i); \ sort2(c,d); sort2(e,f); sort2(g,h); \ sort2(d,e); sort2(f,g); \ } while (0) #define sort11(a,b,c,d,e,f,g,h,i,j,k) do { \ sort2(a,j); sort2(b,g); sort2(c,e); sort2(d,h); sort2(f,i); \ sort2(a,b); sort2(d,f); sort2(e,k); sort2(g,j); sort2(h,i); \ sort2(b,d); sort2(c,f); sort2(e,h); sort2(i,k); \ sort2(a,e); sort2(b,c); sort2(d,h); sort2(f,j); sort2(g,i); \ sort2(a,b); sort2(c,g); sort2(e,f); sort2(h,i); sort2(j,k); \ sort2(c,e); sort2(d,g); sort2(f,h); sort2(i,j); \ sort2(b,c); sort2(d,e); sort2(f,g); sort2(h,i); \ sort2(c,d); sort2(e,f); sort2(g,h); \ } while (0) #define sort12(a,b,c,d,e,f,g,h,i,j,k,l) do { \ sort2(a,i); sort2(b,h); sort2(c,g); sort2(d,l); sort2(e,k); sort2(f,j); \ sort2(a,c); sort2(b,e); sort2(d,f); sort2(g,i); sort2(h,k); sort2(j,l); \ sort2(a,b); sort2(c,j); sort2(e,h); sort2(f,g); sort2(k,l); \ sort2(b,d); sort2(c,h); sort2(e,j); sort2(i,k); \ sort2(a,b); sort2(c,d); sort2(e,f); sort2(g,h); sort2(i,j); sort2(k,l); \ sort2(b,c); sort2(d,f); sort2(g,i); sort2(j,k); \ sort2(c,e); sort2(d,g); sort2(f,i); sort2(h,j); \ sort2(b,c); sort2(d,e); sort2(f,g); sort2(h,i); sort2(j,k); \ } while (0) static void sorting_network(BLQS_TYPE* l, int partszm1_min_1) { switch (partszm1_min_1) { case 0: break; case 1: sort2(l[0],l[1]); break; case 2: sort3(l[0],l[1],l[2]); break; case 3: sort4(l[0],l[1],l[2],l[3]); break; case 4: sort5(l[0],l[1],l[2],l[3],l[4]); break; case 5: sort6(l[0],l[1],l[2],l[3],l[4],l[5]); break; case 6: sort7(l[0],l[1],l[2],l[3],l[4],l[5],l[6]); break; case 7: sort8(l[0],l[1],l[2],l[3],l[4],l[5],l[6],l[7]); break; case 8: sort9(l[0],l[1],l[2],l[3],l[4],l[5],l[6],l[7],l[8]); break; case 9: sort10(l[0],l[1],l[2],l[3],l[4],l[5],l[6],l[7],l[8],l[9]); break; case 10: sort11(l[0],l[1],l[2],l[3],l[4],l[5],l[6],l[7],l[8],l[9],l[10]); break; case 11: sort12(l[0],l[1],l[2],l[3],l[4],l[5],l[6],l[7],l[8],l[9],l[10],l[11]); break; } } #define med5(a,b,c,d,e) do { \ sort2(a,b); sort2(c,d); sort2(a,c); \ sort2(b,d); sort2(b,c); sort2(c,e); \ sort2(b,c); \ } while(0) static BLQS_TYPE* partition_small(BLQS_TYPE* left, BLQS_TYPE* right) { BLQS_TYPE* outerleft = left; BLQS_TYPE* pivp = left + 6; BLQS_TYPE piv = *pivp; BLQS_TYPE l1 = left[1],l2 = left[2]; BLQS_TYPE r1 = right[-1], r0 = *right; med5(l1, l2, piv, r1, r0); left[1] = l1; left[2] = l2; right[-1] = r1; *right = r0; left += 3; right -= 2; *pivp = *outerleft; BLQS_TYPE swbuf[SMALLPART]; BLQS_TYPE* sw = swbuf; BLQS_TYPE* lwr = left; while (right - left >= 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 < right - UNROLL) { ptrdiff_t avail = min(right - left, SWSZ - (sw - swbuf)); BLQS_TYPE* endp = right - avail; while (right > 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 < left||rwr > right) && left <= right); while (left <= right && !BLQS_CMP(*right, piv)) { right--; rwr--; } memcpy(lwr, swbuf, (sw - swbuf) * sizeof(BLQS_TYPE)); *outerleft = *rwr; *rwr = piv; return rwr; } static void smallsort(BLQS_TYPE* left, BLQS_TYPE* right) { while (right - 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 < partszm1 / 16) { if (mid > 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 <stdio.h> #include <stdlib.h> #include <time.h> #include <sys/time.h> #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\.### A few cosmetic changes 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 <stddef.h> #include <string.h> #define min(a, b) (((a) < (b)) ? (a) : (b)) #define SMALLPART 2048 #define SWSZ 512 #define UNROLL 16 #define sort2(a, b) do { \ unsigned m = BLQS_CMP(a, b); \ BLQS_TYPE x = a; \ a = m ? a : b; \ b = m ? b : x; \ } while(0) #define sort3(a, b, c) do { \ sort2(a, b); sort2(b, c); sort2(a, b); \ } while(0) #define sort4(a, b, c, d) do { \ sort2(a, b); sort2(c, d); sort2(a, c); \ sort2(b, d); sort2(b, c); \ } while(0) #define sort5(a, b, c, d, e) do { \ sort2(b, c); sort2(d, e); sort2(b, d); \ sort2(a, c); sort2(a, d); sort2(c, e); \ sort2(a, b); sort2(c, d); sort2(b, c); \ } while(0) #define sort6(a, b, c, d, e, f) do { \ sort2(a, b); sort2(c, d); sort2(e, f); \ sort2(a, c); sort2(b, d); sort2(e, f); \ sort2(a, e); sort2(b, f); sort2(c, e); \ sort2(d, f); sort2(b, c); sort2(d, e); \ sort2(c, d); \ } while(0) #define sort7(a, b, c, d, e, f, g) do { \ sort2(a, b); sort2(c, d); sort2(a, c); \ sort2(b, d); sort2(b, c); sort2(e, f); \ sort2(e, g); sort2(f, g); sort2(a, e); \ sort2(b, f); sort2(c, g); sort2(b, e); \ sort2(d, g); sort2(c, e); sort2(b, c); \ sort2(d, f); sort2(d, e); \ } while(0) #define sort8(a,b,c,d,e,f,g,h) do { \ sort2(a,b); sort2(c,d); sort2(e,f); sort2(g,h); \ sort2(a,c); sort2(b,d); sort2(e,g); sort2(f,h); \ sort2(b,c); sort2(f,g); \ sort2(a,e); sort2(b,f); sort2(c,g); sort2(d,h); \ sort2(c,e); sort2(d,f); \ sort2(b,c); sort2(d,e); sort2(f,g); \ } while (0) #define sort9(a,b,c,d,e,f,g,h,i) do { \ sort2(a,d); sort2(b,h); sort2(c,f); sort2(e,i); \ sort2(a,h); sort2(c,e); sort2(d,i); sort2(f,g); \ sort2(a,c); sort2(b,d); sort2(e,f); sort2(h,i); \ sort2(b,e); sort2(d,g); sort2(f,h); \ sort2(a,b); sort2(c,e); sort2(d,f); sort2(g,i); \ sort2(c,d); sort2(e,f); sort2(g,h); \ sort2(b,c); sort2(d,e); sort2(f,g); \ } while (0) #define sort10(a,b,c,d,e,f,g,h,i,j) do { \ sort2(a,i); sort2(b,j); sort2(c,h); sort2(d,f); sort2(e,g); \ sort2(a,c); sort2(b,e); sort2(f,i); sort2(h,j); \ sort2(a,d); sort2(c,e); sort2(f,h); sort2(g,j); \ sort2(a,b); sort2(d,g); sort2(i,j); \ sort2(b,f); sort2(c,d); sort2(e,i); sort2(g,h); \ sort2(b,c); sort2(d,f); sort2(e,g); sort2(h,i); \ sort2(c,d); sort2(e,f); sort2(g,h); \ sort2(d,e); sort2(f,g); \ } while (0) #define sort11(a,b,c,d,e,f,g,h,i,j,k) do { \ sort2(a,j); sort2(b,g); sort2(c,e); sort2(d,h); sort2(f,i); \ sort2(a,b); sort2(d,f); sort2(e,k); sort2(g,j); sort2(h,i); \ sort2(b,d); sort2(c,f); sort2(e,h); sort2(i,k); \ sort2(a,e); sort2(b,c); sort2(d,h); sort2(f,j); sort2(g,i); \ sort2(a,b); sort2(c,g); sort2(e,f); sort2(h,i); sort2(j,k); \ sort2(c,e); sort2(d,g); sort2(f,h); sort2(i,j); \ sort2(b,c); sort2(d,e); sort2(f,g); sort2(h,i); \ sort2(c,d); sort2(e,f); sort2(g,h); \ } while (0) #define sort12(a,b,c,d,e,f,g,h,i,j,k,l) do { \ sort2(a,i); sort2(b,h); sort2(c,g); sort2(d,l); sort2(e,k); sort2(f,j); \ sort2(a,c); sort2(b,e); sort2(d,f); sort2(g,i); sort2(h,k); sort2(j,l); \ sort2(a,b); sort2(c,j); sort2(e,h); sort2(f,g); sort2(k,l); \ sort2(b,d); sort2(c,h); sort2(e,j); sort2(i,k); \ sort2(a,b); sort2(c,d); sort2(e,f); sort2(g,h); sort2(i,j); sort2(k,l); \ sort2(b,c); sort2(d,f); sort2(g,i); sort2(j,k); \ sort2(c,e); sort2(d,g); sort2(f,i); sort2(h,j); \ sort2(b,c); sort2(d,e); sort2(f,g); sort2(h,i); sort2(j,k); \ } while (0) static void sorting_network(BLQS_TYPE* l, int partszm1_min_1) { switch (partszm1_min_1) { case 0: break; case 1: sort2(l[0],l[1]); break; case 2: sort3(l[0],l[1],l[2]); break; case 3: sort4(l[0],l[1],l[2],l[3]); break; case 4: sort5(l[0],l[1],l[2],l[3],l[4]); break; case 5: sort6(l[0],l[1],l[2],l[3],l[4],l[5]); break; case 6: sort7(l[0],l[1],l[2],l[3],l[4],l[5],l[6]); break; case 7: sort8(l[0],l[1],l[2],l[3],l[4],l[5],l[6],l[7]); break; case 8: sort9(l[0],l[1],l[2],l[3],l[4],l[5],l[6],l[7],l[8]); break; case 9: sort10(l[0],l[1],l[2],l[3],l[4],l[5],l[6],l[7],l[8],l[9]); break; case 10: sort11(l[0],l[1],l[2],l[3],l[4],l[5],l[6],l[7],l[8],l[9],l[10]); break; case 11: sort12(l[0],l[1],l[2],l[3],l[4],l[5],l[6],l[7],l[8],l[9],l[10],l[11]); break; } } #define med5(a,b,c,d,e) do { \ sort2(a,b); sort2(c,d); sort2(a,c); \ sort2(b,d); sort2(b,c); sort2(c,e); \ sort2(b,c); \ } while(0) static BLQS_TYPE* partition_small(BLQS_TYPE* left, BLQS_TYPE* right) { BLQS_TYPE* outerleft = left; BLQS_TYPE* pivp = left + 6; BLQS_TYPE piv = *pivp; BLQS_TYPE l1 = left[1],l2 = left[2]; BLQS_TYPE r1 = right[-1], r0 = *right; med5(l1, l2, piv, r1, r0); left[1] = l1; left[2] = l2; right[-1] = r1; *right = r0; left += 3; right -= 2; *pivp = *outerleft; BLQS_TYPE swbuf[SMALLPART]; BLQS_TYPE* sw = swbuf; BLQS_TYPE* lwr = left; while (right - left >= 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 < right - UNROLL) { ptrdiff_t avail = min(right - left, SWSZ - (sw - swbuf)); BLQS_TYPE* endp = right - avail; while (right > 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 < left||rwr > right) && left <= right); while (left <= right && !BLQS_CMP(*right, piv)) { right--; rwr--; } memcpy(lwr, swbuf, (sw - swbuf) * sizeof(BLQS_TYPE)); *outerleft = *rwr; *rwr = piv; return rwr; } static void smallsort(BLQS_TYPE* left, BLQS_TYPE* right) { while (right - 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 < partszm1 / 16) { if (mid > 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\.### But what actually happened? 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\. ### Links [blqsort \- Fast Quicksort with C and C\+\+ Interface](https://github.com/chkas/blqsort) [When ‘if’ slows you down, avoid it](https://tiki.li/blog/branchless) [Interactive sorting demo](https://tiki.li/sorting) --- christof\.kaser@gmail\.com