为了账号安全,请及时绑定邮箱和手机立即绑定

最快的固定长度6 int数组

/ 猿问

最快的固定长度6 int数组

UYOU 2019-07-27 14:54:45

最快的固定长度6 int数组

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

由于问题是非常低的水平:

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

  • 避免排空指令流水线(具有非常高的成本),我们也许应该尽量减少分支机构,跳跃,和所有其他类型的控制流断裂的(像那些隐藏在背后的序列点&&||)。

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

真的这个问题是一种高尔夫,其目标不是最小化源长度而是执行时间。我把它叫做“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],

原始结果

随着变体的数量变得越来越大,我将它们全部收集在一个可以在这里找到的测试套件中。由于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

  • 具有快速交换V2的重新排序的分类网络:33.63

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

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

我既包括-O1和-02的结果,因为出奇的好节目O2是比O1效率。我想知道具体的优化有什么影响?

查看完整描述

3 回答

?
慕森卡

对于任何优化,最好是测试,测试和测试。我会尝试至少排序网络和插入排序。如果我在下注,我会根据过去的经验将我的钱放在插入排序上。

你对输入数据有什么了解吗?某些算法在某些类型的数据中表现更好。例如,插入排序在已排序或几乎排序的数据上表现更好,因此如果几乎排序数据的概率高于平均值,那么它将是更好的选择。

您发布的算法类似于插入排序,但看起来您已经以更多比较为代价减少了掉期数量。然而,比较远比交换更昂贵,因为分支可能导致指令管道停滞。

这是一个插入排序实现:

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}


查看完整回答
反对 回复 2019-07-27
?
蓝山帝景

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

inline void Sort2(int *p0, int *p1){
    const int temp = min(*p0, *p1);
    *p1 = max(*p0, *p1);
    *p0 = temp;}inline void Sort3(int *p0, int *p1, int *p2){
    Sort2(p0, p1);
    Sort2(p1, p2);
    Sort2(p0, p1);}inline void Sort4(int *p0, int *p1, int *p2, int *p3){
    Sort2(p0, p1);
    Sort2(p2, p3);
    Sort2(p0, p2);  
    Sort2(p1, p3);  
    Sort2(p1, p2);  }inline void Sort6(int *p0, int *p1, int *p2, int *p3, int *p4, int *p5){
    Sort3(p0, p1, p2);
    Sort3(p3, p4, p5);
    Sort2(p0, p3);  
    Sort2(p2, p5);  
    Sort4(p1, p2, p3, p4);  }

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

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

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


查看完整回答
反对 回复 2019-07-27
?
慕圣8478803

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

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


查看完整回答
反对 回复 2019-07-27

添加回答

回复

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信