最快的固定长度6 int数组
回答另一个堆栈溢出问题（这一个）我偶然发现了一个有趣的子问题。 对6个整数的数组进行排序的最快方法是什么？
由于问题非常低：
&&或||序列点后面的流程）。 真的这个问题是一种高尔夫球，其目标不是尽量减少源长度而是缩短执行时间。 我将它称为'Zening'代码，用于Michael Abrash及其续集的“代码优化之禅”一书的标题中。
至于为什么它很有趣，有几层：
这是我的参考（天真的，未优化的）实现和我的测试集。
#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 %dn", 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 %dn", (unsigned)cycles);
}
原始结果
随着变体的数量变得越来越大，我将它们全部收集在可在此处找到的测试套件中。 由于Kevin Stock的使用，所使用的实际测试比上面显示的少一些天真。 您可以在自己的环境中编译并执行它。 我对不同的目标体系结构/编译器的行为很感兴趣。 （好吧，把它放在答案中，我会+1每一个新结果集的贡献者）。
一年前，我对Daniel Stutzbach（打高尔夫）的答案给出了答案，因为他当时是最快解决方案的来源（排序网络）。
Linux 64位，gcc 4.6.1 64位，Intel Core 2 Duo E8400，-O2
Linux 64位，gcc 4.6.1 64位，Intel Core 2 Duo E8400，-O1
我既包括-O1和-02的结果，因为出奇的好节目O2比O1效率较低 。 我不知道具体的优化有哪些效果？
对所提出的解
插入排序（Daniel Stutzbach）
如预期的那样，最小化分支确实是一个好主意。
排序网络（Daniel Stutzbach）
比插入排序更好。 我想知道主要效果是不是避免了外部循环。 我试着通过展开的插入排序来检查，实际上我们得到的数字大致相同（代码在这里）。
排序网络（Paul R）
迄今为止最好的。 我用来测试的实际代码在这里。 不知道为什么它比其他分拣网络实施快两倍。 参数传递？ 快速最大？
对网络进行分类12快速交换SWAP
正如Daniel Stutzbach所建议的那样，我将他的12交换排序网络与无分支快速交换（代码在这里）结合起来。 它的速度确实更快，迄今为止最好，只有少量掉期（约5％），可以预计使用1次掉期。
有趣的是，注意到无网分支交换似乎比使用PPC体系结构的简单交换效率差很多（4倍）。
调用库qsort
为了给出另一个参考点，我还尝试建议只调用库qsort（代码在这里）。 正如预期的那样，速度要慢得多：慢10到30倍......随着新测试套件的出现，主要问题似乎是第一次调用后库的初始加载，并且与其他软件比较起来并不那么糟糕版。 在我的Linux上，它只是慢了3到20倍。 在一些用于其他测试的体系结构上，它似乎甚至更快（我真的很惊讶，因为库qsort使用更复杂的API）。
排序
雷克斯克尔提出了另一种完全不同的方法：对阵列中的每一项直接计算其最终位置。 这是有效的，因为计算等级顺序不需要分支。 这种方法的缺点是它需要三倍的数组内存量（一个数组副本和变量来存储等级顺序）。 表现的结果非常令人惊讶（也很有趣）。 在我使用32位操作系统和Intel Core2 Quad E8300的参考体系结构中，周期数略低于1000（例如使用分支交换进行排序的网络）。 但是，当我在64位盒（Intel Core2 Duo）上编译和执行时，它表现更好：它成为迄今为止最快的。 我终于找出真正的原因。 我的32位盒子使用gcc 4.4.1和我的64位盒子gcc 4.4.3，最后一个在优化这个特定代码方面似乎更好（其他提议没有什么区别）。
更新：
正如上面公布的数据显示，gcc的后续版本对这种影响仍然有所增强，秩序秩序一直比任何其他选择的速度快两倍。
使用重新排序的交换排序网络12
使用gcc 4.4.3的雷克斯克尔建议的惊人效率让我怀疑：3倍内存使用率的程序如何比无分类分类网络更快？ 我的假设是，它在写入之后对类型读取的依赖性较小，可以更好地使用x86的超标量指令调度器。 这给了我一个想法：重新排序交换以最小化写入依赖关系之后的读取。 更简单地说：当你做SWAP(1, 2); SWAP(0, 2); SWAP(1, 2); SWAP(0, 2); 在执行第二个交换之前，您必须等待第一个交换完成，因为它们都访问共同的存储单元。 当你做SWAP(1, 2); SWAP(4, 5); 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个周期。 我称之为非常快。 任何其他可能的改进？
链接地址: http://www.djcxy.com/p/1915.html