在回答另一个Stack Overflow问题时，我偶然发现了一个有趣的子问题。对6个整数的数组进行排序的最快方法是什么?
因为问题层次很低:
我们不能假设库是可用的(而且调用本身也有开销)，只有纯C 为了避免清空指令管道(这有非常高的成本)，我们可能应该最小化分支、跳转和其他类型的控制流中断(比如隐藏在&&或||序列点后面的那些)。 空间是有限的，最小化寄存器和内存的使用是一个问题，理想情况下，就地排序可能是最好的。
实际上，这个问题是一种Golf，其目标不是最小化源长度，而是最小化执行时间。我称之为“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
Direct call to qsort library function : 689.38 Naive implementation (insertion sort) : 285.70 Insertion Sort (Daniel Stutzbach) : 142.12 Insertion Sort Unrolled : 125.47 Rank Order : 102.26 Rank Order with registers : 58.03 Sorting Networks (Daniel Stutzbach) : 111.68 Sorting Networks (Paul R) : 66.36 Sorting Networks 12 with Fast Swap : 58.86 Sorting Networks 12 reordered Swap : 53.74 Sorting Networks 12 reordered Simple Swap : 31.54 Reordered Sorting Network w/ fast swap : 31.54 Reordered Sorting Network w/ fast swap V2 : 33.63 Inlined Bubble Sort (Paolo Bonzini) : 48.85 Unrolled Insertion Sort (Paolo Bonzini) : 75.30
Linux 64位，gcc 4.6.1 64位，Intel Core 2 Duo E8400， -O1
Direct call to qsort library function : 705.93 Naive implementation (insertion sort) : 135.60 Insertion Sort (Daniel Stutzbach) : 142.11 Insertion Sort Unrolled : 126.75 Rank Order : 46.42 Rank Order with registers : 43.58 Sorting Networks (Daniel Stutzbach) : 115.57 Sorting Networks (Paul R) : 64.44 Sorting Networks 12 with Fast Swap : 61.98 Sorting Networks 12 reordered Swap : 54.67 Sorting Networks 12 reordered Simple Swap : 31.54 Reordered Sorting Network w/ fast swap : 31.24 Reordered Sorting Network w/ fast swap V2 : 33.07 Inlined Bubble Sort (Paolo Bonzini) : 45.79 Unrolled Insertion Sort (Paolo Bonzini) : 80.15
我包括了-O1和-O2的结果，因为令人惊讶的是，在一些程序中，O2的效率低于O1。我想知道什么具体的优化有这种效果?
对建议解决方案的评论
插入排序(丹尼尔·斯图茨巴赫)
正如预期的那样，最小化分支确实是一个好主意。
排序网络(丹尼尔·斯图茨巴赫)
比插入排序好。我想知道主要的效果是不是避免外部循环。我试着通过展开插入排序来检查，确实我们得到了大致相同的数字(代码在这里)。
排序网络(保罗R)
迄今为止最好的。我用来测试的实际代码在这里。目前还不知道为什么它的速度几乎是其他排序网络实现的两倍。参数传递?快速max ?
排序网络12 SWAP与快速交换
根据Daniel Stutzbach的建议，我将他的12交换排序网络与无分支快速交换相结合(代码在这里)。它确实更快，到目前为止最好的，只有很小的利润率(大约5%)，因为可以使用更少的交换。
同样有趣的是，无分支交换似乎比在PPC架构上使用if的简单交换效率低得多(4倍)。
调用库qsort
To give another reference point I also tried as suggested to just call library qsort (code is here). As expected it is much slower : 10 to 30 times slower... as it became obvious with the new test suite, the main problem seems to be the initial load of the library after the first call, and it compares not so poorly with other version. It is just between 3 and 20 times slower on my Linux. On some architecture used for tests by others it seems even to be faster (I'm really surprised by that one, as library qsort use a more complex API).
等级次序
Rex Kerr proposed another completely different method : for each item of the array compute directly its final position. This is efficient because computing rank order do not need branch. The drawback of this method is that it takes three times the amount of memory of the array (one copy of array and variables to store rank orders). The performance results are very surprising (and interesting). On my reference architecture with 32 bits OS and Intel Core2 Quad E8300, cycle count was slightly below 1000 (like sorting networks with branching swap). But when compiled and executed on my 64 bits box (Intel Core2 Duo) it performed much better : it became the fastest so far. I finally found out the true reason. My 32bits box use gcc 4.4.1 and my 64bits box gcc 4.4.3 and the last one seems much better at optimizing this particular code (there was very little difference for other proposals).
更新:
正如上面公布的数字所示，这种效果在gcc的后续版本中仍然得到了增强，Rank Order的速度始终是其他任何替代版本的两倍。
用重新排序的交换对网络进行排序
The amazing efficiency of the Rex Kerr proposal with gcc 4.4.3 made me wonder : how could a program with 3 times as much memory usage be faster than branchless sorting networks? My hypothesis was that it had less dependencies of the kind read after write, allowing for better use of the superscalar instruction scheduler of the x86. That gave me an idea: reorder swaps to minimize read after write dependencies. More simply put: when you do SWAP(1, 2); SWAP(0, 2); you have to wait for the first swap to be finished before performing the second one because both access to a common memory cell. When you do SWAP(1, 2); SWAP(4, 5);the processor can execute both in parallel. I tried it and it works as expected, the sorting networks is running about 10% faster.
使用简单交换对网络进行排序
One year after the original post Steinar H. Gunderson suggested, that we should not try to outsmart the compiler and keep the swap code simple. It's indeed a good idea as the resulting code is about 40% faster! He also proposed a swap optimized by hand using x86 inline assembly code that can still spare some more cycles. The most surprising (it says volumes on programmer's psychology) is that one year ago none of used tried that version of swap. Code I used to test is here. Others suggested other ways to write a C fast swap, but it yields the same performances as the simple one with a decent compiler.
“最佳”代码如下:
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个周期。我称之为惊人的快。还有其他可能的改进吗?
