提问



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


由于问题水平很低:



  • 我们不能假设库可用(并且调用本身有其成本),只有普通的C

  • 为了避免清空指令管道(具有非常高成本),我们应该最小化分支,跳转和其他类型的控制流中断(如&&中隐藏在序列点后面的那些)]]或||)。

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



真的这个问题是一种高尔夫,其目标不是最小化源长度而是执行时间。我把它称为Zening代码,用于Michael Abrash的代码优化书及其续集的书中。 [73] [74]


至于它有趣的原因,有几个层次:



  • 这个例子很简单,易于理解和衡量,涉及的技能不多

  • 它显示了为问题选择好算法的效果,以及编译器和底层硬件的效果。



这是我的参考(天真,未优化)实现和我的测试集。


#include 

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);
}


原始结果



随着变体的数量变得越来越大,我将它们全部收集在一个可以在这里找到的测试套件中。由于凯文·斯托克,所使用的实际测试比上面显示的要少一些。您可以在自己的环境中编译和执行它。我对不同的目标架构/编译器的行为非常感兴趣。(好的,把它放在答案中,我将为新结果集的每个贡献者+1)。[75]


一年前,我给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

  • 重新排序网络w/快速交换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

  • 重新排序网络w/快速交换:31.24

  • 重新排序网络w/快速交换V2:33.07

  • 内联冒泡排序(Paolo Bonzini):45.79

  • 展开插入排序(Paolo Bonzini):80.15



我包括-O1和-O2结果,因为令人惊讶的是,对于几个程序,O2比O1 有效。我想知道具体的优化有什么影响?


对提议的解决方案的评论



插入排序(Daniel Stutzbach)


正如所料,最小化分支确实是一个好主意。


排序网络(Daniel Stutzbach)


比插入排序更好。我想知道主要影响是不是来自避免外部循环。我通过展开的插入排序尝试检查,实际上我们得到大致相同的数字(代码在这里)。[76]


排序网络(Paul R)


到目前为止最好的。我以前测试的实际代码就在这里。不知道为什么它几乎是其他分拣网络实施的两倍。参数传递?快速最大?[77]


按快速交换排序网络12 SWAP


正如Daniel Stutzbach所建议的那样,我将他的12交换分拣网络与无分支快速交换(代码在这里)相结合。它确实更快,是目前为止最好的,利用少量掉期可以预期的小幅度(大约5%)。 [78]


值得注意的是,无分支交换似乎比使用PPC架构的简单交换(4倍)效率低。


调用库qsort


为了给出另一个参考点,我也按照建议尝试调用库qsort(代码在这里)。正如预期的那样速度慢得多:慢了10到30倍......随着新测试套件变得明显,主要问题似乎是第一次调用后库的初始加载,并且与其他调用相比并没有那么差。版。它在我的Linux上慢了3到20倍。在一些用于其他人测试的体系结构上,它似乎更快(我真的很惊讶,因为库qsort使用更复杂的API)。[79]


排名顺序


Rex Kerr提出了另一种完全不同的方法:对于数组的每个项目直接计算其最终位置。这是有效的,因为计算排名顺序不需要分支。这种方法的缺点是它需要三倍的数组内存量(数组的一个副本和存储排名顺序的变量)。性能结果非常令人惊讶(而且很有趣)。在我的32位操作系统和英特尔酷睿2四核E8300的参考架构上,循环计数略低于1000(就像分支交换的分拣网络一样)。但是当我在我的64位盒(Intel Core2 Duo)上编译和执行时,它的表现要好得多:它成为目前为止最快的。我终于找到了真正的原因。我的32位框使用gcc 4.4.1和我的64位框gcc 4.4.3,最后一个框似乎更好地优化了这个特定代码(其他提议几乎没有差别)。


更新:


正如上面公布的数据所示,gcc的后续版本仍然提高了这种效果,而Rank Order的速度始终是其他任何替代品的两倍。


使用重新排序的交换对网络12进行排序


使用gcc 4.4.3的Rex Kerr提议的惊人效率让我想知道:具有3倍内存使用量的程序如何比无分支排序网络更快?我的假设是它在写入后具有较少的读取类型的依赖性,允许更好地使用x86的超标量指令调度程序。这给了我一个想法:重新排序交换以最小化写入依赖项后的读取。更简单地说:当你做SWAP(1, 2); SWAP(0, 2);时,你必须等待第一次交换完成才能执行第二次交换,因为它们都可以访问公共存储单元。执行SWAP(1, 2); SWAP(4, 5);时,处理器可以并行执行。我尝试了它并按预期工作,排序网络的运行速度提高了约10%。


使用简单交换对网络12进行排序


在最初的帖子Steinar H. Gunderson建议的一年后,我们不应该试图超越编译器并保持交换代码简单。这确实是一个好主意,因为生成的代码速度提高了大约40%!他还提出了一个使用x86内联汇编代码优化的交换,它仍然可以节省更多的周期。最令人惊讶的是(它说的是程序员的心理学卷) )是一年前没有使用过的那个版本的交换。我以前用来测试的代码就在这里。其他人提出了编写C快速交换的其他方法,但它产生的性能与具有合适编译器的简单方法相同。[80]


最佳代码现在如下:


static inline void sort6_sorting_network_simple_swap(int * d){
#define min(x, y) (x


如果我们相信我们的测试集(并且,它是非常差的,仅仅是好处是简短且易于理解我们正在测量的内容),一种类型的结果代码的平均周期数低于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宏。把它包含在一个函数中给了我:[81]


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
}

其它参考1


这是使用排序网络的实现:[82]


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);  
}


你真的需要非常有效的无分支minmax实现,因为这实际上是这个代码归结为 - minmax操作的序列(13每个,总计)。我将此作为练习留给读者。


请注意,此实现很容易实现向量化(例如SIMD - 大多数SIMD ISA具有向量最小/最大指令)以及GPU实现(例如CUDA - 无分支,没有扭曲分歧等问题)。


另请参阅:快速算法实现以排序非常小的列表

其它参考2


由于这些是整数并且比较快,为什么不直接计算每个的排名顺序:


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];
}

其它参考3


看起来我迟到了一年,但在这里我们去......


看一下gcc 4.5.2生成的程序集,我观察到每次交换都在进行加载和存储,实际上并不需要。最好将6个值加载到寄存器中,对它们进行排序,并将它们存储回来我命令商店的负载尽可能接近,首先需要寄存器并最后使用。我还使用了Steinar H. Gunderson的SWAP宏。更新:我切换到Paolo Bonzini的SWAP宏,其中gcc转换成类似于Gunderson的东西,但是gcc能够更好地命令指令,因为它们不是作为显式汇编而给出的。


虽然可能有更好的排序,但我使用与重新排序的交换网络相同的交换顺序作为最佳性能。如果我找到更多的时间,我将生成并测试一堆排列。


我更改了测试代码以考虑超过4000个阵列,并显示了对每个阵列进行排序所需的平均周期数。在i5-650上我得到~34.1个循环/排序(使用-O3),与原始重新排序的排序网络相比,得到~65.3个循环/排序(使用-O1,beats -O2和-O3)。


#include 

static inline void sort6_fast(int * d) {
#define SWAP(x,y) { int dx = x, dy = y, tmp; tmp = x = dx < dy ? dx : dy; y ^= dx ^ tmp; }
    register int x0,x1,x2,x3,x4,x5;
    x1 = d[1];
    x2 = d[2];
    SWAP(x1, x2);
    x4 = d[4];
    x5 = d[5];
    SWAP(x4, x5);
    x0 = d[0];
    SWAP(x0, x2);
    x3 = d[3];
    SWAP(x3, x5);
    SWAP(x0, x1);
    SWAP(x3, x4);
    SWAP(x1, x4);
    SWAP(x0, x3);
    d[0] = x0;
    SWAP(x2, x5);
    d[5] = x5;
    SWAP(x1, x3);
    d[1] = x1;
    SWAP(x2, x4);
    d[4] = x4;
    SWAP(x2, x3);
    d[2] = x2;
    d[3] = x3;

#undef SWAP
#undef min
#undef max
}

static __inline__ unsigned long long rdtsc(void)
{
    unsigned long long int x;
    __asm__ volatile ("rdtsc; shlq $32, %%rdx; orq %%rdx, %0" : "=a" (x) : : "rdx");
    return x;
}

void ran_fill(int n, int *a) {
    static int seed = 76521;
    while (n--) *a++ = (seed = seed *1812433253 + 12345);
}

#define NTESTS 4096
int main() {
    int i;
    int d[6*NTESTS];
    ran_fill(6*NTESTS, d);

    unsigned long long cycles = rdtsc();
    for (i = 0; i < 6*NTESTS ; i+=6) {
        sort6_fast(d+i);
    }
    cycles = rdtsc() - cycles;
    printf("Time is %.2lf\n", (double)cycles/(double)NTESTS);

    for (i = 0; i < 6*NTESTS ; i+=6) {
        if (d[i+0] > d[i+1] || d[i+1] > d[i+2] || d[i+2] > d[i+3] || d[i+3] > d[i+4] || d[i+4] > d[i+5])
            printf("d%d : %d %d %d %d %d %d\n", i,
                    d[i+0], d[i+1], d[i+2],
                    d[i+3], d[i+4], d[i+5]);
    }
    return 0;
}


我更改了修改测试套件以报告每种类型的时钟并运行更多测试(更新cmp函数以处理整数溢出),这里是一些不同体系结构的结果。我尝试在AMD CPU上进行测试,但是rdtsc在我可用的X6 1100T上并不可靠。[84]


Clarkdale (i5-650)
==================
Direct call to qsort library function      635.14   575.65   581.61   577.76   521.12
Naive implementation (insertion sort)      538.30   135.36   134.89   240.62   101.23
Insertion Sort (Daniel Stutzbach)          424.48   159.85   160.76   152.01   151.92
Insertion Sort Unrolled                    339.16   125.16   125.81   129.93   123.16
Rank Order                                 184.34   106.58   54.74    93.24    94.09
Rank Order with registers                  127.45   104.65   53.79    98.05    97.95
Sorting Networks (Daniel Stutzbach)        269.77   130.56   128.15   126.70   127.30
Sorting Networks (Paul R)                  551.64   103.20   64.57    73.68    73.51
Sorting Networks 12 with Fast Swap         321.74   61.61    63.90    67.92    67.76
Sorting Networks 12 reordered Swap         318.75   60.69    65.90    70.25    70.06
Reordered Sorting Network w/ fast swap     145.91   34.17    32.66    32.22    32.18

Kentsfield (Core 2 Quad)
========================
Direct call to qsort library function      870.01   736.39   723.39   725.48   721.85
Naive implementation (insertion sort)      503.67   174.09   182.13   284.41   191.10
Insertion Sort (Daniel Stutzbach)          345.32   152.84   157.67   151.23   150.96
Insertion Sort Unrolled                    316.20   133.03   129.86   118.96   105.06
Rank Order                                 164.37   138.32   46.29    99.87    99.81
Rank Order with registers                  115.44   116.02   44.04    116.04   116.03
Sorting Networks (Daniel Stutzbach)        230.35   114.31   119.15   110.51   111.45
Sorting Networks (Paul R)                  498.94   77.24    63.98    62.17    65.67
Sorting Networks 12 with Fast Swap         315.98   59.41    58.36    60.29    55.15
Sorting Networks 12 reordered Swap         307.67   55.78    51.48    51.67    50.74
Reordered Sorting Network w/ fast swap     149.68   31.46    30.91    31.54    31.58

Sandy Bridge (i7-2600k)
=======================
Direct call to qsort library function      559.97   451.88   464.84   491.35   458.11
Naive implementation (insertion sort)      341.15   160.26   160.45   154.40   106.54
Insertion Sort (Daniel Stutzbach)          284.17   136.74   132.69   123.85   121.77
Insertion Sort Unrolled                    239.40   110.49   114.81   110.79   117.30
Rank Order                                 114.24   76.42    45.31    36.96    36.73
Rank Order with registers                  105.09   32.31    48.54    32.51    33.29
Sorting Networks (Daniel Stutzbach)        210.56   115.68   116.69   107.05   124.08
Sorting Networks (Paul R)                  364.03   66.02    61.64    45.70    44.19
Sorting Networks 12 with Fast Swap         246.97   41.36    59.03    41.66    38.98
Sorting Networks 12 reordered Swap         235.39   38.84    47.36    38.61    37.29
Reordered Sorting Network w/ fast swap     115.58   27.23    27.75    27.25    26.54

Nehalem (Xeon E5640)
====================
Direct call to qsort library function      911.62   890.88   681.80   876.03   872.89
Naive implementation (insertion sort)      457.69   236.87   127.68   388.74   175.28
Insertion Sort (Daniel Stutzbach)          317.89   279.74   147.78   247.97   245.09
Insertion Sort Unrolled                    259.63   220.60   116.55   221.66   212.93
Rank Order                                 140.62   197.04   52.10    163.66   153.63
Rank Order with registers                  84.83    96.78    50.93    109.96   54.73
Sorting Networks (Daniel Stutzbach)        214.59   220.94   118.68   120.60   116.09
Sorting Networks (Paul R)                  459.17   163.76   56.40    61.83    58.69
Sorting Networks 12 with Fast Swap         284.58   95.01    50.66    53.19    55.47
Sorting Networks 12 reordered Swap         281.20   96.72    44.15    56.38    54.57
Reordered Sorting Network w/ fast swap     128.34   50.87    26.87    27.91    28.02

其它参考4


测试代码非常糟糕;它溢出了初始数组(不要让人们在这里读取编译器警告吗?),printf打印出错误的元素,它使用.byte为rdtsc没有任何理由,只有一个运行(!),那里有没有检查最终结果是否正确(所以它很容易优化成微妙的错误),包含的测试是非常基本的(没有负数?)并没有什么可以阻止编译器丢弃整个函数作为死代码。


话虽如此,改进bitonic网络解决方案也很容易;只需将min/max/SWAP内容更改为


#define SWAP(x,y) { int tmp; asm("mov %0, %2 ; cmp %1, %0 ; cmovg %1, %0 ; cmovg %2, %1" : "=r" (d[x]), "=r" (d[y]), "=r" (tmp) : "0" (d[x]), "1" (d[y]) : "cc"); }


它对我来说快了大约65%(Debian gcc 4.4.5 with -O2,amd64,Core i7)。

其它参考5


几天前我偶然发现了Google的这个问题,因为我还需要快速排序6个整数的固定长度数组。然而,在我的情况下,我的整数只有8位(而不是32位),我没有严格要求只使用C.我想我会分享我的发现,以防它们可能对某人有帮助......


我在程序集中实现了一种网络排序的变体,它使用SSE来尽可能地对比较和交换操作进行矢量化。完成对数组的排序需要六次通过。我使用一种新颖的机制直接将PCMPGTB(矢量化比较)的结果转换为PSHUFB(矢量化交换)的混洗参数,仅使用PADDB(矢量化添加),在某些情况下还使用PAND(按位AND)指令。


这种方法还具有产生真正无分支功能的副作用。没有任何跳转指令。


看起来这个实现比当前标记为问题中最快的选项(使用简单交换排序网络12)的实现快<38%。我在测试期间修改了该实现以使用char数组元素,以使比较公平。


我应该注意,这种方法可以应用于任何最多16个元素的数组。我预计相对于替代品的相对速度优势会对更大的阵列变大。


代码用MASM编写,用于带有SSSE3的x86_64处理器。该函数使用新的Windows x64调用约定。这里是...


PUBLIC simd_sort_6

.DATA

ALIGN 16

pass1_shuffle   OWORD   0F0E0D0C0B0A09080706040503010200h
pass1_add       OWORD   0F0E0D0C0B0A09080706050503020200h
pass2_shuffle   OWORD   0F0E0D0C0B0A09080706030405000102h
pass2_and       OWORD   00000000000000000000FE00FEFE00FEh
pass2_add       OWORD   0F0E0D0C0B0A09080706050405020102h
pass3_shuffle   OWORD   0F0E0D0C0B0A09080706020304050001h
pass3_and       OWORD   00000000000000000000FDFFFFFDFFFFh
pass3_add       OWORD   0F0E0D0C0B0A09080706050404050101h
pass4_shuffle   OWORD   0F0E0D0C0B0A09080706050100020403h
pass4_and       OWORD   0000000000000000000000FDFD00FDFDh
pass4_add       OWORD   0F0E0D0C0B0A09080706050403020403h
pass5_shuffle   OWORD   0F0E0D0C0B0A09080706050201040300h
pass5_and       OWORD 0000000000000000000000FEFEFEFE00h
pass5_add       OWORD   0F0E0D0C0B0A09080706050403040300h
pass6_shuffle   OWORD   0F0E0D0C0B0A09080706050402030100h
pass6_add       OWORD   0F0E0D0C0B0A09080706050403030100h

.CODE

simd_sort_6 PROC FRAME

    .endprolog

    ; pxor xmm4, xmm4
    ; pinsrd xmm4, dword ptr [rcx], 0
    ; pinsrb xmm4, byte ptr [rcx + 4], 4
    ; pinsrb xmm4, byte ptr [rcx + 5], 5
    ; The benchmarked 38% faster mentioned in the text was with the above slower sequence that tied up the shuffle port longer.  Same on extract
    ; avoiding pins/extrb also means we don't need SSE 4.1, but SSSE3 CPUs without SSE4.1 (e.g. Conroe/Merom) have slow pshufb.
    movd    xmm4, dword ptr [rcx]
    pinsrw  xmm4,  word ptr [rcx + 4], 2  ; word 2 = bytes 4 and 5


    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass1_shuffle]
    pcmpgtb xmm5, xmm4
    paddb xmm5, oword ptr [pass1_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass2_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass2_and]
    paddb xmm5, oword ptr [pass2_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass3_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass3_and]
    paddb xmm5, oword ptr [pass3_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass4_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass4_and]
    paddb xmm5, oword ptr [pass4_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass5_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass5_and]
    paddb xmm5, oword ptr [pass5_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass6_shuffle]
    pcmpgtb xmm5, xmm4
    paddb xmm5, oword ptr [pass6_add]
    pshufb xmm4, xmm5

    ;pextrd dword ptr [rcx], xmm4, 0    ; benchmarked with this
    ;pextrb byte ptr [rcx + 4], xmm4, 4 ; slower version
    ;pextrb byte ptr [rcx + 5], xmm4, 5
    movd   dword ptr [rcx], xmm4
    pextrw  word ptr [rcx + 4], xmm4, 2  ; x86 is little-endian, so this is the right order

    ret

simd_sort_6 ENDP

END


您可以将其编译为可执行对象并将其链接到C项目中。有关如何在Visual Studio中执行此操作的说明,您可以阅读本文。您可以使用以下C原型从C代码调用函数:[85]


void simd_sort_6(char *values);

其它参考6


虽然我真的很喜欢提供的交换宏:


#define min(x, y) (y ^ ((x ^ y) & -(x < y)))
#define max(x, y) (x ^ ((x ^ y) & -(x < y)))
#define SWAP(x,y) { int tmp = min(d[x], d[y]); d[y] = max(d[x], d[y]); d[x] = tmp; }


我看到了一个改进(一个好的编译器可能会做):


#define SWAP(x,y) { int tmp = ((x ^ y) & -(y < x)); y ^= tmp; x ^= tmp; }


我们注意min和max如何工作并明确地拉出公共子表达式。这完全消除了最小和最大宏。

其它参考7


在没有基准测试并查看实际编译器生成的程序集的情如果我让GCC用条件移动指令优化min,我得到33%的加速:


#define SWAP(x,y) { int dx = d[x], dy = d[y], tmp; tmp = d[x] = dx < dy ? dx : dy; d[y] ^= dx ^ tmp; }


(测试代码中280对420周期)。使用?:做最大值或多或少相同,几乎在噪声中丢失,但上面的速度要快一些。对于GCC和Clang,这个SWAP更快。


编译器在寄存器分配和别名分析方面也做得非常出色,有效地将d [[x]]预先移动到局部变量中,并且最后只复制回内存。事实上,他们比你完全使用局部变量(如d0 = d[0], d1 = d[1], d2 = d[2], d3 = d[3], d4 = d[4], d5 = d[5])更好。我写这篇文章是因为你正在进行强有力的优化,并试图在min/max上超越编译器。:)


顺便说一句,我试过Clang和GCC。他们进行相同的优化,但由于调度差异,两者在结果上有一些变化,不能说实际上哪个更快或更慢.GCC在分拣网络上更快,Clang在二次分类上。


为了完整性,也可以进行展开的冒泡排序和插入排序。这是冒泡排序:


SWAP(0,1); SWAP(1,2); SWAP(2,3); SWAP(3,4); SWAP(4,5);
SWAP(0,1); SWAP(1,2); SWAP(2,3); SWAP(3,4);
SWAP(0,1); SWAP(1,2); SWAP(2,3);
SWAP(0,1); SWAP(1,2);
SWAP(0,1);


这是插入排序:


//#define ITER(x) { if (t < d[x]) { d[x+1] = d[x]; d[x] = t; } }
//Faster on x86, probably slower on ARM or similar:
#define ITER(x) { d[x+1] ^= t < d[x] ? d[x] ^ d[x+1] : 0; d[x] = t < d[x] ? t : d[x]; }
static inline void sort6_insertion_sort_unrolled_v2(int * d){
    int t;
    t = d[1]; ITER(0);
    t = d[2]; ITER(1); ITER(0);
    t = d[3]; ITER(2); ITER(1); ITER(0);
    t = d[4]; ITER(3); ITER(2); ITER(1); ITER(0);
    t = d[5]; ITER(4); ITER(3); ITER(2); ITER(1); ITER(0);


这种插入排序比Daniel Stutzbach更快,并且在GPU或具有预测的计算机上特别好,因为ITER只能用3条指令完成(而SWAP则为4条)。例如,这是t = d[2]; ITER(1); ITER(0);]] ARM程序集中的行:


    MOV    r6, r2
    CMP    r6, r1
    MOVLT  r2, r1
    MOVLT  r1, r6
    CMP    r6, r0
    MOVLT  r1, r0
    MOVLT  r0, r6


对于六个元素,插入排序与排序网络竞争(12次交换与15次迭代平衡4次指令/交换与3次指令/迭代);冒泡当然比较慢。但是当尺寸增大时,它不会成立,因为插入排序是O(n ^ 2),而排序网络是O(n log n)。

其它参考8


我将测试套件移植到我无法识别的PPC架构机器上(不需要触摸代码,只需增加测试的迭代次数,使用8个测试用例来避免使用mods污染结果并替换x86特定的rdtsc):


直接调用qsort库函数:101


天真实施(插入排序):299


插入排序(Daniel Stutzbach):108


插入排序已展开:51


排序网络(Daniel Stutzbach):26


排序网络(Paul R):85


使用快速交换排序网络:117


排序网络12重新排序交换:116


排名顺序:56

其它参考9


XOR交换在您的交换功能中可能很有用。


void xorSwap (int *x, int *y) {
     if (*x != *y) {
         *x ^= *y;
         *y ^= *x;
         *x ^= *y;
     }
 }


if可能会导致您的代码过多分歧,但如果您保证所有的int都是唯一的,那么这可能很方便。

其它参考10


期待尝试这一点,并从这些例子中亚博2018平台,但首先是我的1.5 GHz PPC Powerbook G4 w/1 GB DDR RAM的一些时序。 (我从http://www.mcs.anl.gov/~kazutomo/rdtsc.html为PPC借了一个类似rdtsc的计时器来计算时间。)我运行了几次程序,绝对结果各不相同但是一致最快的测试是插入排序(Daniel Stutzbach),其中Insertion Sort Unrolled紧随其后。 [86]


这是最后一次:


**Direct call to qsort library function** : 164
**Naive implementation (insertion sort)** : 138
**Insertion Sort (Daniel Stutzbach)**     : 85
**Insertion Sort Unrolled**               : 97
**Sorting Networks (Daniel Stutzbach)**   : 457
**Sorting Networks (Paul R)**             : 179
**Sorting Networks 12 with Fast Swap**    : 238
**Sorting Networks 12 reordered Swap**    : 236
**Rank Order**                            : 116

其它参考11


以下是我对此主题的贡献:针对包含唯一值的6成员int向量(valp)的优化的1,4 gap gaport。


void shellsort (int *valp)
{      
  int c,a,*cp,*ip=valp,*ep=valp+5;

  c=*valp;    a=*(valp+4);if (c>a) {*valp=    a;*(valp+4)=c;}
  c=*(valp+1);a=*(valp+5);if (c>a) {*(valp+1)=a;*(valp+5)=c;}

  cp=ip;    
  do
  {
    c=*cp;
    a=*(cp+1);
    do
    {
      if (c=valp);
    ip+=1;
    cp=ip;
  } while (ip


在配备双核Athlon M300 @ 2 Ghz(DDR2内存)的HP dv7-3010so笔记本电脑上,它可在165个时钟周期内执行。这是从每个唯一序列的时间计算的平均值(总共6!/720)。使用OpenWatcom 1.8编译为Win32。循环本质上是一种插入排序,长度为16条指令/37字节。


我没有要编译的64位环境。

其它参考12


如果插入排序在这里具有相当的竞争力,我建议尝试一个shellort。我担心6个元素可能太少而不能成为最好的元素,但它可能值得一试。


示例代码,未经测试,未调整等。您想调整inc=4和inc - =3序列以找到最佳值(例如,尝试inc=2,inc - =1)。


static __inline__ int sort6(int * d) {
    char j, i;
    int tmp;
    for (inc = 4; inc > 0; inc -= 3) {
        for (i = inc; i < 5; i++) {
            tmp = a[i];
            j = i;
            while (j >= inc && a[j - inc] > tmp) {
                a[j] = a[j - inc];
                j -= inc;
            }
            a[j] = tmp;
        }
    }
}


我不认为这会赢,但如果有人发布关于排序10个元素的问题,谁知道......


根据维基百科,这甚至可以与排序网络结合:
Pratt,V(1979)。 Shellsort和分拣网络(计算机科学中的杰出论文)。花环。国际标准书号0-824-04406-1

其它参考13


这个问题变得很老了,但实际上我现在必须解决同样的问题:快速算法来排序小数组。我认为分享我的知识是个好主意。当我第一次开始使用排序网络时,我终于设法找到其他算法,其中执行的比较总数对6个值的每个排列进行排序小于排序网络,并且小于插入排序。我没有计算掉期数量;我预计它会大致相当(可能会高一些)输入法)。


算法sort6使用算法sort4,它使用算法sort3。这是一些轻量级C ++形式的实现(原始模板很重,因此它可以与任何随机访问迭代器和任何合适的比较函数一起使用)。


排序3个值



以下算法是展开的插入排序。当必须执行两次交换(6次分配)时,它使用4次分配:


void sort3(int* array)
{
    if (array[1] < array[0]) {
        if (array[2] < array[0]) {
            if (array[2] < array[1]) {
                std::swap(array[0], array[2]);
            } else {
                int tmp = array[0];
                array[0] = array[1];
                array[1] = array[2];
                array[2] = tmp;
            }
        } else {
            std::swap(array[0], array[1]);
        }
    } else {
        if (array[2] < array[1]) {
            if (array[2] < array[0]) {
                int tmp = array[2];
                array[2] = array[1];
                array[1] = array[0];
                array[0] = tmp;
            } else {
                std::swap(array[1], array[2]);
            }
        }
    }
}


它看起来有点复杂,因为排序对于数组的每个可能的排列都有或多或少的一个分支,使用2~3个比较和最多4个赋值来对这三个值进行排序。


排序4个值



这个调用sort3然后使用数组的最后一个元素执行展开的插入排序:


void sort4(int* array)
{
    // Sort the first 3 elements
    sort3(array);

    // Insert the 4th element with insertion sort 
    if (array[3] < array[2]) {
        std::swap(array[2], array[3]);
        if (array[2] < array[1]) {
            std::swap(array[1], array[2]);
            if (array[1] < array[0]) {
                std::swap(array[0], array[1]);
            }
        }
    }
}


该算法执行3到6次比较,最多5次交换。展开插入排序很容易,但我们将使用另一种算法进行最后一次排序...


排序6个值



这个使用我所谓的双插入排序的展开版本。这个名字不是那么好,但它很具描述性,以下是它的工作原理:



  • 对除阵列的第一个和最后一个元素之外的所有内容进行排序。

  • 如果第一个元素和第一个元素大于最后一个元素,则交换第一个元素和元素。

  • 将第一个元素从前面插入排序后的序列,然后从后面插入最后一个元素。



在交换之后,第一个元素总是小于最后一个元素,这意味着,当将它们插入到排序序列中时,在最坏的情况下插入两个元素不会超过N个比较:例如,如果第一个元素已插入第3个位置,然后最后一个元素不能插入低于第4个位置。


void sort6(int* array)
{
    // Sort everything but first and last elements
    sort4(array+1);

    // Switch first and last elements if needed
    if (array[5] < array[0]) {
        std::swap(array[0], array[5]);
    }

    // Insert first element from the front
    if (array[1] < array[0]) {
        std::swap(array[0], array[1]);
        if (array[2] < array[1]) {
            std::swap(array[1], array[2]);
            if (array[3] < array[2]) {
                std::swap(array[2], array[3]);
                if (array[4] < array[3]) {
                    std::swap(array[3], array[4]);
                }
            }
        }
    }

    // Insert last element from the back
    if (array[5] < array[4]) {
        std::swap(array[4], array[5]);
        if (array[4] < array[3]) {
            std::swap(array[3], array[4]);
            if (array[3] < array[2]) {
                std::swap(array[2], array[3]);
                if (array[2] < array[1]) {
                    std::swap(array[1], array[2]);
                }
            }
        }
    }
}


我对6个值的每个排列的测试表明,这种算法总是执行6到13次比较。我没有计算掉掉的交换次数,但在最坏的情况下我不希望它高于11。


我希望这有帮助,即使这个问题可能不再代表实际问题:)


EDIT:将其置于提供的基准测试之后,它比大多数有趣的替代品更加清晰。它往往比展开的插入排序更好一点,但它几乎就是它。基本上,它不是整数的最佳排序,但对于具有昂贵比较操作的类型可能会很有趣。

其它参考14


我知道我已经超级晚了,但我有兴趣尝试一些不同的解决方案。首先,我清理了那个粘贴,使其编译,并将其放入存储库。我保留了一些不合需要的解决方案作为死胡同,以便其他人不会尝试。其中包括我的第一个解决方案,它试图确保x1> x2计算一次。优化后,它并不比其他简单版本快。


我添加了排序顺序排序的循环版本,因为我自己的本研究应用程序用于排序2-8项,因此由于存在可变数量的参数,因此需要循环。这也是我忽略排序网络解决方案的原因。


测试代码没有测试重复项是否正确处理,所以虽然现有解决方案都是正确的,但我在测试代码中添加了一个特殊情况,以确保正确处理重复项。


然后,我写了一个完全在AVX寄存器中的插入排序。在我的机器上,它比其他插入排序快25%,但比排名顺序慢100%。我这样做纯粹是为了实验,并且由于插入排序中的分支而没有期望这更好。


static inline void sort6_insertion_sort_avx(int* d) {
    __m256i src = _mm256_setr_epi32(d[0], d[1], d[2], d[3], d[4], d[5], 0, 0);
    __m256i index = _mm256_setr_epi32(0, 1, 2, 3, 4, 5, 6, 7);
    __m256i shlpermute = _mm256_setr_epi32(7, 0, 1, 2, 3, 4, 5, 6);
    __m256i sorted = _mm256_setr_epi32(d[0], INT_MAX, INT_MAX, INT_MAX,
            INT_MAX, INT_MAX, INT_MAX, INT_MAX);
    __m256i val, gt, permute;
    unsigned j;
     // 8 / 32 = 2^-2
#define ITER(I) \
        val = _mm256_permutevar8x32_epi32(src, _mm256_set1_epi32(I));\
        gt =  _mm256_cmpgt_epi32(sorted, val);\
        permute =  _mm256_blendv_epi8(index, shlpermute, gt);\
        j = ffs( _mm256_movemask_epi8(gt)) >> 2;\
        sorted = _mm256_blendv_epi8(_mm256_permutevar8x32_epi32(sorted, permute),\
                val, _mm256_cmpeq_epi32(index, _mm256_set1_epi32(j)))
    ITER(1);
    ITER(2);
    ITER(3);
    ITER(4);
    ITER(5);
    int x[8];
    _mm256_storeu_si256((__m256i*)x, sorted);
    d[0] = x[0]; d[1] = x[1]; d[2] = x[2]; d[3] = x[3]; d[4] = x[4]; d[5] = x[5];
#undef ITER
}


然后,我使用AVX编写了排名顺序排序。这与其他排序解决方案的速度相匹配,但速度并不快。这里的问题是我只能用AVX计算索引,然后我必须制作一个索引表。这是因为计算是基于目标而不是基于源。请参阅从基于来源的指数转换为基于目的地的指数


static inline void sort6_rank_order_avx(int* d) {
    __m256i ror = _mm256_setr_epi32(5, 0, 1, 2, 3, 4, 6, 7);
    __m256i one = _mm256_set1_epi32(1);
    __m256i src = _mm256_setr_epi32(d[0], d[1], d[2], d[3], d[4], d[5], INT_MAX, INT_MAX);
    __m256i rot = src;
    __m256i index = _mm256_setzero_si256();
    __m256i gt, permute;
    __m256i shl = _mm256_setr_epi32(1, 2, 3, 4, 5, 6, 6, 6);
    __m256i dstIx = _mm256_setr_epi32(0,1,2,3,4,5,6,7);
    __m256i srcIx = dstIx;
    __m256i eq = one;
    __m256i rotIx = _mm256_setzero_si256();
#define INC(I)\
    rot = _mm256_permutevar8x32_epi32(rot, ror);\
    gt = _mm256_cmpgt_epi32(src, rot);\
    index = _mm256_add_epi32(index, _mm256_and_si256(gt, one));\
    index = _mm256_add_epi32(index, _mm256_and_si256(eq,\
                _mm256_cmpeq_epi32(src, rot)));\
    eq = _mm256_insert_epi32(eq, 0, I)
    INC(0);
    INC(1);
    INC(2);
    INC(3);
    INC(4);
    int e[6];
    e[0] = d[0]; e[1] = d[1]; e[2] = d[2]; e[3] = d[3]; e[4] = d[4]; e[5] = d[5];
    int i[8];
    _mm256_storeu_si256((__m256i*)i, index);
    d[i[0]] = e[0]; d[i[1]] = e[1]; d[i[2]] = e[2]; d[i[3]] = e[3]; d[i[4]] = e[4]; d[i[5]] = e[5];
}


回购可以在这里找到:https://github.com/eyepatchParrot/sort6/[89]

其它参考15


我相信你的问题有两部分。



  • 首先是确定最佳算法。这样做 - 至少在这种情况下 - 通过循环遍历每个可能的排序(没有那么多),它允许您计算比较和交换的精确最小值,最大值,平均值和标准差。有一个或两个亚军也很方便。

  • 第二是优化算法。可以做很多事情来将教科书代码示例转换为均值和精益现实算法。如果您意识到算法无法在所需的范围内进行优化,请尝试获得亚军。



我不会太担心清空管道(假设当前的x86):分支预测已经走了很长的路。我担心的是确保代码和数据分别适合一个缓存行(代码可能是两个)一旦获取延迟低得令人耳目一新,这将弥补任何失速。这也意味着你的内部循环可能是10个指令左右,它应该是正确的位置(在我的排序算法中有两个不同的内部循环,它们是10个指令/22个字节和9/22长)。假设代码不包含任何div,你可以肯定它会非常快。

其它参考16


我发现,至少在我的系统中,下面定义的函数sort6_iterator()sort6_iterator_local()的运行速度至少与上述当前记录持有者一样快,并且通常明显更快:


#define MIN(x, y) (x 
inline void sort6_iterator(IterType it) 
{
#define SWAP(x,y) { const auto a = MIN(*(it + x), *(it + y)); \
  const auto b = MAX(*(it + x), *(it + y)); \
  *(it + x) = a; *(it + 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
}


我在我的计时代码中传递了这个函数std::vector的迭代器。我怀疑使用迭代器给g ++确定了迭代器引用的内存能够和不可能发生的事情,否则就不会这样做了。有这些保证允许g ++更好地优化排序代码(如果我没记错的话,也是 part 之所以有如此多的std算法,例如std::sort()]],通常有这样的淫秽性能)。但是,虽然时间我注意到调用排序功能的上下文(即周围代码)对性能有重大影响,这可能是由于函数是内联然后优化。例如,如果程序足够简单,那么通过排序函数指针与传递迭代器之间的性能通常没有太大差别;否则使用迭代器通常会导致明显更好的性能,并且从未(至少在我的经验中)至少表现出明显更差的性能。我怀疑这可能是因为g ++可以全局优化足够简单的代码。


此外,sort6_iterator() 一些次(再次,取决于调用函数的上下文)始终优于以下排序函数:


template 
inline void sort6_iterator_local(IterType it) 
{
#define SWAP(x,y) { const auto a = MIN(data##x, data##y); \
  const auto b = MAX(data##x, data##y); \
  data##x = a; data##y = b; }
//DD = Define Data
#define DD1(a)   auto data##a = *(it + a);
#define DD2(a,b) auto data##a = *(it + a), data##b = *(it + b);
//CB = Copy Back
#define CB(a) *(it + a) = data##a;

  DD2(1,2)    SWAP(1, 2)
  DD2(4,5)    SWAP(4, 5)
  DD1(0)      SWAP(0, 2)
  DD1(3)      SWAP(3, 5)
  SWAP(0, 1)  SWAP(3, 4)
  SWAP(1, 4)  SWAP(0, 3)   CB(0)
  SWAP(2, 5)  CB(5)
  SWAP(1, 3)  CB(1)
  SWAP(2, 4)  CB(4)
  SWAP(2, 3)  CB(2)        CB(3)
#undef CB
#undef DD2
#undef DD1
#undef SWAP
}


请注意,将SWAP()定义为以下一些次会导致性能稍好一些,但大多数情况下会导致性能稍差或性能差异可忽略不计。


#define SWAP(x,y) { const auto a = MIN(data##x, data##y); \
  data##y = MAX(data##x, data##y); \
  data##x = a; }


如果您只是想要一个排序算法,gcc -O3始终擅长优化,那么根据您传递输入的方式,尝试以下两种算法之一:


template inline void sort6(T it) {
#define SORT2(x,y) {if(data##x>data##y){auto a=std::move(data##y);data##y=std::move(data##x);data##x=std::move(a);}}
#define DD1(a)   register auto data##a=*(it+a);
#define DD2(a,b) register auto data##a=*(it+a);register auto data##b=*(it+b);
#define CB1(a)   *(it+a)=data##a;
#define CB2(a,b) *(it+a)=data##a;*(it+b)=data##b;
  DD2(1,2) SORT2(1,2)
  DD2(4,5) SORT2(4,5)
  DD1(0)   SORT2(0,2)
  DD1(3)   SORT2(3,5)
  SORT2(0,1) SORT2(3,4) SORT2(2,5) CB1(5)
  SORT2(1,4) SORT2(0,3) CB1(0)
  SORT2(2,4) CB1(4)
  SORT2(1,3) CB1(1)
  SORT2(2,3) CB2(2,3)
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}


要么


template inline void sort6(T& e0, T& e1, T& e2, T& e3, T& e4, T& e5) {
#define SORT2(x,y) {if(data##x>data##y)std::swap(data##x,data##y);}
#define DD1(a)   register auto data##a=e##a;
#define DD2(a,b) register auto data##a=e##a;register auto data##b=e##b;
#define CB1(a)   e##a=data##a;
#define CB2(a,b) e##a=data##a;e##b=data##b;
  DD2(1,2) SORT2(1,2)
  DD2(4,5) SORT2(4,5)
  DD1(0)   SORT2(0,2)
  DD1(3)   SORT2(3,5)
  SORT2(0,1) SORT2(3,4) SORT2(2,5) CB1(5)
  SORT2(1,4) SORT2(0,3) CB1(0)
  SORT2(2,4) CB1(4)
  SORT2(1,3) CB1(1)
  SORT2(2,3) CB2(2,3)
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}


使用register关键字的原因是因为这是您知道在寄存器中需要这些值的少数几次之一。如果没有register,编译器会在大多数情况下解决这个问题,但有时它并没有。使用register关键字有助于解决这个问题。但是,通常情况下,不要使用register]]关键字,因为它更有可能减慢你的代码而不是加速它。


另外,请注意模板的使用。这是有目的的,因为即使使用inline关键字,模板函数通常通过gcc比vanilla C函数更积极地进行优化(这与gcc需要处理vanilla C函数的函数指针有关,但不是带模板功能)。

其它参考17


我知道这是一个老问题。


但我刚刚写了一篇我想分享的不同解决方案。

只使用嵌套的MIN MAX,


它并不快,因为它使用了114个,

可以简单地将它减少到75 - > pastebin [90]


但那时它不再是纯粹的最大值。


可能有效的方法是使用AVX一次对多个整数执行min/max


PMINSW参考[91]


#include 

static __inline__ int MIN(int a, int b){
int result =a;
__asm__ ("pminsw %1, %0" : "+x" (result) : "x" (b));
return result;
}
static __inline__ int MAX(int a, int b){
int result = a;
__asm__ ("pmaxsw %1, %0" : "+x" (result) : "x" (b));
return result;
}
static __inline__ unsigned long long rdtsc(void){
  unsigned long long int x;
__asm__ volatile (".byte 0x0f, 0x31" :
  "=A" (x));
  return x;
}

#define MIN3(a, b, c) (MIN(MIN(a,b),c))
#define MIN4(a, b, c, d) (MIN(MIN(a,b),MIN(c,d)))

static __inline__ void sort6(int * in) {
  const int A=in[0], B=in[1], C=in[2], D=in[3], E=in[4], F=in[5];

  in[0] = MIN( MIN4(A,B,C,D),MIN(E,F) );

  const int
  AB = MAX(A, B),
  AC = MAX(A, C),
  AD = MAX(A, D),
  AE = MAX(A, E),
  AF = MAX(A, F),
  BC = MAX(B, C),
  BD = MAX(B, D),
  BE = MAX(B, E),
  BF = MAX(B, F),
  CD = MAX(C, D),
  CE = MAX(C, E),
  CF = MAX(C, F),
  DE = MAX(D, E),
  DF = MAX(D, F),
  EF = MAX(E, F);

  in[1] = MIN4 (
  MIN4( AB, AC, AD, AE ),
  MIN4( AF, BC, BD, BE ),
  MIN4( BF, CD, CE, CF ),
  MIN3( DE, DF, EF)
  );

  const int
  ABC = MAX(AB,C),
  ABD = MAX(AB,D),
  ABE = MAX(AB,E),
  ABF = MAX(AB,F),
  ACD = MAX(AC,D),
  ACE = MAX(AC,E),
  ACF = MAX(AC,F),
  ADE = MAX(AD,E),
  ADF = MAX(AD,F),
  AEF = MAX(AE,F),
  BCD = MAX(BC,D),
  BCE = MAX(BC,E),
  BCF = MAX(BC,F),
  BDE = MAX(BD,E),
  BDF = MAX(BD,F),
  BEF = MAX(BE,F),
  CDE = MAX(CD,E),
  CDF = MAX(CD,F),
  CEF = MAX(CE,F),
  DEF = MAX(DE,F);

  in[2] = MIN( MIN4 (
  MIN4( ABC, ABD, ABE, ABF ),
  MIN4( ACD, ACE, ACF, ADE ),
  MIN4( ADF, AEF, BCD, BCE ),
  MIN4( BCF, BDE, BDF, BEF )),
  MIN4( CDE, CDF, CEF, DEF )
  );


  const int
  ABCD = MAX(ABC,D),
  ABCE = MAX(ABC,E),
  ABCF = MAX(ABC,F),
  ABDE = MAX(ABD,E),
  ABDF = MAX(ABD,F),
  ABEF = MAX(ABE,F),
  ACDE = MAX(ACD,E),
  ACDF = MAX(ACD,F),
  ACEF = MAX(ACE,F),
  ADEF = MAX(ADE,F),
  BCDE = MAX(BCD,E),
  BCDF = MAX(BCD,F),
  BCEF = MAX(BCE,F),
  BDEF = MAX(BDE,F),
  CDEF = MAX(CDE,F);

  in[3] = MIN4 (
  MIN4( ABCD, ABCE, ABCF, ABDE ),
  MIN4( ABDF, ABEF, ACDE, ACDF ),
  MIN4( ACEF, ADEF, BCDE, BCDF ),
  MIN3( BCEF, BDEF, CDEF )
  );

  const int
  ABCDE= MAX(ABCD,E),
  ABCDF= MAX(ABCD,F),
  ABCEF= MAX(ABCE,F),
  ABDEF= MAX(ABDE,F),
  ACDEF= MAX(ACDE,F),
  BCDEF= MAX(BCDE,F);

  in[4]= MIN (
  MIN4( ABCDE, ABCDF, ABCEF, ABDEF ),
  MIN ( ACDEF, BCDEF )
  );

  in[5] = MAX(ABCDE,F);
}

int main(int argc, char ** argv) {
  int d[6][6] = {
    {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 (int i = 0; i < 6; i++) {
    sort6(d[i]);
  }
  cycles = rdtsc() - cycles;
  printf("Time is %d\n", (unsigned)cycles);

  for (int i = 0; i < 6; i++) {
    printf("d%d : %d %d %d %d %d %d\n", i,
     d[i][0], d[i][1], d[i][2],
     d[i][3], d[i][4], d[i][5]);
  }
}


编辑:点击
排名顺序解决方案受Rex Kerr的启发,
比上面的混乱快得多


static void sort6(int *o) {
const int 
A=o[0],B=o[1],C=o[2],D=o[3],E=o[4],F=o[5];
const unsigned char
AB = A>B, AC = A>C, AD = A>D, AE = A>E,
          BC = B>C, BD = B>D, BE = B>E,
                    CD = C>D, CE = C>E,
                              DE = D>E,
a =          AB + AC + AD + AE + (A>F),
b = 1 - AB      + BC + BD + BE + (B>F),
c = 2 - AC - BC      + CD + CE + (C>F),
d = 3 - AD - BD - CD      + DE + (D>F),
e = 4 - AE - BE - CE - DE      + (E>F);
o[a]=A; o[b]=B; o[c]=C; o[d]=D; o[e]=E;
o[15-a-b-c-d-e]=F;
}

其它参考18


也许我我迟到了,但至少我的贡献是新的方法。



  • 代码确实应该内联

  • 即使内联,也有太多分支

  • 分析部分基本上是O(N(N-1)),其对于N=6
  • 似乎是可以的
  • 如果swap 的成本会更高(compare的费用
  • ,代码会更有效
  • 我相信内联的静态函数。

  • 该方法与rank-sort有关


    • 而不是排名,使用相对排名(抵消)。

    • 任何排列组中每个周期的排名总和为零。

    • 而不是SWAP()两个元素,循环被追逐,只需要一个temp和一个(register-> register)swap(new< - old)。







更新:改了一下代码,有些人用C ++编译器来编译C代码......


#include 

#if WANT_CHAR
typedef signed char Dif;
#else
typedef signed int Dif;
#endif

static int walksort (int *arr, int cnt);
static void countdifs (int *arr, Dif *dif, int cnt);
static void calcranks(int *arr, Dif *dif);

int wsort6(int *arr);

void do_print_a(char *msg, int *arr, unsigned cnt)
{
fprintf(stderr,"%s:", msg);
for (; cnt--; arr++) {
        fprintf(stderr, " %3d", *arr);
        }
fprintf(stderr,"\n");
}

void do_print_d(char *msg, Dif *arr, unsigned cnt)
{
fprintf(stderr,"%s:", msg);
for (; cnt--; arr++) {
        fprintf(stderr, " %3d", (int) *arr);
        }
fprintf(stderr,"\n");
}

static void inline countdifs (int *arr, Dif *dif, int cnt)
{
int top, bot;

for (top = 0; top < cnt; top++ ) {
        for (bot = 0; bot < top; bot++ ) {
                if (arr[top] < arr[bot]) { dif[top]--; dif[bot]++; }
                }
        }
return ;
}
        /* Copied from RexKerr ... */
static void inline calcranks(int *arr, Dif *dif){

dif[0] =     (arr[0]>arr[1])+(arr[0]>arr[2])+(arr[0]>arr[3])+(arr[0]>arr[4])+(arr[0]>arr[5]);
dif[1] = -1+ (arr[1]>=arr[0])+(arr[1]>arr[2])+(arr[1]>arr[3])+(arr[1]>arr[4])+(arr[1]>arr[5]);
dif[2] = -2+ (arr[2]>=arr[0])+(arr[2]>=arr[1])+(arr[2]>arr[3])+(arr[2]>arr[4])+(arr[2]>arr[5]);
dif[3] = -3+ (arr[3]>=arr[0])+(arr[3]>=arr[1])+(arr[3]>=arr[2])+(arr[3]>arr[4])+(arr[3]>arr[5]);
dif[4] = -4+ (arr[4]>=arr[0])+(arr[4]>=arr[1])+(arr[4]>=arr[2])+(arr[4]>=arr[3])+(arr[4]>arr[5]);
dif[5] = -(dif[0]+dif[1]+dif[2]+dif[3]+dif[4]);
}

static int walksort (int *arr, int cnt)
{
int idx, src,dst, nswap;

Dif difs[cnt];

#if WANT_REXK
calcranks(arr, difs);
#else
for (idx=0; idx < cnt; idx++) difs[idx] =0;
countdifs(arr, difs, cnt);
#endif
calcranks(arr, difs);

#define DUMP_IT 0
#if DUMP_IT
do_print_d("ISteps ", difs, cnt);
#endif

nswap = 0;
for (idx=0; idx < cnt; idx++) {
        int newval;
        int step,cyc;
        if ( !difs[idx] ) continue;
        newval = arr[idx];
        cyc = 0;
        src = idx;
        do      {
                int oldval;
                step = difs[src];
                difs[src] =0;
                dst = src + step;
                cyc += step ;
                if(dst == idx+1)idx=dst;
                oldval = arr[dst];
#if (DUMP_IT&1)
                fprintf(stderr, "[Nswap=%d] Cyc=%d Step=%2d Idx=%d  Old=%2d New=%2d #### Src=%d Dst=%d[%2d]->%2d <-- %d\n##\n"
                        , nswap, cyc, step, idx, oldval, newval
                        , src, dst, difs[dst], arr[dst]
                        , newval  );
                do_print_a("Array ", arr, cnt);
                do_print_d("Steps ", difs, cnt);
#endif

                arr[dst] = newval;
                newval = oldval;
                nswap++;
                src = dst;
                } while( cyc);
        }

return nswap;
}
/*************/
int wsort6(int *arr)
{
return walksort(arr, 6);
}

其它参考19


好吧,如果它只有6个元素并且你可以利用并行性,想要最小化条件分支等等。为什么你不生成所有组合并测试订单?我想在一些架构中冒险,它可以非常快(只要你预先分配内存)

其它参考20


尝试合并排序列表排序。 :)使用两个数组。最快的小型和大型阵列。

如果你结束,你只检查插入的位置。您不需要比较的其他更大的值(cmp=a-b> 0)。

对于4个数字,您可以使用系统4-5 cmp(~4.6)或3-6 cmp(~4.9)。冒泡排序使用6 cmp(6)。大量慢速代码的cmp很多。

此代码使用5 cmp(不是MSL排序):

if (cmp(arr[n][i+0],arr[n][i+1])>0) {swap(n,i+0,i+1);} if (cmp(arr[n][i+2],arr[n][i+3])>0) {swap(n,i+2,i+3);} if (cmp(arr[n][i+0],arr[n][i+2])>0) {swap(n,i+0,i+2);} if (cmp(arr[n][i+1],arr[n][i+3])>0) {swap(n,i+1,i+3);} if (cmp(arr[n][i+1],arr[n][i+2])>0) {swap(n,i+1,i+2);}


主要MSL 9 8 7 6 5 4 3 2 1 0 89 67 45 23 01 ... concat two sorted lists, list length = 1 6789 2345 01 ... concat two sorted lists, list length = 2 23456789 01 ... concat two sorted lists, list length = 4 0123456789 ... concat two sorted lists, list length = 8


js代码




function sortListMerge_2a(cmp)	
{
var step, stepmax, tmp, a,b,c, i,j,k, m,n, cycles;
var start = 0;
var end   = arr_count;
//var str = '';
cycles = 0;
if (end>3)
	{
	stepmax = ((end - start + 1) >> 1) << 1;
	m = 1;
	n = 2;
	for (step=1;step0)
					{arr[n][k] = arr[m][j]; j++; k++;}
				else	{arr[n][k] = arr[m][i]; i++; k++;}
				}
			while (i



使用cmp == 0对4个项目进行排序。
cmp的数量是~4.34(FF原生有~4.52),但是比合并列表需要3倍的时间。但是,如果你有大数字或大文本,那么更少的cmp操作。
编辑:修复错误


在线测试http://mlich.zam.slu.cz/js-sort/x-sort-x2.htm [92]


function sort4DG(cmp,start,end,n) // sort 4
{
var n     = typeof(n)    !=='undefined' ? n   : 1;
var cmp   = typeof(cmp)  !=='undefined' ? cmp   : sortCompare2;
var start = typeof(start)!=='undefined' ? start : 0;
var end   = typeof(end)  !=='undefined' ? end   : arr[n].length;
var count = end - start;
var pos = -1;
var i = start;
var cc = [];
// stabilni?
cc[01] = cmp(arr[n][i+0],arr[n][i+1]);
cc[23] = cmp(arr[n][i+2],arr[n][i+3]);
if (cc[01]>0) {swap(n,i+0,i+1);}
if (cc[23]>0) {swap(n,i+2,i+3);}
cc[12] = cmp(arr[n][i+1],arr[n][i+2]);
if (!(cc[12]>0)) {return n;}
cc[02] = cc[01]==0 ? cc[12] : cmp(arr[n][i+0],arr[n][i+2]);
if (cc[02]>0)
    {
    swap(n,i+1,i+2); swap(n,i+0,i+1); // bubble last to top
    cc[13] = cc[23]==0 ? cc[12] : cmp(arr[n][i+1],arr[n][i+3]);
    if (cc[13]>0)
        {
        swap(n,i+2,i+3); swap(n,i+1,i+2); // bubble
        return n;
        }
    else    {
    cc[23] = cc[23]==0 ? cc[12] : (cc[01]==0 ? cc[30] : cmp(arr[n][i+2],arr[n][i+3]));  // new cc23 | c03 //repaired
        if (cc[23]>0)
            {
            swap(n,i+2,i+3);
            return n;
            }
        return n;
        }
    }
else    {
    if (cc[12]>0)
        {
        swap(n,i+1,i+2);
        cc[23] = cc[23]==0 ? cc[12] : cmp(arr[n][i+2],arr[n][i+3]); // new cc23
        if (cc[23]>0)
            {
            swap(n,i+2,i+3);
            return n;
            }
        return n;
        }
    else    {
        return n;
        }
    }
return n;
}

其它参考21


以下是三种典型的排序方法,它们代表三种不同的排序算法:


Insertion Sort: Θ(n^2)

Heap Sort: Θ(n log n)

Count Sort: Θ(3n)


但请查看Stefan Nelsson关于最快排序算法的讨论?在那里他讨论一个解决方案,直到O(n log log n) ..检查它在C [93] [94]中的实现


这种半线性排序算法于1995年由一篇论文提出:


甲。 Andersson,T。Hagerup,S。Nilsson和R. Raman。按线性排序
时间?在第27届ACM理论研讨会论文集中
计算,第427-436页,1995年。