kri*_*iss 396 sorting algorithm optimization gpgpu sorting-network
回答另一个Stack Overflow问题(这个)我偶然发现了一个有趣的子问题.排序6个整数数组的最快方法是什么？
由于问题是非常低的水平:
&&或||).真的这个问题是一种高尔夫,其目标不是最小化源长度而是执行时间.我把它叫做"Zening"代码在本书的标题中的代码优化禅由迈克尔·亚伯拉什及其续集.
至于为什么它很有趣,有几个层次:
这是我的参考(天真的,未优化的)实现和我的测试集.
#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
Linux 64位,gcc 4.6.1 64位,Intel Core 2 Duo E8400,-O1
我既包括-O1和-02的结果,因为出奇的好节目O2是少比O1效率.我想知道具体的优化有什么影响？
插入排序(Daniel Stutzbach)
正如所料,最小化分支确实是一个好主意.
排序网络(Daniel Stutzbach)
比插入排序更好.我想知道主要影响是不是来自避免外部循环.我通过展开的插入排序尝试检查,实际上我们得到大致相同的数字(代码在这里).
排序网络(Paul R)
到目前为止最好的.我以前测试的实际代码就在这里.不知道为什么它几乎是其他分拣网络实施的两倍.参数传递？最快？
使用快速交换对网络进行排序12 SWAP
正如Daniel Stutzbach所建议的那样,我将他的12交换排序网络与无分支快速交换相结合(代码在这里).它确实更快,是迄今为止最好的,利用少量掉期可以预期的小幅度(大约5%).
值得注意的是,无分支交换似乎比使用PPC架构的简单交换(4倍)效率低.
调用库qsort
为了给出另一个参考点,我也按照建议尝试调用库qsort(代码在这里).正如预期的那样速度慢得多:慢了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);,处理器可以并行执行.我尝试了它并按预期工作,排序网络的运行速度提高了约10%.
使用简单交换对网络12进行排序
在最初的帖子Steinar H. Gunderson建议的一年后,我们不应该试图超越编译器并保持交换代码简单.这确实是一个好主意,因为生成的代码快了大约40%!他还提出了使用x86内联汇编代码手动优化的交换,它仍然可以节省更多的周期.最令人惊讶的是(它说程序员心理学的卷)是一年前没有人尝试过那种版本的交换.我以前用来测试的代码就在这里.其他人提出了编写C快速交换的其他方法,但它产生的性能与具有合适编译器的简单方法相同.
"最佳"代码现在如下:
static inline void sort6_sorting_network_simple_swap(int * d){
#define min(x, y) (x<y?x:y)
#define max(x, y) (x<y?y:x)
#define SWAP(x,y) { const int a = min(d[x], d[y]); \
const int b = max(d[x], d[y]); \
d[x] = a; d[y] = b; }
SWAP(1, 2);
SWAP(4, 5);
SWAP(0, 2);
SWAP(3, 5);
SWAP(0, 1);
SWAP(3, 4);
SWAP(1, 4);
SWAP(0, 3);
SWAP(2, 5);
SWAP(1, 3);
SWAP(2, 4);
SWAP(2, 3);
#undef SWAP
#undef min
#undef max
}
如果我们相信我们的测试集(并且,它是非常差的,它的好处是简短且易于理解我们正在测量的内容),一种类型的结果代码的平均周期数低于40个周期(执行6次测试).这使得每次交换平均为4个周期.我打电话的速度非常快.还有其他改进吗？
Dan*_*ach 160
对于任何优化,最好是测试,测试和测试.我会尝试至少排序网络和插入排序.如果我在下注,我会根据过去的经验将我的钱放在插入排序上.
你对输入数据有什么了解吗？某些算法在某些类型的数据中表现更好.例如,插入排序在已排序或几乎排序的数据上表现更好,因此如果几乎排序数据的概率高于平均值,那么它将是更好的选择.
您发布的算法类似于插入排序,但看起来您已经以更多比较为代价减少了掉期数量.然而,比较远比交换更昂贵,因为分支可能导致指令管道停滞.
这是一个插入排序实现:
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
}
Pau*_*l R 60
这是使用排序网络的实现:
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 - 无分支,没有扭曲分歧等问题).
另请参阅:快速算法实现以排序非常小的列表
Rex*_*err 44
由于这些是整数并且比较快,为什么不直接计算每个的排名顺序:
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];
}
Kev*_*ock 35
看起来我迟到了一年,但在这里我们去......
看一下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;
}
我更改了修改测试套件以报告每种类型的时钟并运行更多测试(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
小智 15
几天前我偶然发现了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代码调用该函数:
void simd_sort_6(char *values);
小智 14
测试代码非常糟糕; 它溢出了初始数组(这里没有人读过编译器警告吗？),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).
phk*_*ler 13
虽然我真的很喜欢提供的交换宏:
#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如何工作并明确地拉出公共子表达式.这完全消除了最小和最大宏.
Pao*_*ini 12
在没有基准测试并查看实际编译器生成的程序集的情 如果我让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).
jhe*_*iko 11
我将测试套件移植到我无法识别的PPC架构机器上(不必触摸代码,只需增加测试的迭代次数,使用8个测试用例来避免使用mods污染结果并替换x86特定的rdtsc):
直接调用qsort库函数:101
天真的实现(插入排序):299
插入排序(Daniel Stutzbach) :108
插入排序已展开 :51
排序网络(Daniel Stutzbach) :26
排序网络(Paul R) :85
使用快速交换对网络12进行排序 :117
排序网络12重新排序交换 :116
排名顺序 :56
小智 7
XOR交换在您的交换功能中可能很有用.
void xorSwap (int *x, int *y) {
if (*x != *y) {
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
}
if可能会导致您的代码过多分歧,但如果您保证所有的int都是唯一的,那么这可能很方便.
小智 5
期待尝试这一点,并从这些例子中学习,但首先是我的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"紧随其后.
这是最后一次:
**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