c - 使い方 - sort arrays java




固定長の最速の並べ替え6 int配列 (16)

別のスタックオーバーフローへの回答( この1つ )私は興味深いサブ問題を見つけました。 6 intの配列をソートする最速の方法は何ですか?

問題は非常に低いレベルです:

  • ライブラリが利用可能であると仮定することはできません(呼び出し自体にはコストがかかります)。単純なC
  • 非常にコストが高い)命令パイプラインを空にするのを避けるために、ブランチ、ジャンプ、および( &&||シーケンスポイントの後ろに隠れているような)他のあらゆる種類のコントロールフローを最小限に抑えるべきでしょう。
  • 部屋が制約され、レジスタやメモリの使用を最小限にすることが問題になります。

本当にこの質問は、ソースの長さを減らすことを目的とせず、実行時間を最小限にするゴルフのようなものです。 マイケル・ブラッシュ(Michael Abrash)とそのsequelsによる「コード最適化(Code Zen of Code Optimization)」という本のタイトルで使用されている「ゼーニング(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);
}

生の結果

変種の数が増えているので、私はhereで見つけることができるテストスイートでそれらをすべて集めましhere 。 使用された実際のテストは、Kevin Stockのおかげで、上に示したものよりやや素朴なものです。 あなたは自分の環境でコンパイルして実行することができます。 私は、さまざまなターゲットアーキテクチャ/コンパイラでの動作にはかなり興味があります。 (OK人、答えに入れて、私は新しい結果セットのすべての貢献者を+1する)。

私はダニエル・シュトゥットバッハ(Daniel Stutzbach)に1年前に答えを出しました。そのとき、彼はその時点で最も速い解決策の源泉でした(ネットワークを分類しています)。

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
  • Fast Swapを使用したネットワーク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

驚くべきことに、いくつかのプログラムでは、O2はO1よりも効率が悪いため、-O1と-O2の両方の結果が含まれていました。 どのような特定の最適化がこの効果を持っているのだろうか?

提案された解決策に関するコメント

挿入ソート(Daniel Stutzbach)

予想通り、分岐を最小化することは確かに良い考えです。

ソートネットワーク(Daniel Stutzbach)

挿入の並べ替えよりも優れています。 私は主な効果が外部ループを避けることから得られなかったのか疑問に思った。 確認のためにアンローリング挿入型で試してみましたが、実際にはほぼ同じ数字が表示さhere (コードはhereありhere )。

ソートネットワーク(Paul R)

これまでのところ最高です。 私がテストに使った実際のコードはhereありhere 。 他のソートネットワーク実装の約2倍の速さである理由はまだ分かりません。 パラメータ渡し? ファーストマックス?

ネットワークのソート12スワップとスワップスワップ

Daniel Stutzbachの提案によれば、私は12のスワップソートネットワークとブランチレス高速スワップ(コードはhereありhere )を組み合わせました。 実際には速いですが、スワップが1つ少ないことを前提として、わずかなマージン(約5%)でこれまで最高です。

ブランチレススワップは、PPCアーキテクチャーを使用している単純なものよりも効率が低い(4倍)と思われることも興味深い。

ライブラリqsortを呼び出す

別の参照ポイントを与えるために、ライブラリqsort(コードはhereありhere )を呼び出すように提案しました。 新しいテストスイートでは明らかになったように、主な問題は最初の呼び出しの後のライブラリの最初の読み込みであるように見えますが、それは他のものとそれほど貧弱ではありませんバージョン。 私のLinuxでは3〜20倍遅いです。 他の人のテストに使われているアーキテクチャでは、もっと速くなっているように見えます(ライブラリqsortはもっと複雑なAPIを使うので、私は本当にそれに驚いています)。

ランキング

Rex Kerrは全く別の方法を提案しました。配列の各アイテムが最終的な位置を直接計算するためです。 ランクオーダーの計算にブランチが必要ないため、効率的です。 この方法の欠点は、配列のメモリ容量の3倍(配列の1つのコピーとランクオーダーを格納するための変数)がかかることです。 パフォーマンスの結果は非常に驚くほどです(興味深い)。 32ビットOSとIntel Core2 Quad E8300を使用したリファレンスアーキテクチャでは、サイクル数が1000をわずかに下回っていました(分岐スワップを持つソートネットワークのように)。 しかし、私の64ビットボックス(Intel Core2 Duo)でコンパイルして実行すると、これまでの方がはるかに優れていました。 私はついに真の理由を知りました。 私の32ビットのボックスはgcc 4.4.1と私の64ビットボックスgcc 4.4.3を使い、最後のものはこの特定のコードを最適化する上でとても良いようです(他の提案にはほとんど違いがありません)。

アップデート

上の公表された図が示すように、この効果はgccのそれ以降のバージョンではまだ改善されていて、ランクオーダーは他の方法よりも2倍速くなっています。

リオーダーされたスワップによるネットワーク12のソート

GCC 4.4.3のRex Kerr提案の驚くべき効率は、3倍のメモリー使用量を持つプログラムが、どのようにしてブランチレスソートネットワークよりも高速になるのだろうと思いましたか? 私の仮説は、書き込み後に読み取られる種類の依存性が少なく、x86のスーパスカラ命令スケジューラをより有効に利用できるということでした。 これは、書き込みの依存関係の後に読み込みを最小限にするためにスワップを並べ替えるというアイディアをもたらしました。 より簡単に言えば: SWAP(1, 2); SWAP(0, 2); SWAP(1, 2); SWAP(0, 2); 両方の共通のメモリセルへのアクセスのために、最初のスワップが完了するのを待たなければなりません。 あなたがSWAP(1, 2); SWAP(4, 5); SWAP(1, 2); SWAP(4, 5); プロセッサは両方を同時に実行することができます。 私はそれを試して、期待どおりに動作し、ソートネットワークは約10%速く走っています。

シンプルスワップによるネットワーク12の並べ替え

Steinar H. Gunderson氏が提案した元の記事の1年後、私たちはコンパイラの能力を失い、スワップコードを単純にしてはいけないと提案しました。 結果として得られるコードが約40%速くなることは確かに良い考えです! また、x86インラインアセンブリコードを使用して手作業で最適化したスワップを提案しました。 最も驚くべきこと(それはプログラマーの心理学の量を言う)は、1年前にそのスワップのバージョンを試したことがないということです。 私がテストに使用したコードはhereあり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サイクルにします。 私はそれを驚くほど早く呼びます。 その他の改善は可能ですか?


ソートネットワークを使用した実装を次に示します

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操作(それぞれ合計13個)のシーケンスなので、非常に効率的なブランチレスのminmax実装が本当に必要です。 私はこれを読者のための練習として残す。

この実装はベクトル化(例えば、SIMD - ほとんどのSIMD ISAはベクトル最小/最大命令を持つ)やGPU実装(例えばCUDA - 分岐なしではワーピングの分岐などに問題はない)に容易に対応することに注意してください。

参照: 非常に小さなリストをソートするための高速アルゴリズム実装


XORスワップは、スワップ機能に便利です。

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

ifはあなたのコードに多すぎる相違を引き起こすかもしれませんが、あなたのintがすべてユニークであるという保証があれば、これは便利かもしれません。


このスレッドへの私の貢献は次のとおりです。固有の値を含む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);
}

デュアルコアAthlon M300 @ 2GHz(DDR2メモリ)搭載のHP dv7-3010soノートパソコンでは、165クロックサイクルで実行されます。これは、一意のシーケンスごとにタイミングから計算された平均です(全体で6!/ 720)。OpenWatcom 1.8を使用してWin32にコンパイルされました。ループは本質的に挿入の並べ替えであり、16命令/ 37バイトの長さです。

私はコンパイルするための64ビット環境を持っていません。


これらは整数なので、比較は速いので、それぞれの順位を直接計算してみませんか?

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

テストコードはかなり悪いです。 それは最初の配列をオーバーフローさせます(ここではコンパイラの警告を読まないのですか?)、printfは間違った要素を出力しています。rdtscにはrdtscを使用しています、実行は1つしかありません!含まれているテストは非常に初歩的(負の数はありません)であり、関数全体をデッドコードとして破棄することからコンパイラを停止させるものは何もありません。

つまり、ビットネットワークソリューションでも改善するのは簡単です。 単に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、-O2、amd64、Core i7)。


私は1年後にパーティーに参加したようですが、ここに行きます...

gcc 4.5.2で生成されたアセンブリを見ると、実際には必要ないスワップごとにロードとストアが実行されていることがわかりました。 6つの値をレジスタにロードし、それらをソートし、それらをメモリに戻す方が良いでしょう。 私は店舗での荷物を可能な限り近くに配置するように命令しました。レジスタは、最初に必要とされ、最後に使用されました。 Steinar H. GundersonのSWAPマクロも使用しました。 更新:私はPaolo BonziniのSWAPマクロに切り替えました。これはgccがGundersonに似たものに変換しますが、gccは明示的なアセンブリとして与えられていないため、命令の順序を整えることができます。

私は最高のパフォーマンスとして与えられたリオーダーされたスワップネットワークと同じスワップオーダーを使用しましたが、より良いオーダーがあるかもしれません。 もう少し時間を見つけたら、私は一連の並べ替えを生成してテストします。

テストコードを変更して4000個以上の配列を検討し、それぞれの配列をソートするのに必要な平均サイクル数を表示しました。 i5-650では、元の並べ替えソートネットワークが〜65.3サイクル/ソート(-O1を使用、-O2と-O3を上回る)と比較して~34.1サイクル/ソート(-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

私はこれが古い質問であることを知っています。

しかし、私は共有したい別の種類のソリューションを書きました。
ネストされたMIN MAXを使用して、

それは、それぞれの114を使っているので高速ではなく、
とても単純に75に減らすことができます - > pastebin

しかしそれは純粋にmin maxではありません。

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

編集:
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;
}

私は数日前にGoogleからこの質問に出会いました。固定長配列の6つの整数を素早くソートする必要があったからです。 しかし、私の場合、整数は8ビット(32ではなく)で、C言語のみを使用するという厳しい要件はありません。

SSEを使って比較とスワップの動作を可能な限りベクトル化するアセンブリで、ネットワークソートの変種を実装しました。 配列を完全にソートするには6回の "パス"が必要です。 私は、PADDB(ベクトル化された加算)と場合によってはPAND(ビット単位のAND)命令だけを使用して、PSHUFB(ベクトル化されたスワップ)のパラメータをシャッフルするために、PCMPGTB

このアプローチには、 本当にブランチレス機能をもたらす副作用もありました。 ジャンプ命令はまったくありません。

この実装 、質問で最も速いオプションとして現在マークされている実装(「単純なスワップを使用してネットワークを並べ替える」) より約38%高速です。 テスト中にchar配列要素を使用するようにその実装を変更し、比較を公正に行いました。

このアプローチは、16までの任意の配列サイズに適用できることに注意してください。 代替配列よりも相対的な速度の利点が、より大きなアレイではより大きくなることが期待されます。

このコードは、SSSE3を搭載したx86_64プロセッサのMASMで記述されています。 関数は、 "新しい" 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);

私は識別できないPPCアーキテクチャマシンにテストスイートを移植しました(コードに触れる必要はありませんでした。テストの反復回数を増やし、8つのテストケースを使用してmodで汚染を避け、x86固有のrdtscを置き換えます)。

qsortライブラリ関数への直接呼び出し:101

純粋な実装(挿入ソート):299

挿入ソート(Daniel Stutzbach):108

挿入された並べ替えの並べ替え:51

ソートネットワーク(Daniel Stutzbach):26

ソートネットワーク(Paul R):85

Fast Swapを使用してネットワーク12を並べ替える:117

ソートネットワーク12並べ替えスワップ:116

ランク順:56


'ソートされたリストの並べ替え'ソートを試してください。:) 2つの配列を使用します。小さくて大きな配列のために最速。
あなたがコンクレートする場合は、挿入箇所のみをチェックします。必要のない他の大きな値(cmp = ab> 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;
	}
}


これらの例から私の手を試してみることを楽しみにしていますが、まず1.5 GHz PPC Powerbook G4(1 GB DDR RAM搭載)のタイミングを見てください。(私はタイミングに関してはhttp://www.mcs.anl.gov/~kazutomo/rdtsc.htmlからPPCのための同様のrdtscのようなタイマーを借りた)私はプログラムを数回実行し、絶対的な結果は様々だったが一貫して最も速いテストは "Insertion Sort(Daniel Stutzbach)"で、 "Insertion Sort Unrolled"は2番目に近いテストでした。

ここに最後のセットがあります:

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

たぶん私パーティーに遅れているかもしれませんが、少なくとも私の貢献は新しいアプローチです。

  • コードは本当にインライン化する必要があります
  • インライン化されていても、ブランチが多すぎる
  • 分析部は、基本的にO(N(N-1))であり、N = 6
  • コストswapがより高い(コストがかかるcompare)場合、コードはより効果的なります。
  • インライン化された静的関数を信頼します。
  • このメソッドはランクソートに関連しています
    • ランクの代わりに、相対ランク(オフセット)が使用されます。
    • ランクの合計は、任意の順列グループの各サイクルについてゼロである。
    • SWAP()2つの要素の代わりに、1つのtempと1つの(register-> register)swap(new-old)を必要とするサイクルが追跡されます。

アップデート:コードを少し変更しました。一部の人々は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);
}

ベンチマークや実際のコンパイラ生成アセンブリを見ることなく、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サイクル対420サイクル)。?:と最大限にやっているのは、ほぼ同じですが、ノイズがほとんどなくなりますが、上記は少し速いです。この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を試しました。彼らは同じ最適化を行いますが、スケジューリングの違いにより、2つの結果にはいくつかのバリエーションがあり、どちらが速いか遅いかは実際には言えません。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のものよりも高速で、ITERは3つの命令(SWAPでは4つ)で実行できるため、GPUまたは述語を持つコンピュータで特に優れています。たとえば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

6つの要素の場合、挿入ソートはソートネットワークと競合します(12回のスワップと15回の反復で4命令/スワップと3命令/反復のバランスがとれます)。バブルの種類はもちろん遅いです。しかし、ソート・ネットワークはO(n log n)であるのに対し、挿入ソートはO(n ^ 2)であるため、サイズが大きくなると真ではありません。


使用法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;
}

私は少なくとも私のシステムでは、以下のように定義された機能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 ++がソートコードをよりよく最適化できるようにする保証です私は正しく覚えている、なぜまた非常に多くのアルゴリズムなどの理由の一部ですstdstd::sort()一般的には、このような優れた性能を有する)。しかし、タイミングIでは、ソート機能への呼び出しが行われたコンテキスト(つまり周囲のコード)がパフォーマンスに重大な影響を与えていることに気付きました。これは、関数がインライン展開されて最適化されたためです。例えば、プログラムが十分にシンプルであれば、ソート関数にポインタを渡して反復子を渡すことと、反復子を渡すこととの間にパフォーマンスの違いはほとんどありません。それ以外の場合、イテレータを使用すると、パフォーマンスが顕著に向上し、パフォーマンスは大幅に低下します。私はこれが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が一貫して最適化しているソートアルゴリズムを使いたい場合は、次の2つのアルゴリズムのいずれかを試してみてください:

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
}

または

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キーワードを指定しても、バニラC関数よりもgccによってテンプレート関数が一般にはるかに積極的に最適化されているためです(これはgccがバニラC関数の関数ポインタを処理する必要がありますがテンプレート関数では機能しません)。


私は非常に遅いと知っていますが、いくつかの異なるソリューションを試してみることに興味がありました。まず、そのペーストをクリーンアップし、コンパイルしてリポジトリに入れました。私は、他人がそれを試していないように、行き詰まりとしていくつかの望ましくない解決策を保った。この中で私の最初の解決策は、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/ : https://github.com/eyepatchParrot/sort6/





gpgpu