[解決済み】固定長 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],
         *  d[i][8], d[i][9], d[i][10]);
        */
    }
    cycles = rdtsc() - cycles;
    printf("Time is %d\n", (unsigned)cycles);
}

生の結果

バリアントの数が多くなってきたので、それらをすべてテストスイートに集めましたので、ご覧ください。 こちら . 実際に使用されているテストは、Kevin Stockのおかげで、上で紹介したものよりも少し素朴なものになっています。自分の環境でコンパイルして実行することができます。私は、異なるターゲットアーキテクチャ/コンパイラでの動作にかなり興味があります。(OK みんな、それを答えに入れて、私は新しい結果セットのすべての貢献者を+1します)。

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
• ソーティング・ネットワークス（ポール・R）：66.36
• ソートネットワーク12と高速スワップ : 58.86
• ソートネットワーク 12 並べ替え Swap : 53.74
• ソートネットワーク 12並べ替え シンプルスワップ：31.54
• 高速スワップを含む並べ替えネットワーク：31.54
• 高速スワップ機能付き並べ替えネットワーク V2 : 33.63
• インラインバブルソート（パオロ・ボンツィーニ）：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
• ソーティング・ネットワークス（ポール・R）：64.44
• ソートネットワーク12と高速スワップ：61.98
• ソートネットワーク 12 並べ替え Swap : 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）

今のところベストです。実際にテストに使用したコードは ここで . なぜ、他のソートネットワークの実装と比較して2倍近く速いのかは、まだわかりません。パラメータ受け渡し？高速な最大値？

ネットワークの並べ替え 12 SWAPとFast Swapの併用

Daniel Stutzbach氏の提案により、彼の12スワップソーティングネットワークと分岐なし高速スワップを組み合わせてみました（コードはこちら こちら ). 1つ少ないスワップで予想されるマージン(約5%)で、これまでで最も高速になりました。

また、分岐のないスワップは、PPCアーキテクチャでifを使用したシンプルなスワップよりもはるかに（4倍）効率が悪いことに気づくのは興味深いことです。

ライブラリqsortの呼び出し

もう一つの参考として、提案されたようにライブラリqsortを呼び出すこともやってみました（コードは ここで ). 新しいテスト・スイートで明らかになったように、主な問題は最初の呼び出し後のライブラリの初期ロードにあるようで、他のバージョンとの比較ではそれほど悪い結果にはなっていません。私の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のバージョンでも強化され、Rank Orderは他のどの選択肢よりも常に2倍高速になりました。

ソートネットワーク12とスワップ順序の変更

gcc 4.4.3でのRex Kerr提案の驚異的な効率を見て、「どうしてメモリ使用量が3倍のプログラムが、分岐なしソートネットワークより速いのだろう？私の仮説では、書き込みの後に読み込むような依存関係が少ないので、x86のスーパースカラ命令スケジューラをよりよく利用できるのではないかと思いました。そこで思いついたのが、スワップを並べ替えて、書き込み後の読み出し依存性を最小にすることです。もっと簡単に言うと SWAP(1, 2); SWAP(0, 2); というのも、両者とも共通のメモリセルにアクセスするため、最初のスワップが終了するのを待ってから2番目のスワップを実行しなければならないからです。一方 SWAP(1, 2); SWAP(4, 5); プロセッサは両方を並列に実行することができます。試してみたところ、期待通りに動作し、ソートネットワークは約10%高速に動作しています。

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

最初の投稿から1年後、Steinar H. Gundersonは、コンパイラーを出し抜こうとせず、スワップコードをシンプルに保つべきだと提案しました。その結果、コードが約40%高速化されたのですから、これは本当に良いアイデアです。彼はまた、x86インライン・アセンブリ・コードを用いて手作業で最適化したスワップも提案し、これでももう少しサイクルを節約できるとしています。最も驚いたのは（プログラマの心理をよく表している）、1年前は誰もそのバージョンのスワップを試していなかったことだ。私がテストに使ったコードは こちら . 他の人は 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
}

もし私たちのテストセット(そう、それは非常に貧弱です。それは単に短く、シンプルで、私たちが何を測定しているかを理解しやすいという利点があります)を信じるなら、1ソートの結果のコードの平均サイクル数は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;
        }
}

仕分けネットワークを構築する方法は、次の通りです。 まず 本サイト で、適切な長さのネットワークのための最小限の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
}