最快的固定长度6 int数组排序

在回答另一个堆栈溢出问题(这一个)时，我偶然发现了一个有趣的子问题。对6个整数的数组进行排序的最快方法是什么?

因为问题层次很低:

  • 我们不能假设库是可用的(而且调用本身也有开销)，只有纯C
  • 为了避免清空指令管道(具有非常的高成本)，我们可能应该最小化分支、跳转和其他类型的控制流中断(如隐藏在&&或||序列点后面的那些)。
  • 空间是有限的，最小化寄存器和内存的使用是一个问题，理想情况下，就地排序可能是最好的。

实际上，这个问题是一种Golf，其目标不是最小化源长度，而是最小化执行时间。我称其为“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],
       *  d[i][8], d[i][9], d[i][10]);
        */
    }
    cycles = rdtsc() - cycles;
    printf("Time is %d\n", (unsigned)cycles);
}

生的结果

随着变量的数量越来越大，我把它们都收集到一个测试套件中，可以找到在这里。在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
  • 重排序网络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有效少。我想知道什么具体的优化有这种效果?

对建议解决方案的评论

插入排序(丹尼尔·斯图茨巴赫)

正如预期的那样，最小化分支确实是一个好主意。

排序网络(丹尼尔·斯图茨巴赫)

比插入排序好。我想知道主要的效果是不是避免外部循环。我尝试通过展开插入排序来检查，确实我们得到了大致相同的数字(代码是在这里)。

排序网络(保罗R)

迄今为止最好的。我用来测试的实际代码是在这里。目前还不知道为什么它的速度几乎是其他排序网络实现的两倍。参数传递?快速max ?

排序网络12 SWAP与快速交换

根据Daniel Stutzbach的建议，我将他的12交换排序网络与无分支快速交换(代码为在这里)结合起来。它确实更快，到目前为止最好的，只有很小的利润率(大约5%)，因为可以使用更少的交换。

同样有趣的是，无分支交换似乎比在PPC架构上使用if的简单交换效率低得多(4倍)。

调用库qsort

为了提供另一个参考点，我还尝试按建议调用库qsort(代码是在这里)。正如预期的那样，它要慢得多:慢了10到30倍……随着新测试套件的出现，主要问题似乎是第一次调用后库的初始负载，与其他版本相比，它并没有那么差。它在我的Linux上只慢了3到20倍。在其他人用于测试的某些架构上，它似乎更快(我真的很惊讶，因为库qsort使用了更复杂的API)。

等级次序

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

更新:

正如上面公布的数字所示，这种效果在gcc的后续版本中仍然得到了增强，Rank Order的速度始终是其他任何替代版本的两倍。

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

Rex Kerr提议的gcc 4.4.3惊人的效率让我好奇:一个内存使用量是无分支排序网络3倍的程序怎么可能比它更快呢?我的假设是，它具有更少的写后读依赖性，允许更好地使用x86的超标量指令调度程序。这给了我一个想法:重新排序交换以最小化读写依赖。更简单地说:当你执行SWAP(1, 2); SWAP(0, 2);时，你必须在执行第二次交换之前等待第一次交换完成，因为两者都访问一个公共的内存单元。当你执行__abc1时，处理器可以并行执行。我试了一下，结果和预期的一样，排序网络的运行速度快了10%。

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

在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个周期。我称之为惊人的快。还有其他可能的改进吗?

79497 次浏览
小开

下面是一个使用排序网络的实现:

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 -无分支，不存在扭曲发散等问题)。

参见:快速算法实现排序非常小的列表

小开
最佳答案

对于任何优化，最好的方法总是测试、测试、测试。我至少会尝试网络排序和插入排序。如果我要打赌，我会根据过去的经验把钱押在插入排序上。

你知道输入数据吗?某些算法在处理特定类型的数据时会表现得更好。例如，插入排序在已排序或几乎已排序的数据上执行得更好，因此如果几乎已排序的数据的概率高于平均水平，则插入排序将是更好的选择。

您发布的算法类似于插入排序，但看起来您以更多比较为代价最小化了交换的数量。但是，比较的代价要比交换高得多，因为分支会导致指令管道暂停。

这是一个插入排序实现:

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

异或交换在交换函数中可能很有用。

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

if可能会在代码中导致太多的分歧，但如果你能保证所有int都是唯一的，这可能会很方便。

小开

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

__abc0: 101

__abc0: 299

__abc0: 108

__abc0: 51

__abc0: 26

__abc0: 85

__abc0: 117

__abc0: 116

__abc0: 56

小开

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

#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是如何工作的，并显式地提取公共子表达式。这完全消除了min和max宏。

小开

如果插入排序在这里是合理的竞争，我建议尝试shell排序。我担心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个元素的问题，谁知道呢……

根据维基百科，这甚至可以与排序网络相结合: 普拉特，V(1979)。贝壳排序和排序网络(计算机科学杰出论文)。花环。ISBN 0-824-04406-1 < / em >

小开

如果它只有6个元素，你可以利用并行性，想要最小化条件分支等等。为什么不生成所有的组合并测试顺序?我敢说，在某些架构中，它可以非常快(只要你预先分配了内存)

小开

看来我迟到了一年，但我们开始吧…

查看gcc 4.5.2生成的程序集，我注意到每次交换都要进行加载和存储，这实际上是不需要的。最好是将这6个值加载到寄存器中，对它们进行排序，然后将它们存储回内存中。我命令商店的装载尽可能靠近寄存器首先需要和最后使用的地方。我还使用了Steinar H. Gunderson的SWAP宏。更新:我切换到Paolo Bonzini的SWAP宏，gcc将其转换为类似于Gunderson的东西，但gcc能够更好地排序指令，因为它们不是显式的汇编。

我使用与重新排序的交换网络相同的交换顺序，尽管可能有更好的顺序。如果我有更多的时间，我会生成并测试一堆排列。

我修改了测试代码，考虑超过4000个数组，并显示排序每个数组所需的平均周期数。在i5-650上，我得到~34.1循环/排序(使用-O3)，相比之下，原始的重新排序网络得到~65.3循环/排序(使用-O1，击败-O2和-O3)。

#include <stdio.h>


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上不可靠。

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
小开

测试代码非常糟糕;它溢出了初始数组(这里的人没有阅读编译器警告吗?)，printf打印出了错误的元素，它为RDTSC使用了.byte，没有任何理由，只有一次运行(!)，没有任何检查最终结果实际上是正确的(所以很容易“优化”成一些微妙的错误)，包含的测试非常基本(没有负数?)，没有任何东西可以阻止编译器将整个函数作为死代码丢弃。

话虽如此，改进二进制网络解决方案也很容易;简单地改变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)。

小开

永远不要在没有基准测试和查看实际编译器生成的程序集的情况下优化min/max。如果我让GCC用条件移动指令优化最小值，我得到了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 vs. 420)。用?:做max或多或少是一样的，几乎淹没在噪音中，但上面的速度稍微快一点。这个SWAP在GCC和Clang中都更快。

编译器在寄存器分配和别名分析方面也做得很出色，有效地将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条指令)。例如，下面是ARM汇编中的t = d[2]; ITER(1); ITER(0);行:

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

对于6个元素，插入排序与排序网络竞争(12次交换vs. 15次迭代平衡4条指令/交换vs. 3条指令/迭代);泡沫当然要慢一些。但当大小增加时就不成立了，因为插入排序是O(n²)而排序网络是O(n log n)。

小开

期待着尝试这一点，并从这些例子中学习，但首先要从我的1.5 GHz PPC Powerbook G4 w/ 1 GB DDR RAM中进行一些计时。(我从http://www.mcs.anl.gov/~kazutomo/rdtsc.html中借用了一个类似于rdtsc的PPC定时器来计时。)我运行了几次程序，绝对结果各不相同，但始终最快的测试是“插入排序(Daniel Stutzbach)”，“插入排序展开”紧随其后。

下面是最后一组时间:

**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
小开

我认为你的问题有两个方面。

  • 首先是确定最优算法。至少在这种情况下，这是通过遍历每个可能的排序(没有那么多)来完成的，这允许您计算比较和交换的精确的最小值，最大值，平均值和标准偏差。手边也有一两个亚军。
  • 二是优化算法。可以做很多工作来将教科书上的代码示例转换为真实且精简的算法。如果你意识到一种算法不能优化到所需的程度，试试第二种算法。

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

小开

这是我对这个线程的贡献:一个包含唯一值的6成员int向量(valp)的优化1,4间隙壳排序。

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<a) break;


*cp=a;
*(cp+1)=c;
cp-=1;
c=*cp;
} while (cp>=valp);
ip+=1;
cp=ip;
} while (ip<ep);
}

在我的惠普dv7-3010so笔记本电脑上，双核Athlon M300 @ 2 Ghz (DDR2内存)，它在165个时钟周期内执行。这是一个平均计算从计时每个独特的序列(6!/总共720)。使用OpenWatcom 1.8编译到Win32。这个循环本质上是一个插入排序，有16条指令/37字节长。

我没有一个64位的环境来编译。

小开

几天前，我无意中从谷歌中发现了这个问题，因为我还需要快速排序一个由6个整数组成的固定长度数组。然而，在我的情况下，我的整数只有8位(而不是32位)，我没有严格的要求只使用c。我想我无论如何都会分享我的发现，以防他们可能对某人有帮助……

我在程序集中实现了一个网络排序的变体，它使用SSE尽可能地向量化比较和交换操作。需要六次“传递”才能对数组进行完全排序。我使用了一种新颖的机制，直接将PCMPGTB(向量化比较)的结果转换为PSHUFB(向量化交换)的洗牌参数，只使用PADDB(向量化添加)，在某些情况下还使用PAND(位与)指令。

这种方法也有产生真正的无分支函数的副作用。没有任何跳跃指令。

似乎这个实现大约快38%比目前在问题中标记为最快选项的实现(“用简单交换排序网络12”)。我在测试期间修改了该实现，使用char数组元素，以使比较公平。

我应该指出，这种方法可以应用于任何大小不超过16个元素的数组。我希望在更大的数组中，相对于替代方案的速度优势会越来越大。

代码是用MASM编写的，适用于带有SSSE3的x86_64处理器。该函数使用“new”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代码中调用这个函数:

void simd_sort_6(char *values);
小开

这个问题已经很老了，但我最近也不得不解决同样的问题:用快速算法对小数组进行排序。我觉得分享我的知识是个好主意。当我开始使用排序网络时，我最终设法找到了其他算法，其中对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。

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

编辑:在将它放入提供的基准测试后，它明显比大多数有趣的替代方法要慢。它的性能往往比展开插入排序好一点，但也仅此而已。基本上，它不是整数的最佳排序，但对于具有昂贵比较操作的类型可能很有趣。

小开

我知道我来晚了，但我有兴趣尝试一些不同的解决方案。首先，我清理了该粘贴，使其编译，并将其放入存储库中。我把一些不受欢迎的解决方案作为死胡同，这样其他人就不会尝试了。其中有我的第一个解决方案，它试图确保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/

小开

尝试“合并排序列表”排序。:)使用两个数组。对于小数组和大数组，速度最快 如果你拼接，你只检查插入的位置。其他更大的值你不需要比较(cmp = a-b>0).
对于4个号码，您可以使用系统4-5 cmp(~4.6)或3-6 cmp(~4.9)。冒泡排序使用6 cmp(6)。大量cmp的大数字慢代码。
这段代码使用5 cmp(不是MSL排序):
如果(cmp (arr [n][我+ 0],arr [n] [i + 1])在0){交换(n,我+ 0,+ 1);} 如果(cmp (arr [n] [i + 2], arr [n][我+ 3])在0){交换(n,我+ 2,+ 3);} 如果(cmp (arr [n][我+ 0],arr [n] [i + 2])在0){交换(n,我+ 0,+ 2);} 如果(cmp (arr [n] (i + 1), arr [n][我+ 3])在0){交换(n,我+ 1,+ 3);} 如果(cmp (arr [n] (i + 1), arr [n] [i + 2])在0){交换(n,我+ 1,+ 2);}< /代码> < / p > < p >原始的韩剧<代码> 9 8 7 6 5 4 3 2 10 0 89 67 45 23 01…Concat两个排序的列表，列表长度= 1 6789 2345 01…Concat两个排序的列表，列表长度= 2 23456789 01…Concat两个排序的列表，列表长度= 4 0123456789……Concat两个排序的列表，列表长度= 8 < /代码> < / p >

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;step<stepmax;step<<=1)	//bounds 1-1, 2-2, 4-4, 8-8...
{
a = start;
while (a<end)
{
b = a + step;
c = a + step + step;
b = b<end ? b : end;
c = c<end ? c : end;
i = a;
j = b;
k = i;
while (i<b && j<c)
{
if (cmp(arr[m][i],arr[m][j])>0)
{arr[n][k] = arr[m][j]; j++; k++;}
else	{arr[n][k] = arr[m][i]; i++; k++;}
}
while (i<b)
{arr[n][k] = arr[m][i]; i++; k++;
}
while (j<c)
{arr[n][k] = arr[m][j]; j++; k++;
}
a = c;
}
tmp = m; m = n; n = tmp;
}
return m;
}
else
{
// sort 3 items
sort10(cmp);
return m;
}
}

小开

排序使用cmp==0的4个条目。 cmp的数量是~4.34 (FF原生的有~4.52)，但是比合并列表花费3倍的时间。但如果你有大数字或大文本，最好少做cmp操作。 编辑:修复bug

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

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;
}
小开

我发现至少在我的系统上，下面定义的函数sort6_iterator()和sort6_iterator_local()都运行得至少和上面的当前记录保持者一样快，而且经常明显更快:

#define MIN(x, y) (x<y?x:y)
#define MAX(x, y) (x<y?y:x)


template<class IterType>
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++更好地优化排序代码(例如，对于指针，编译器不能确保所有指针都指向不同的内存位置)。如果我没记错的话，这也是为什么这么多STL算法(比如std::sort())通常具有如此出色的性能的原因之一。

此外，sort6_iterator()是__abc1倍(同样，取决于调用该函数的上下文)，始终优于以下排序函数，该排序函数在排序之前将数据复制到局部变量中。1注意，由于只定义了6个局部变量，如果这些局部变量是原语，那么它们可能永远不会实际存储在RAM中，而是只存储在CPU的寄存器中，直到函数调用结束，这有助于使这个排序函数更快。(这也有助于编译器知道不同的局部变量在内存中有不同的位置)。

template<class IterType>
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()如下一些times会导致稍微更好的性能，尽管大多数时候它会导致稍微更差的性能或可以忽略的性能差异。

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

如果你只是想要一个排序算法，在基本数据类型上，gcc -O3始终擅长优化，无论排序函数调用在__abc0中出现什么上下文，那么，根据你传递输入的方式，尝试以下两种算法之一:

template<class T> 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
}

或者如果你想通过引用传递变量，那么使用这个(下面的函数与上面的前5行不同):

template<class T> 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对模板函数的优化通常比普通C函数要积极得多(这与gcc需要处理普通C函数的函数指针而不是模板函数有关)。

  1. 在计时各种排序函数时，我注意到调用排序函数的上下文(即周围的代码)对性能有重大影响，这可能是由于函数被内联然后优化。例如，如果程序足够简单，那么传递给排序函数一个指针和传递给它一个迭代器在性能上通常没有太大区别;否则，使用迭代器通常会带来明显更好的性能，而不会(至少在我的经验中)明显更差的性能。我怀疑这可能是因为g++可以对简单的代码进行全局优化。
小开

我知道这是一个老问题。

但是我刚刚写了一个不同的解，我想和大家分享 只使用嵌套MIN MAX，

它不是很快，因为它每个使用114，
可以像这样简单地将其减少到75 -> pastebin

但它不再是单纯的最小最大值了。

什么可能工作是做最小/最大对多个整数一次与AVX

PMINSW参考

#include <stdio.h>


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]);
}
}
< p >编辑:< br > 受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;
}
小开

也许我我姗姗来迟，但至少我的贡献是一种新方法。

  • 代码真的应该内联
  • 即使是内联的，也有太多的分支
  • 分析部分基本上是O(N(N-1))，当N=6时似乎没问题
  • 如果swap的成本的成本更高(而不是compare的成本)，代码可能会更有效。
  • 我相信静态函数被内联。
  • 该方法与rank-sort有关
    • 而不是秩，使用相对秩(偏移量)。
    • 在任何排列组中，每个周期的秩和为零。
    • 而不是SWAP()ing两个元素，循环被跟踪，只需要一个temp和一个(寄存器->寄存器)swap (new <- old)。
      • 李< / ul > < / >

    更新:代码改动了一点，有些人用c++编译器编译C代码…

    #include <stdio.h>


#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);
}
小开 
//Bruteforce compute unrolled count dumbsort(min to 0-index)
void bcudc_sort6(int* a)
{
int t[6] = {0};
int r1,r2;


r1=0;
r1 += (a[0] > a[1]);
r1 += (a[0] > a[2]);
r1 += (a[0] > a[3]);
r1 += (a[0] > a[4]);
r1 += (a[0] > a[5]);
while(t[r1]){r1++;}
t[r1] = a[0];


r2=0;
r2 += (a[1] > a[0]);
r2 += (a[1] > a[2]);
r2 += (a[1] > a[3]);
r2 += (a[1] > a[4]);
r2 += (a[1] > a[5]);
while(t[r2]){r2++;}
t[r2] = a[1];


r1=0;
r1 += (a[2] > a[0]);
r1 += (a[2] > a[1]);
r1 += (a[2] > a[3]);
r1 += (a[2] > a[4]);
r1 += (a[2] > a[5]);
while(t[r1]){r1++;}
t[r1] = a[2];


r2=0;
r2 += (a[3] > a[0]);
r2 += (a[3] > a[1]);
r2 += (a[3] > a[2]);
r2 += (a[3] > a[4]);
r2 += (a[3] > a[5]);
while(t[r2]){r2++;}
t[r2] = a[3];


r1=0;
r1 += (a[4] > a[0]);
r1 += (a[4] > a[1]);
r1 += (a[4] > a[2]);
r1 += (a[4] > a[3]);
r1 += (a[4] > a[5]);
while(t[r1]){r1++;}
t[r1] = a[4];


r2=0;
r2 += (a[5] > a[0]);
r2 += (a[5] > a[1]);
r2 += (a[5] > a[2]);
r2 += (a[5] > a[3]);
r2 += (a[5] > a[4]);
while(t[r2]){r2++;}
t[r2] = a[5];


a[0]=t[0];
a[1]=t[1];
a[2]=t[2];
a[3]=t[3];
a[4]=t[4];
a[5]=t[5];
}


static __inline__ void sort6(int* a)
{
#define wire(x,y); t = a[x] ^ a[y] ^ ( (a[x] ^ a[y]) & -(a[x] < a[y]) ); a[x] = a[x] ^ t; a[y] = a[y] ^ t;
register int t;


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


#undef wire
}
小开
我想我应该尝试展开Ford-Johnson归并插入排序，它实现了尽可能少的比较数量(ceil(log2(6!)) = 10)并且没有交换。 不过，它没有竞争(我得到的时间比最糟糕的排序网络解决方案sort6_sorting_network_v1略好) 它将值加载到6个寄存器中，然后执行8到10个比较 来决定哪个720=6! 然后将寄存器写回相应的寄存器中 在这720个订单中(每种情况的代码单独)。 在最后的回写之前，没有任何交换或重新排序。我还没有查看生成的程序集代码 
static inline void sort6_ford_johnson_unrolled(int *D) {
register int a = D[0], b = D[1], c = D[2], d = D[3], e = D[4], f = D[5];
#define abcdef(a,b,c,d,e,f) (D[0]=a, D[1]=b, D[2]=c, D[3]=d, D[4]=e, D[5]=f)
#define abdef_cd(a,b,c,d,e,f) (c<a ? abcdef(c,a,b,d,e,f) \
: c<b ? abcdef(a,c,b,d,e,f) \
: abcdef(a,b,c,d,e,f))
#define abedf_cd(a,b,c,d,e,f) (c<b ? c<a ? abcdef(c,a,b,e,d,f) \
: abcdef(a,c,b,e,d,f) \
: c<e ? abcdef(a,b,c,e,d,f) \
: abcdef(a,b,e,c,d,f))
#define abdf_cd_ef(a,b,c,d,e,f) (e<b ? e<a ? abedf_cd(e,a,c,d,b,f) \
: abedf_cd(a,e,c,d,b,f) \
: e<d ? abedf_cd(a,b,c,d,e,f) \
: abdef_cd(a,b,c,d,e,f))
#define abd_cd_ef(a,b,c,d,e,f) (d<f ? abdf_cd_ef(a,b,c,d,e,f) \
: b<f ? abdf_cd_ef(a,b,e,f,c,d) \
: abdf_cd_ef(e,f,a,b,c,d))
#define ab_cd_ef(a,b,c,d,e,f) (b<d ? abd_cd_ef(a,b,c,d,e,f) \
: abd_cd_ef(c,d,a,b,e,f))
#define ab_cd(a,b,c,d,e,f) (e<f ? ab_cd_ef(a,b,c,d,e,f) \
: ab_cd_ef(a,b,c,d,f,e))
#define ab(a,b,c,d,e,f) (c<d ? ab_cd(a,b,c,d,e,f) \
: ab_cd(a,b,d,c,e,f))
a<b ? ab(a,b,c,d,e,f)
: ab(b,a,c,d,e,f);
#undef ab
#undef ab_cd
#undef ab_cd_ef
#undef abd_cd_ef
#undef abdf_cd_ef
#undef abedf_cd
#undef abdef_cd
#undef abcdef
}


TEST(ford_johnson_unrolled,   "Unrolled Ford-Johnson Merge-Insertion sort");

提交答案