別のStackOverflowの質問（これ）に答えると、興味深いサブ問題に遭遇しました。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年前にダニエル・スタッツバッハ（ゴルフ用）に答えました。彼は当時最速のソリューション（ソーティングネットワーク）のソースでした。
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はSimpleSwapを並べ替えました：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はSimpleSwapを並べ替えました：31.54
- 高速スワップ付きの並べ替えられたソーティングネットワーク：31.24
- 高速スワップV2を使用した並べ替えネットワーク：33.07
- インラインバブルソート（Paolo Bonzini）：45.79
- 展開された挿入ソート（Paolo Bonzini）：80.15
驚くべきことに、いくつかのプログラムではO2の効率がO1よりも低いため、-O1と-O2の両方の結果を含めました。どのような特定の最適化がこの効果をもたらすのだろうか？
提案されたソリューションに関するコメント
挿入ソート（Daniel Stutzbach）
予想通り、ブランチを最小化することは確かに良い考えです。
ソーティングネットワーク（Daniel Stutzbach）
挿入ソートよりも優れています。主な効果は外部ループを回避することから得られたのではないかと思いました。挿入ソートを展開して確認してみたところ、ほぼ同じ数値が得られました（コードはこちら）。
ソーティングネットワーク（Paul R）
これまでで最高。私がテストに使用した実際のコードはここにあります。他のソーティングネットワークの実装のほぼ2倍の速度である理由はまだわかりません。パラメータの受け渡し？ファストマックス？
高速スワップを使用したネットワーク12SWAPの並べ替え
Daniel Stutzbachが提案したように、私は彼の12スワップソーティングネットワークをブランチレス高速スワップと組み合わせました（コードはここにあります）。それは確かに高速であり、1つ少ないスワップを使用して期待できるように、わずかなマージン（約5％）でこれまでのところ最高です。
ブランチレススワップは、PPCアーキテクチャでifを使用する単純なスワップよりもはるかに（4倍）効率が低いように見えることにも注目してください。
ライブラリqsortの呼び出し
別の参照ポイントを与えるために、私は提案されたようにライブラリqsortを呼び出すことも試みました（コードはここにあります）。予想どおり、はるかに遅くなります。10〜30倍遅くなります...新しいテストスイートで明らかになったように、主な問題は最初の呼び出し後のライブラリの初期ロードであるように見え、他のライブラリと比べてもそれほど悪くはありません。バージョン。私のLinuxでは3倍から20倍遅いです。他の人がテストに使用する一部のアーキテクチャでは、さらに高速に見えるようです（ライブラリqsortはより複雑なAPIを使用しているため、このアーキテクチャには本当に驚いています）。
順位
Rex Kerrは、まったく異なる別の方法を提案しました。配列の各項目について、その最終位置を直接計算します。ランク順の計算には分岐が必要ないため、これは効率的です。この方法の欠点は、配列の3倍のメモリ量（ランク順を格納するための配列と変数の1つのコピー）を必要とすることです。パフォーマンスの結果は非常に驚くべきものです（そして興味深いものです）。32ビットOSとIntelCore2Quad E8300を使用したリファレンスアーキテクチャでは、サイクル数は1000をわずかに下回りました（分岐スワップを使用したネットワークの並べ替えなど）。しかし、64ビットボックス（Intel Core2 Duo）でコンパイルして実行すると、パフォーマンスが大幅に向上しました。これまでのところ最速になりました。私はついに本当の理由を見つけました。私の32ビットボックスはgcc4.4.1を使用し、64ビットボックスはgcc4.4を使用します。
更新：
上記の公開された図が示すように、この効果はgccの新しいバージョンによってさらに強化され、ランク順は他の代替手段の2倍の速度になりました。
並べ替えられたスワップを使用したネットワーク12の並べ替え
gcc4.4.3を使用したRexKerr提案の驚くべき効率は、私に不思議に思いました。メモリ使用量が3倍のプログラムは、ブランチレスソーティングネットワークよりもどのように高速でしょうか。私の仮説は、書き込み後に読み取られる種類の依存関係が少なく、x86のスーパースカラー命令スケジューラをより適切に使用できるようにするというものでした。それは私にアイデアを与えました：書き込み後の読み取り依存関係を最小化するためにスワップを並べ替えます。もっと簡単に言えSWAP(1, 2); SWAP(0, 2);ば、両方が共通のメモリセルにアクセスするため、最初のスワップが終了するのを待ってから2番目のスワップを実行する必要があります。これを行うとSWAP(1, 2); SWAP(4, 5);、プロセッサは両方を並行して実行できます。私はそれを試しましたが、期待どおりに機能し、ソーティングネットワークは約10％高速に実行されています。
単純なスワップを使用したネットワーク12の並べ替え
Steinar H. Gundersonが最初の投稿から1年後、コンパイラーの裏をかくことを試みて、スワップコードを単純に保つべきではないと提案しました。結果のコードは約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サイクルになります。私はそれを驚くほど速く呼んでいます。他に可能な改善はありますか？