回答另一个Stack Overflow的问题（this one），我偶然发现了一个有趣的子问题。如何最快地对包含6个整数的数组进行排序？
由于这个问题非常低级：
- 我们不能假定库是可用的（而且调用本身也有成本），只能使用纯C。
- 为了避免清空指令流水线（这是一种非常高的成本），我们应该尽可能减少分支、跳转和其他任何控制流中断（例如在
&&或||中隐藏的那些）。 - 空间受限，最小化寄存器和内存使用是一个问题，最好采用原地排序。
实际上，这个问题是一种高尔夫游戏，目标不是使源长度最小化，而是执行时间最短。我称之为“禅”的代码，正如Michael Abrash的书《Zen of Code optimization》及其sequels中所使用的标题。
至于为什么它很有趣，有几个层次：
- 这个例子简单易懂，容易衡量，不需要太多的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.3，后者在优化这个特定代码方面要好得多（对其他提案几乎没有什么区别）。 更新： 如上面发布的数字表明，这个效果仍然受到后来版本的gcc的增强，排名顺序变得比任何其他替代方案都快两倍。
重新排序的交换排序网络12
Rex Kerr提议使用gcc 4.4.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个周期。我认为这非常快。还有其他改进可能吗？
x-y和x+y不会导致下溢或上溢吗？ - Matthieu M.__asm__ volatile (".byte 0x0f, 0x31; shlq $32, %%rdx; orq %%rdx, %0" : "=a" (x) : : "rdx");，因为rdtsc将答案放在EDX：EAX中，而GCC希望它在一个64位寄存器中。您可以通过在-O3下编译来查看错误。另请参见我对Paul R关于更快速的SWAP的评论。 - Paolo BonziniCMP EAX, EBX; SBB EAX, EAX会根据EAX与EBX的大小关系，在EAX中放入0或0xFFFFFFFF。SBB是"带借位减法"，与ADC("带进位加法")相对应; 您所指的状态位 就是 进位位。然而，我记得在 Pentium 4 上，ADC和SBB的延迟和吞吐量很差，与ADD和SUB相比仍然慢两倍，并且在Core CPU上也是如此。自从80386以来，还有SETcc条件存储和CMOVcc条件移动指令，但它们也很慢。 - j_random_hacker