回答另一个Stack Overflow问题（this one）我偶然发现了一个有趣的子问题。排序6个整数数组的最快方法是什么？
由于问题是非常低的水平：
&&或||中序列点后面的那些）。真的这个问题是一种高尔夫，其目标不是最小化源长度而是执行时间。我把它称为'Zening'代码，用于Zen of Code optimization及其Michael Abrash的书sequels的标题中。
至于为什么它很有趣，有几个层次：
这是我的参考（天真的，未优化的）实现和我的测试集。
#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);
}
随着变种的数量变得越来越大，我将它们全部收集在一个可以找到here的测试套件中。由于Kevin Stock，所使用的实际测试比上面显示的要少一些。您可以在自己的环境中编译和执行它。我对不同目标架构/编译器的行为很感兴趣。 （好的，把它放在答案中，我将为新结果集的每个贡献者+1）。
一年前我给了Daniel Stutzbach（打高尔夫球）的答案，因为当时他是当时最快解决方案的来源（排序网络）。
Linux 64位，gcc 4.6.1 64位，Intel Core 2 Duo E8400，-O2
Linux 64位，gcc 4.6.1 64位，Intel Core 2 Duo E8400，-O1
我包括-O1和-O2结果，因为令人惊讶的是，对于几个程序，O2的效率低于O1。我想知道具体的优化有什么影响？
插入排序（Daniel Stutzbach）
正如所料，最小化分支确实是一个好主意。
排序网络（Daniel Stutzbach）
比插入排序更好。我想知道主要影响是不是来自避免外部循环。我试着通过展开的插入排序来检查，实际上我们得到大致相同的数字（代码是here）。
排序网络（Paul R）
到目前为止最好的。我用来测试的实际代码是here。不知道为什么它几乎是其他分拣网络实施的两倍。参数传递？最快？
使用快速交换对网络进行排序12 SWAP
正如Daniel Stutzbach所建议的那样，我将他的12交换排序网络与无分支快速交换（代码为here）相结合。它确实更快，是迄今为止最好的，利用少量掉期可以预期的小幅度（大约5％）。
值得注意的是，无分支交换似乎比使用PPC架构的简单交换（4倍）效率低。
调用库qsort
为了给出另一个参考点，我也按照建议尝试调用库qsort（代码是here）。正如预期的那样速度慢得多：慢了10到30倍......随着新测试套件变得明显，主要问题似乎是第一次调用后库的初始加载，并且它与其他调用的差别不大版。它在我的Linux上慢了3到20倍。在一些用于其他人测试的体系结构上，它似乎更快（我真的很惊讶，因为库qsort使用更复杂的API）。
排序
Rex Kerr提出了另一种完全不同的方法：对于数组的每个项目直接计算其最终位置。这是有效的，因为计算等级顺序不需要分支。这种方法的缺点是它需要三倍的数组内存量（数组的一个副本和存储排名顺序的变量）。性能结果非常令人惊讶（而且很有趣）。在我的32位操作系统和英特尔酷睿2四核E8300的参考架构上，循环计数略低于1000（就像分支交换的排序网络一样）。但是当我在我的64位盒（英特尔酷睿2双核处理器）上编译和执行时，它表现得更好：它成为目前为止最快的。我终于找到了真正的原因。我的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);t时，处理器可以并行执行。我尝试了它并按预期工作，排序网络的运行速度提高了约10％。
使用简单交换对网络12进行排序
在最初的帖子Steinar H. Gunderson建议的一年后，我们不应该试图超越编译器并保持交换代码简单。这确实是一个好主意，因为生成的代码快了大约40％！他还提出了使用x86内联汇编代码手动优化的交换，它仍然可以节省更多的周期。最令人惊讶的是（它说程序员心理学的卷）是一年前没有人用过这个版本的交换。我以前用来测试的代码是here。其他人提出了编写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个周期。我打电话的速度非常快。还有其他改进吗？
对于任何优化，最好是测试，测试和测试。我会尝试至少排序网络和插入排序。如果我在下注，我会根据过去的经验将我的钱放在插入排序上。
你对输入数据有什么了解吗？某些算法在某些类型的数据中表现更好。例如，插入排序在已排序或几乎排序的数据上表现更好，因此如果几乎排序数据的概率高于平均值，那么它将是更好的选择。
您发布的算法类似于插入排序，但看起来您已经以更多比较为代价减少了掉期数量。然而，比较远比交换更昂贵，因为分支可能导致指令管道停滞。
这是一个插入排序实现：
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;
}
}
这是我如何建立一个分拣网络。首先，使用this site为适当长度的网络生成一组最小的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
}
XOR交换在您的交换功能中可能很有用。
void xorSwap (int *x, int *y) {
if (*x != *y) {
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
}
if可能会导致您的代码过多分歧，但如果您保证所有的int都是唯一的，那么这可能很方便。
期待尝试这一点，并从这些例子中学习，但首先是我的1.5 GHz PPC Powerbook G4 w / 1 GB DDR RAM的一些时序。 （我从http://www.mcs.anl.gov/~kazutomo/rdtsc.html为PPC借用了一个类似rdtsc的计时器作为计时。）我运行了几次程序，绝对结果各不相同，但始终最快的测试是“插入排序（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
以下是我对此主题的贡献：针对包含唯一值的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<a) break;
*cp=a;
*(cp+1)=c;
cp-=1;
c=*cp;
} while (cp>=valp);
ip+=1;
cp=ip;
} while (ip<ep);
}
在配备双核Athlon M300 @ 2 Ghz（DDR2内存）的HP dv7-3010so笔记本电脑上，它可在165个时钟周期内执行。这是从每个唯一序列的时间计算的平均值（总共6！/ 720）。使用OpenWatcom 1.8编译为Win32。循环本质上是一种插入排序，长度为16条指令/ 37字节。
我没有要编译的64位环境。
如果插入排序在这里相当有竞争力，我建议尝试一个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和分拣网络（计算机科学中的杰出论文）。花环。 ISBN 0-824-04406-1
我知道我已经很晚了，但我有兴趣尝试一些不同的解决方案。首先，我清理了该粘贴，使其编译，并将其放入存储库。我把一些不受欢迎的解决方案作为死胡同，以便其他人不会尝试。其中包括我的第一个解决方案，它试图确保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计算索引，然后我必须制作一个索引表。这是因为计算是基于目标而不是基于源的。见Converting from Source-based Indices to Destination-based Indices
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/
这个问题变得很老了，但实际上我现在必须解决同样的问题：快速算法来排序小数组。我认为分享我的知识是个好主意。当我第一次开始使用排序网络时，我终于设法找到其他算法，其中执行的比较总数对6个值的每个排列进行排序小于排序网络，并且小于插入排序。我没有计算掉期数量;我希望它大致相当（有时可能会高一点）。
算法sort6使用算法sort4，它使用算法sort3。下面是一些轻量级C ++形式的实现（原始模板很重，因此可以使用任何随机访问迭代器和任何合适的比较函数）。
以下算法是展开的插入排序。当必须执行两次交换（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个赋值来对这三个值进行排序。
这个调用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次交换。展开插入排序很容易，但我们将使用另一种算法进行最后一次排序...
这个使用我称之为双插入排序的展开版本。这个名字不是那么好，但它很具描述性，以下是它的工作原理：
在交换之后，第一个元素总是小于最后一个元素，这意味着，当将它们插入到排序序列中时，在最坏的情况下插入两个元素将不会有多于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。
我希望这有帮助，即使这个问题可能不再代表实际问题:)
编辑：在将其放入提供的基准测试之后，它比大多数有趣的替代品更加清晰。它往往比展开的插入排序更好一点，但这就是它。基本上，它不是整数的最佳排序，但对于具有昂贵比较操作的类型可能是有趣的。
我相信你的问题分为两部分。
我不会太担心清空管道（假设当前的x86）：分支预测已经走过了漫长的道路。我担心的是确保代码和数据分别适合一个缓存行（代码可能是两个）。一旦获取延迟低得令人耳目一新，这将弥补任何失速。这也意味着你的内部循环可能是10个指令左右它应该在哪里（在我的排序算法中有两个不同的内部循环，它们分别是10个指令/ 22个字节和9/22个长）。假设代码中不包含任何div，您可以确定它的速度非常快。
我知道这是一个老问题。
但我刚刚写了一篇我想分享的不同解决方案。 只使用嵌套的MIN MAX，
它并不快，因为它使用了114个， 可以简单地将它减少到75 - > pastebin
但那时它不再是纯粹的最大值。
可能有效的方法是使用AVX一次对多个整数执行min / max
#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]);
}
}
编辑： 排名顺序解决方案受到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;
}
我发现，至少在我的系统中，下面定义的函数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 ++更好地优化排序代码（如果我记得没错，也是为什么这么多std算法，如std::sort()，一般都有这样的淫秽性能的部分原因）。然而，虽然时间我注意到调用排序函数的上下文（即周围代码）对性能有显着影响，这可能是由于函数被内联然后优化。例如，如果程序足够简单，那么将排序函数传递给指针与传递迭代器之间的性能通常没有太大差别;否则使用迭代器通常会导致明显更好的性能，而且（至少在我的经验中）至少没有任何明显更差的性能。我怀疑这可能是因为g ++可以全局优化足够简单的代码。
此外，sort6_iterator()有时（再次，取决于函数被调用的上下文）始终优于以下排序函数，该函数在排序之前将数据复制到局部变量中：
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()有时会导致稍微好一点的性能，尽管大多数时候它会导致性能稍差或性能差异可以忽略不计。
#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<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而不是vanilla C函数进行更积极的优化（这与gcc需要处理vanilla C函数的函数指针而不是模板函数有关） 。
尝试'合并排序列表'排序。 :)使用两个数组。最快的小型和大型阵列。
如果你结束，你只检查插入的位置。您不需要比较的其他更大的值（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;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;
}
}这是使用sorting networks的实现：
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 - 无分支，没有扭曲分歧等问题）。
使用cmp == 0对4个项目进行排序。 cmp的数量是~4.34（FF原生有~4.52），但是比合并列表需要3倍的时间。但是如果你有大数字或大文本，那么更少的cmp操作。编辑：修复错误
在线测试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;
}
也许我迟到了，但至少我的贡献是一种新方法。
swap的成本会更高（qrtxswpoi的成本），代码可能会更有效compareing两个元素，循环被追逐，只需要一个临时，和一个（寄存器 - >寄存器）交换（新更新：改了一下代码，有些人用C ++编译器来编译C代码......
SWAP()#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);
}
好吧，如果它只有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
}
但请查看Insertion Sort: Θ(n^2)
Heap Sort: Θ(n log n)
Count Sort: Θ(3n)
，在那里他讨论一个解决方案，直到Stefan Nelsson discussion on the fastest sorting algorithm? ..查看O(n log log n)
这种半线性排序算法于1995年由一篇论文提出：
A. Andersson，T。Hagerup，S。Nilsson和R. Raman。按线性时间排序？在第27届ACM计算机理论研讨会论文集，第427-436页，1995年。
由于这些是整数并且比较快，为什么不直接计算每个的排名顺序：
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];
}
看起来我迟到了一年，但在这里我们去......
看一下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 <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;
}
我更改了modified the test suite以报告每种类型的时钟并运行更多测试（cmp函数也更新以处理整数溢出），这里是一些不同架构的结果。我尝试在AMD CPU上进行测试，但是在我可用的X6 1100T上rdtsc不可靠。
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
几天前我偶然发现了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中执行此操作的说明，您可以阅读this article。您可以使用以下C原型从C代码调用该函数：
void simd_sort_6(char *values);
测试代码非常糟糕;它溢出了初始数组（这里没有人读过编译器警告吗？），printf打印出错误的元素，它使用.byte为rdtsc没有充分理由，只有一次运行（！），没有什么检查最终结果实际上是正确的（因此很容易“优化”成微妙错误的东西），包含的测试非常简陋（没有负数？）并且没有什么可以阻止编译器将整个函数作为死代码丢弃。
话虽这么说，改进比特网络解决方案也很容易;只需将最小/最大/ 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）。
虽然我真的很喜欢提供的交换宏：
#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如何工作并明确地拉出公共子表达式。这完全消除了最小和最大宏。
在没有基准测试并查看实际编译器生成的程序集的情如果我让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条）。例如，这是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
对于六个元素，插入排序与排序网络竞争（12次交换与15次迭代平衡4次指令/交换与3次指令/迭代）;冒泡当然比较慢。但是当尺寸增大时，它不会成立，因为插入排序是O（n ^ 2），而排序网络是O（n log n）。
我将测试套件移植到我无法识别的PPC架构机器上（不必触摸代码，只需增加测试的迭代次数，使用8个测试用例来避免使用mods污染结果并替换x86特定的rdtsc）：
直接调用qsort库函数：101
天真的实现（插入排序）：299
插入排序（Daniel Stutzbach）：108
插入排序已展开：51
排序网络（Daniel Stutzbach）：26
排序网络（Paul R）：85
使用快速交换对网络12进行排序：117
排序网络12重新排序交换：116
排名顺序：56