Stack Overflow の別の質問への回答 (これです) 興味深いサブ問題に遭遇しました。6 つの整数の配列をソートする最も速い方法は何でしょうか?
質問のレベルが非常に低いので:
- ライブラリが利用可能であるとは想定できない（呼び出し自体にコストがかかる）ため、プレーンなCのみ
- 命令パイプラインが空になるのを避けるには（コストが非常に
&&高い）、分岐、ジャンプ、その他のあらゆる種類の制御フローの中断（またはのシーケンス ポイントの背後に隠れているものなど）を最小限に抑える必要があります||。 - スペースが制限されており、レジスタとメモリの使用を最小限に抑えることが課題である場合、理想的にはインプレース ソートがおそらく最適です。
この質問は、ソースの長さを最小化するのではなく、実行時間を最小化することを目標とする一種のゴルフです。私はこれを、本のタイトルにもあるように「Zening」コードと呼んでいます。Zen of Code の最適化によるマイケル・アブラッシュそしてその続編。
なぜそれが興味深いのかというと、いくつかの層があるからです。
- この例はシンプルで理解しやすく、測定も容易で、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
- 挿入ソート (ダニエル・シュトゥッツバッハ) : 142.12
- 挿入ソート展開: 125.47
- 順位 : 102.26
- レジスターによる順位: 58.03
- ソーティングネットワーク（ダニエル・シュトゥッツバッハ） : 111.68
- ソーティングネットワーク（ポール R） : 66.36
- 高速スワップによるソートネットワーク 12: 58.86
- ソートネットワーク 12 並べ替え スワップ: 53.74
- ソートネットワーク 12 並べ替え Simple Swap : 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
- 挿入ソート (ダニエル・シュトゥッツバッハ) : 142.11
- 挿入ソート展開: 126.75
- 順位: 46.42
- レジスターによる順位: 43.58
- ソーティングネットワーク（ダニエル・シュトゥッツバッハ） : 115.57
- ソーティングネットワーク（ポール R） : 64.44
- 高速スワップ付きソートネットワーク 12: 61.98
- ソートネットワーク 12 並べ替え スワップ: 54.67
- ソートネットワーク 12 並べ替え Simple Swap : 31.54
- 高速スワップを備えた並べ替えソートネットワーク: 31.24
- 高速スワップ付き並べ替えネットワーク V2: 33.07
- インラインバブルソート (Paolo Bonzini) : 45.79
- アンロール挿入ソート (Paolo Bonzini) : 80.15
驚いたことに、いくつかのプログラムでは O2 の方が O1 よりも効率が悪いため、-O1 と -O2 の両方の結果を含めました。どのような特定の最適化がこの効果をもたらすのでしょうか?
提案された解決策に対するコメント
挿入ソート (ダニエル・シュトゥッツバッハ)
予想通り、分岐を最小限に抑えることは確かに良いアイデアです。
ソーティングネットワーク (ダニエル・シュトゥッツバッハ)
挿入ソートよりも優れています。主な効果は外部ループを回避することによるものではないのかと思いました。アンロール挿入ソートで確認してみましたが、確かにほぼ同じ数値が得られました（コードは次のとおりです）。ここ）。
ソーティングネットワーク (Paul R)
今のところ最高です。実際にテストに使用したコードはここ他のソート ネットワーク実装よりも 2 倍近く高速である理由はまだわかりません。パラメータの受け渡し? 最大速度?
ソートネットワーク 12 高速スワップによる SWAP
ダニエル・スタッツバッハの提案に従って、私は彼の12スワップソートネットワークとブランチレス高速スワップ（コードはここ) 確かに高速化しており、スワップを 1 つ少なくすることで期待通りわずかなマージン (約 5%) でこれまでで最高です。
また、ブランチレス スワップは、PPC アーキテクチャで if を使用する単純なスワップよりもはるかに (4 倍) 効率が悪いように見えることも興味深い点です。
ライブラリqsortの呼び出し
もう一つの参考として、私は提案されたようにライブラリqsortを呼び出すことも試しました（コードはここ)。予想通り、かなり遅くなりました。10 ～ 30 倍遅いです。新しいテスト スイートで明らかになったように、主な問題は最初の呼び出し後のライブラリの初期ロードにあるようで、他のバージョンと比べてもそれほど悪くはありません。私の 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 のスーパースカラー命令スケジューラをより有効に活用できるというものでした。そこから、スワップを並べ替えて書き込み後の読み取りの依存関係を最小限に抑えるというアイデアが浮かびました。もっと簡単に言うと、これを行うと、2 つのスワップが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 サイクルです。これは驚くほど高速です。他に改善できる点はありますか?
ベストアンサー1
どのような最適化でも、テスト、テスト、テストを繰り返すのがベストです。少なくともソート ネットワークと挿入ソートを試してみます。賭けるなら、過去の経験に基づいて挿入ソートに賭けます。
入力データについて何か知っていますか? 一部のアルゴリズムは、特定の種類のデータでより優れたパフォーマンスを発揮します。たとえば、挿入ソートは、ソート済みまたはほぼソート済みのデータでより優れたパフォーマンスを発揮するため、ほぼソート済みのデータの可能性が平均以上にある場合は、挿入ソートの方が適しています。
投稿されたアルゴリズムは挿入ソートに似ていますが、比較回数を増やす代わりにスワップ回数を最小限に抑えているように見えます。ただし、分岐によって命令パイプラインが停止する可能性があるため、比較はスワップよりもはるかにコストがかかります。
挿入ソートの実装は次のとおりです。
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
}