由于问题非常低：

• 我们不能假设库可用（并且调用本身有成本），只能使用普通C语言
• 为了避免排空指令流水线（具有 非常 高的成本），我们也许应该尽量减少分支机构，跳跃，和所有其他类型的控制流断裂（像那些隐藏在背后的序列点&&或||）。
• 房间受到限制，尽量减少寄存器和内存使用是一个问题，理想情况下，最好在适当的位置进行排序。

确实，这个问题是一种高尔夫，其目标不是最小化源代码长度，而是执行时间。我将其称为“ 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);
}

原始结果

随着变体数量的增加，我将它们全部收集在一个测试套件中，可以在此处找到。多亏了凯文·斯托克（KevinStock），实际使用的测试比上面显示的要少一些天真。您可以在自己的环境中编译和执行它。我对不同目标体系结构/编译器上的行为非常感兴趣。（好的，请回答，我将为新结果集的每个贡献者+1）。

一年前，我给丹尼尔·斯图兹巴赫（DanielStutzbach）（打高尔夫球）提供了答案，因为他当时是最快的解决方案（排序网络）的源头。

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和-02的结果，因为出奇的好节目O2是 少 比O1效率。我想知道具体的优化有什么作用？

对拟议解决方案的评论

插入排序（Daniel Stutzbach）

不出所料，尽量减少分支机构确实是一个好主意。

分拣网络（Daniel Stutzbach）

比插入排序更好。我想知道是否主要的效果不是避免外部循环。我尝试通过展开插入排序进行检查，实际上我们得到的数字大致相同（代码在此处）。

分类网络（Paul R）

迄今为止最好的。我用来测试的实际代码在这里。尚不知道为什么它的速度是其他分类网络实施速度的两倍。参数传递
快速最大？

排序网络12 SWAP快速交换

正如DanielStutzbach所建议的，我将他的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。

更新 ：

如上面发布的数字所示，gcc的更高版本仍然可以增强这种效果，并且排名顺序一直是其他任何方法的两倍。

排序网络12的交换顺序已重新排序

Rex Kerr提议与gcc4.4.3的惊人效率使我感到奇怪：具有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个周期。我叫那出奇的快。还有其他可能的改进吗？