你的代码很快——如果你运气好的话
摘要
本文介绍了一种使用排序网络的无分支快速排序实现，并探讨了现代编译器（特别是Clang）如何在代码以恰当风格编写时，利用无分支指令来优化循环。
暂无内容
查看缓存全文
缓存时间: 2026/07/11 13:23
# 幸运代码
来源：https://tiki.li/blog/lucky_code.html
## 你的代码很快——如果你运气好的话
最近，我在优化 Quicksort 实现时遇到一个有趣的现象。现代编译器（尤其是 Clang）会使用快速、无分支的指令来优化循环——前提是你使用正确的编程风格。
**sort.h – 一个带有排序网络的快速排序**
```c
// 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 – 对 5000 万个 double 排序**
```c
// SPDX-License-Identifier: MIT
#include <stdio.h>
#include <stdlib.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);
}
```
在 macOS/M1（Clang, -O3）上：
```
Time: 4.39
```
C++ 的 `std::sort` 对这个任务需要 1.33 秒。
### 一些小修改
这段代码已经通过排序网络和循环展开进行了微优化。只剩下一些小修改。我们将这种初学者友好的风格（显式展示指针如何移动）：
```c
if (BLQS_CMP(x, piv)) { *lwr = x; lwr++; }
else { *rwr = x; rwr--; }
```
改写成更地道、更紧凑的 C 形式：
```c
if (BLQS_CMP(x, piv)) *lwr++ = x;
else *rwr-- = x;
```
**sort.h – 重写后**
```c
// 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;
// 收集重复元素
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
```
相似文章
无分支快速排序：性能超越 std::sort 和 pdqsort，提供 C 和 C++ API
一种新的无分支快速排序实现（blqsort）借助排序网络技术，在 Apple M1 和 AMD Ryzen 系统上的性能超越了 std::sort 和 pdqsort，以单头文件形式提供 C 和 C++ 库。其性能提升得益于无分支分区、中位数之中位数枢轴选择以及针对小数组的自定义排序网络。
信任你的编译器：现代C++
本文对比了旧的C++性能技巧与现代编译器的能力，表明编译器现在能够将朴素代码优化得比手工调整的技巧更好。包含在AMD Zen 5上使用Clang 21的基准测试。
当编译器让你惊喜
Matt Godbolt 探讨了编译器优化如何将 O(n) 求和循环转换为 O(1) 的闭式解，突出了 Clang 和 GCC 如何采用循环展开和数学简化等复杂技术来大幅提升代码性能。
通过一个“无用”的if语句将代码性能提升四倍
一篇博客文章展示了添加一个看似无用的条件检查如何通过允许CPU的分支预测器消除数据依赖，从而显著提升循环性能，在特定的压缩算法中实现了高达4倍的加速。
6倍更快的二分查找：从编译代码到机械共鸣
本文详细介绍了Rust中二分查找的一系列底层优化，通过利用分支预测和SIMD等CPU架构特性，实现了6倍的加速，并将其应用于scikit-learn梯度提升用例中。