最快的固定长度6 int数组

Question

最快的固定长度6 int数组

回答另一个Stack Overflow问题（这个）我偶然发现了一个有趣的子问题。排序6个整数数组的最快方法是什么？

由于问题是非常低的水平：

• 我们不能假设库可用（并且调用本身有它的成本），只有普通的C.

• 避免排空指令流水线（具有非常高的成本），我们也许应该尽量减少分支机构，跳跃，和所有其他类型的控制流断裂的（像那些隐藏在背后的序列点&&或||）。

• 房间受限制，最小化寄存器和内存使用是一个问题，理想情况下，排序可能是最好的。

真的这个问题是一种高尔夫，其目标不是最小化源长度而是执行时间。我把它叫做“Zening”代码在本书的标题中的代码优化禅由迈克尔·亚伯拉什及其续集。

至于为什么它很有趣，有几个层次：

• 这个例子很简单，易于理解和衡量，并没有太多的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],

原始结果

随着变体的数量变得越来越大，我将它们全部收集在一个可以在这里找到的测试套件中。由于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

• 重新排序网络w /快速交换：31.54

• 具有快速交换V2的重新排序的分类网络：33.63

• 内联冒泡排序（Paolo Bonzini）：48.85

• 展开插入排序（Paolo Bonzini）：75.30

我既包括-O1和-02的结果，因为出奇的好节目O2是少比O1效率。我想知道具体的优化有什么影响？

Answer 1

由于这些是整数并且比较快，为什么不直接计算每个的排名顺序：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];}