回答另一个Stack Overflow的问题(this one),我偶然发现了一个有趣的子问题。如何最快地对包含6个整数的数组进行排序?
由于这个问题非常低级:
- 我们不能假定库是可用的(而且调用本身也有成本),只能使用纯C。
- 为了避免清空指令流水线(这是一种非常高的成本),我们应该尽可能减少分支、跳转和其他任何控制流中断(例如在
&&
或||
中隐藏的那些)。 - 空间受限,最小化寄存器和内存使用是一个问题,最好采用原地排序。
实际上,这个问题是一种高尔夫游戏,目标不是使源长度最小化,而是执行时间最短。我称之为“禅”的代码,正如Michael Abrash的书《Zen of Code optimization》及其sequels中所使用的标题。
至于为什么它很有趣,有几个层次:
- 这个例子简单易懂,容易衡量,不需要太多的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
- 带快速交换的重排排序网络:31.54
- 带快速交换的重排排序网络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
- 带快速交换的重新排序排序网络:31.24
- 带快速交换的重新排序排序网络V2:33.07
- 内联冒泡排序(Paolo Bonzini):45.79
- 展开的插入排序(Paolo Bonzini):80.15
我包含了-O1和-O2的结果,因为令人惊讶的是对于几个程序,O2比O1效率更低。我想知道具体哪种优化会产生这种影响?
关于提出的解决方案的评论
插入排序(Daniel Stutzbach)
如预期的那样,最小化分支确实是一个好主意。
排序网络(Daniel Stutzbach)
比插入排序更好。我想知道主要效果是否不是通过避免外部循环获得的。我尝试了展开插入排序以进行检查,确实我们得到了大致相同的数据(代码在这里)。排序网络(Paul R)
到目前为止最好的。我用来测试的实际代码在这里。还不知道为什么它几乎比其他排序网络实现快两倍。参数传递?快速最大值?
带快速交换的12交换排序网络
正如Daniel Stutzbach建议的那样,我将他的12个交换排序网络与无分支快速交换组合在一起(代码在这里)。确实更快,迄今为止具有小幅度的优势(大约5%),因为使用1次较少的交换是可以预期的。
另外,有趣的是,分支交换似乎比在PPC架构上使用if的简单交换效率低得多(4倍)。
调用库qsort
为了再给一个参考点,我也试着按建议调用库函数qsort(代码在这里)。正如预期的那样,它慢得多:10到30倍……随着新的测试套件的出现,主要问题似乎是第一次调用后库的初始加载,而且与其他版本相比表现并不差。在我的Linux上,它只比其他版本慢3到20倍。在其他人测试时使用的某些架构上,它甚至似乎更快(我对这个结果感到非常惊讶,因为库函数qsort使用了更复杂的API)。 排名顺序 Rex Kerr提出了另一种完全不同的方法:针对数组的每个项直接计算其最终位置。这很有效,因为计算排名顺序不需要分支。但该方法的缺点是需要数组大小三倍的内存(一个数组副本和变量来存储排名顺序)。性能结果非常令人惊讶(也很有趣)。在我的32位操作系统和Intel Core2 Quad E8300参考架构上,循环计数略低于1000(像带分支交换的排序网络一样)。但是,当在我的64位系统(Intel Core2 Duo)上编译和执行时,它表现得更好:到目前为止,它成为最快的。我最终找到了真正的原因。我的32位系统使用gcc 4.4.1,而我的64位系统使用gcc 4.4.3,后者在优化这个特定代码方面要好得多(对其他提案几乎没有什么区别)。 更新: 如上面发布的数字表明,这个效果仍然受到后来版本的gcc的增强,排名顺序变得比任何其他替代方案都快两倍。
重新排序的交换排序网络12
Rex Kerr提议使用gcc 4.4.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个周期。我认为这非常快。还有其他改进可能吗?
x-y
和x+y
不会导致下溢或上溢吗? - Matthieu M.__asm__ volatile (".byte 0x0f, 0x31; shlq $32, %%rdx; orq %%rdx, %0" : "=a" (x) : : "rdx");
,因为rdtsc将答案放在EDX:EAX中,而GCC希望它在一个64位寄存器中。您可以通过在-O3下编译来查看错误。另请参见我对Paul R关于更快速的SWAP的评论。 - Paolo BonziniCMP EAX, EBX; SBB EAX, EAX
会根据EAX
与EBX
的大小关系,在EAX
中放入0或0xFFFFFFFF。SBB
是"带借位减法",与ADC
("带进位加法")相对应; 您所指的状态位 就是 进位位。然而,我记得在 Pentium 4 上,ADC
和SBB
的延迟和吞吐量很差,与ADD
和SUB
相比仍然慢两倍,并且在Core CPU上也是如此。自从80386以来,还有SETcc
条件存储和CMOVcc
条件移动指令,但它们也很慢。 - j_random_hacker