最快的固定长度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];}