[解決済み] ループのアンロールが役に立つとしたら、どんなときか？

質問

私はいくつかの非常にパフォーマンスが重要なコード (モンテカルロ シミュレーション内で何百万回と呼び出されるクイック ソート アルゴリズム) をループ展開によって最適化しようとしています。 私が高速化しようとしている内部ループは次のとおりです。

// Search for elements to swap.
while(myArray[++index1] < pivot) {}
while(pivot < myArray[--index2]) {}

みたいな感じでアンロールしてみました。

while(true) {
    if(myArray[++index1] < pivot) break;
    if(myArray[++index1] < pivot) break;
    // More unrolling
}


while(true) {
    if(pivot < myArray[--index2]) break;
    if(pivot < myArray[--index2]) break;
    // More unrolling
}

これでは全く変化がないので、より読みやすい形に戻しました。 ループの展開を試した他のときにも、同じような経験があります。 最近のハードウェアの分岐予測の品質を考えると、ループ展開がまだ有用な最適化であるとすれば、それはいつなのでしょうか?

どのように解決するのですか?

ループのアンロールは、依存関係の連鎖を断ち切ることができれば意味があります。これは、アウトオブオーダーまたはスーパースカラー CPU に、物事をよりよくスケジュールする可能性を与え、その結果より速く実行できるようにします。

簡単な例です。

for (int i=0; i<n; i++)
{
  sum += data[i];
}

ここでは、引数の依存関係は非常に短いです。データ配列のキャッシュミスのためにストールした場合、CPUは何もできず、ただ待つだけです。

一方、このコードでは

for (int i=0; i<n; i+=4)
{
  sum1 += data[i+0];
  sum2 += data[i+1];
  sum3 += data[i+2];
  sum4 += data[i+3];
}
sum = sum1 + sum2 + sum3 + sum4;

はより速く実行できるかもしれません。もし、ある計算でキャッシュミスやその他のストールが発生しても、ストールに依存しない他の3つの依存関係チェーンが残っています。順不同の CPU はこれらを実行することができます。