最快的固定长度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个周期。 我称之为非常快。 任何其他可能的改进？
对于任何优化，总是最好测试，测试和测试。 我会尝试至少排序网络和插入排序。 如果我打赌，我会根据过去的经验将我的钱投入插入排序。
你对输入数据有什么了解吗？ 某些算法在某些类型的数据下性能会更好。 例如，插入排序在已排序或几乎排序的数据上执行得更好，因此如果排序几乎为零的数据的机会高于平均水平，它将是更好的选择。
您发布的算法与插入排序类似，但看起来您已将交换次数最小化，但需要花费更多的比较费用。 不过，比较远比交换更昂贵，因为分支可能导致指令管道停顿。
这是一个插入排序实现：
static __inline__ int sort6(int *d){
int i, j;
for (i = 1; i < 6; i++) {
int tmp = d[i];
for (j = i; j >= 1 && tmp < d[j-1]; j--)
d[j] = d[j-1];
d[j] = tmp;
}
}
以下是我将如何构建分类网络。 首先，使用此站点为适当长度的网络生成一组最小的SWAP宏。 用功能包装起来让我：
static __inline__ int sort6(int * d){
#define SWAP(x,y) if (d[y] < d[x]) { int tmp = d[x]; d[x] = d[y]; d[y] = tmp; }
SWAP(1, 2);
SWAP(0, 2);
SWAP(0, 1);
SWAP(4, 5);
SWAP(3, 5);
SWAP(3, 4);
SWAP(0, 3);
SWAP(1, 4);
SWAP(2, 5);
SWAP(2, 4);
SWAP(1, 3);
SWAP(2, 3);
#undef SWAP
}
这是一个使用排序网络的实现：
inline void Sort2(int *p0, int *p1)
{
const int temp = min(*p0, *p1);
*p1 = max(*p0, *p1);
*p0 = temp;
}
inline void Sort3(int *p0, int *p1, int *p2)
{
Sort2(p0, p1);
Sort2(p1, p2);
Sort2(p0, p1);
}
inline void Sort4(int *p0, int *p1, int *p2, int *p3)
{
Sort2(p0, p1);
Sort2(p2, p3);
Sort2(p0, p2);
Sort2(p1, p3);
Sort2(p1, p2);
}
inline void Sort6(int *p0, int *p1, int *p2, int *p3, int *p4, int *p5)
{
Sort3(p0, p1, p2);
Sort3(p3, p4, p5);
Sort2(p0, p3);
Sort2(p2, p5);
Sort4(p1, p2, p3, p4);
}
您真的需要非常高效的无分支min和max实现，因为这实际上是代码归结的结果 - 一系列min和max操作（总共13个）。 我将这作为练习给读者。
请注意，该实现很容易实现向量化（例如，SIMD--大多数SIMD ISA具有向量最小/最大指令），并且也适用于GPU实现（例如，CUDA--无分支，不存在经向偏差等问题）。
另请参见：对非常小的列表进行排序的快速算法实现
由于这些是整数，并且比较速度很快，为什么不直接计算每个的排列顺序：
inline void sort6(int *d) {
int e[6];
memcpy(e,d,6*sizeof(int));
int o0 = (d[0]>d[1])+(d[0]>d[2])+(d[0]>d[3])+(d[0]>d[4])+(d[0]>d[5]);
int o1 = (d[1]>=d[0])+(d[1]>d[2])+(d[1]>d[3])+(d[1]>d[4])+(d[1]>d[5]);
int o2 = (d[2]>=d[0])+(d[2]>=d[1])+(d[2]>d[3])+(d[2]>d[4])+(d[2]>d[5]);
int o3 = (d[3]>=d[0])+(d[3]>=d[1])+(d[3]>=d[2])+(d[3]>d[4])+(d[3]>d[5]);
int o4 = (d[4]>=d[0])+(d[4]>=d[1])+(d[4]>=d[2])+(d[4]>=d[3])+(d[4]>d[5]);
int o5 = 15-(o0+o1+o2+o3+o4);
d[o0]=e[0]; d[o1]=e[1]; d[o2]=e[2]; d[o3]=e[3]; d[o4]=e[4]; d[o5]=e[5];
}
上一篇: Fastest sort of fixed length 6 int array
下一篇: Measuring memory bandwidth from the dot product of two arrays