在回答另一个 Stack Overflow 问题（这个）时，我偶然发现了一个有趣的子问题。对 6 个整数的数组进行排序的最快方法是什么？
由于问题非常低级：
- 我们不能假设库是可用的（并且调用本身有它的成本），只有纯 C
- 为了避免清空指令管道（成本非常高），我们可能应该尽量减少分支、跳转和所有其他类型的控制流中断（比如隐藏在
&&or中的序列点后面的那些||）。 - 房间受到限制，最小化寄存器和内存使用是一个问题，理想情况下，就地排序可能是最好的。
实际上，这个问题是一种高尔夫，其目标不是最小化源长度而是最小化执行时间。我将其称为“Zening”代码，正如Michael Abrash所著的Zen of Code optimization及其续集的书名中所使用的那样。
至于为什么有趣，有好几层：
- 该示例简单易懂，易于测量，涉及的C技能不多
- 它显示了为问题选择好的算法的效果，以及编译器和底层硬件的效果。
这是我的参考（天真，未优化）实现和我的测试集。
#include <stdio.h>
static __inline__ int sort6(int * d){
char j, i, imin;
int tmp;
for (j = 0 ; j < 5 ; j++){
imin = j;
for (i = j + 1; i < 6 ; i++){
if (d[i] < d[imin]){
imin = i;
}
}
tmp = d[j];
d[j] = d[imin];
d[imin] = tmp;
}
}
static __inline__ unsigned long long rdtsc(void)
{
unsigned long long int x;
__asm__ volatile (".byte 0x0f, 0x31" : "=A" (x));
return x;
}
int main(int argc, char ** argv){
int i;
int d[6][5] = {
{1, 2, 3, 4, 5, 6},
{6, 5, 4, 3, 2, 1},
{100, 2, 300, 4, 500, 6},
{100, 2, 3, 4, 500, 6},
{1, 200, 3, 4, 5, 600},
{1, 1, 2, 1, 2, 1}
};
unsigned long long cycles = rdtsc();
for (i = 0; i < 6 ; i++){
sort6(d[i]);
/*
* printf("d%d : %d %d %d %d %d %d\n", i,
* d[i][0], d[i][6], d[i][7],
* d[i][8], d[i][9], d[i][10]);
*/
}
cycles = rdtsc() - cycles;
printf("Time is %d\n", (unsigned)cycles);
}
原始结果
随着变体的数量越来越多，我将它们全部收集在一个可以在此处找到的测试套件中。感谢 Kevin Stock，实际使用的测试比上面显示的要简单一些。您可以在自己的环境中编译和执行它。我对不同目标架构/编译器的行为非常感兴趣。（好的，伙计们，把它放在答案中，我会为新结果集的每个贡献者 +1）。
一年前，我向 Daniel Stutzbach（打高尔夫球）给出了答案，因为他是当时最快解决方案（排序网络）的来源。
Linux 64 位、gcc 4.6.1 64 位、Intel Core 2 Duo E8400、-O2
- 直接调用 qsort 库函数：689.38
- 天真的实现（插入排序）：285.70
- 插入排序 (Daniel Stutzbach) : 142.12
- 插入排序展开：125.47
- 排名顺序：102.26
- 寄存器排名顺序：58.03
- 排序网络 (Daniel Stutzbach)：111.68
- 排序网络（Paul R）：66.36
- 使用快速交换对网络 12 进行排序：58.86
- 排序网络 12 重新排序交换：53.74
- 排序网络 12 重新排序简单交换：31.54
- 带快速交换的重新排序的排序网络：31.54
- 带快速交换 V2 的重新排序的排序网络：33.63
- 内联冒泡排序（Paolo Bonzini）：48.85
- 展开插入排序 (Paolo Bonzini) : 75.30
Linux 64 位、gcc 4.6.1 64 位、Intel Core 2 Duo E8400、-O1
- 直接调用 qsort 库函数：705.93
- 天真的实现（插入排序）：135.60
- 插入排序 (Daniel Stutzbach) : 142.11
- 插入排序展开：126.75
- 排名顺序：46.42
- 寄存器排名顺序：43.58
- 排序网络 (Daniel Stutzbach)：115.57
- 排序网络（Paul R）：64.44
- 使用快速交换对网络 12 进行排序：61.98
- 排序网络 12 重新排序交换：54.67
- 排序网络 12 重新排序简单交换：31.54
- 带快速交换的重新排序的排序网络：31.24
- 带快速交换 V2 的重新排序的排序网络：33.07
- 内联冒泡排序（Paolo Bonzini）：45.79
- 展开插入排序（Paolo Bonzini）：80.15
我将 -O1 和 -O2 结果都包括在内，因为令人惊讶的是，对于几个程序来说，O2 的效率低于O1。我想知道什么具体的优化有这个效果？
对提议的解决方案的评论
插入排序 (Daniel Stutzbach)
正如预期的那样，最小化分支确实是一个好主意。
排序网络 (Daniel Stutzbach)
比插入排序好。我想知道主要效果是否不是来自避免外部循环。我通过展开插入排序进行了尝试，确实我们得到了大致相同的数字（代码在这里）。
排序网络 (Paul R)
迄今为止最好的。我用来测试的实际代码在这里。还不知道为什么它的速度几乎是其他排序网络实现的两倍。参数传递？快速最大值？
排序网络 12 带有快速交换的交换
正如 Daniel Stutzbach 所建议的，我将他的 12 交换排序网络与无分支快速交换相结合（代码在此处）。它确实更快，是迄今为止最好的，利润率很小（大约 5%），正如使用少掉 1 次交换所预期的那样。
有趣的是，无分支交换似乎比在 PPC 架构上使用 if 的简单交换效率低很多（4 倍）。
调用库 qsort
为了提供另一个参考点，我还按照建议尝试调用库 qsort（代码在此处）。正如预期的那样，它要慢得多：慢了 10 到 30 倍......随着新的测试套件变得很明显，主要问题似乎是第一次调用后库的初始加载，它与其他的相比并没有那么差版本。在我的 Linux 上，它只慢了 3 到 20 倍。在其他人用于测试的某些架构上，它似乎甚至更快（我对此感到非常惊讶，因为库 qsort 使用更复杂的 API）。
排序
Rex Kerr 提出了另一种完全不同的方法：对数组中的每一项直接计算其最终位置。这是有效的，因为计算排名顺序不需要分支。这种方法的缺点是它需要三倍于数组的内存量（一份数组和变量的副本来存储排名顺序）。性能结果非常令人惊讶（也很有趣）。在我的 32 位操作系统和 Intel Core2 Quad E8300 的参考架构上，循环计数略低于 1000（如使用分支交换对网络进行排序）。但是当在我的 64 位机器（Intel Core2 Duo）上编译和执行时，它的表现要好得多：它成为迄今为止最快的。我终于找到了真正的原因。我的 32 位盒子使用 gcc 4.4.1 和我的 64 位盒子 gcc 4.4。
更新：
正如上面公布的数字所示，这种效果仍然被更高版本的 gcc 增强，并且排名顺序始终是任何其他替代方案的两倍。
使用重新排序的交换对网络 12 进行排序
使用 gcc 4.4.3 的 Rex Kerr 提案的惊人效率让我想知道：内存使用量是 3 倍的程序怎么可能比无分支排序网络更快？我的假设是，它具有较少的读写依赖，从而可以更好地使用 x86 的超标量指令调度程序。这给了我一个想法：重新排序交换以最大程度地减少写入后读取的依赖关系。更简单地说：当您这样做时，SWAP(1, 2); SWAP(0, 2);您必须等待第一次交换完成才能执行第二次交换，因为两者都访问公共存储单元。当你这样做时SWAP(1, 2); SWAP(4, 5);，处理器可以并行执行。我试过了，它按预期工作，排序网络的运行速度快了大约 10%。
使用简单交换对网络进行排序 12
在最初的帖子 Steinar H. Gunderson 建议一年后，我们不应该试图超越编译器并保持交换代码简单。这确实是一个好主意，因为生成的代码快了大约 40%！他还提出了使用 x86 内联汇编代码手动优化的交换，仍然可以节省更多的周期。最令人惊讶的是（它说明了程序员的心理），一年前没有人尝试过那个版本的交换。我用来测试的代码在这里。其他人提出了编写 C 快速交换的其他方法，但它产生的性能与具有良好编译器的简单交换相同。
“最佳”代码现在如下：
static inline void sort6_sorting_network_simple_swap(int * d){
#define min(x, y) (x<y?x:y)
#define max(x, y) (x<y?y:x)
#define SWAP(x,y) { const int a = min(d[x], d[y]); \
const int b = max(d[x], d[y]); \
d[x] = a; d[y] = b; }
SWAP(1, 2);
SWAP(4, 5);
SWAP(0, 2);
SWAP(3, 5);
SWAP(0, 1);
SWAP(3, 4);
SWAP(1, 4);
SWAP(0, 3);
SWAP(2, 5);
SWAP(1, 3);
SWAP(2, 4);
SWAP(2, 3);
#undef SWAP
#undef min
#undef max
}
如果我们相信我们的测试集（是的，它很差，它的唯一好处是简短、简单且易于理解我们正在测量的内容），那么生成的代码的平均循环数低于 40 个循环（执行 6 次测试）。这使得每次交换平均为 4 个周期。我称之为惊人的快。还有其他可能的改进吗？