cの中で絶対に最速のforループは何ですか？

Question

イメージピクセルにアクセスするための最適化されたコードを書き込もうとしています。アセンブリレベルまで下がることなく、forループを超高速にする必要があります。さらに、索引付けは行に沿って行われ、キャッシュミスを最小限に抑えます。

これは私が持っているものです。

for (indr=0;indr<(height-1)*width;indr+=width) { 
     for (indc=0;indc<width;indc++){ 
      I[indr+indc]= dostuff ; 
     } 
    } 

「dostuffは」同じ行にアレントの要素にアクセスすることを含むので、私はそれ単一のループにするカント。

これを行うより速い方法がありますか？

EDIT 私の前の投稿がここでは完全なコードを追加しています。それはかなり読めませんが、一般的な考え方は、Imが積分画像を使って単純なボックスで畳み込みを実行することです。画像は、左と下にws + 1のゼロが、右と上にwsのゼロが最初に埋め込まれます。それは積分画像Iiとされる。次の関数は積分画像をとり、結果Icが元の画像と同じサイズの畳み込みを抽出します。

void convI(float *Ic,float *Ii,int ws, int width, int height) 
{ 
    int W=width+ws*2+1,indR; 
    int H=height+ws*2+1,indC; 
    int w=width, indr; 
    int h=height, indc; 
    int jmpA=W*(ws+1),jmpC=W*ws,jmpB=ws+1,jmpD=ws; 

    for (indR=W*(ws+1),indr=0;indr<width*(height-1);indR+=W,indr+=width) { 
     for (indC=ws+1,indc=0;indc<width;indC++,indc++){ 
      //Performs I[indA]+I[indD]-I[indB]-I[indC]; 
      Ic[indr+indc]= 
      Ii[indR-jmpA+indC-jmpB]+ 
      Ii[indR+jmpC+indC+jmpD]- 
      Ii[indR+jmpC+indC-jmpB]- 
      Ii[indR-jmpA+indC+jmpD]; 
     } 
    } 
} 

これは、 "dostuff"部分です。ループは低速です。

Answer 1

すべての最適化レベルをオンにしている場合は、他のコードの方がパフォーマンスが向上する理由はあまりありません。

なぜループ自体がボトルネックと思われますか？あなたが実際にやっていることを知らなくても言えることはあまりありません。あなたのコードをベンチマークし、疑問があれば、これが生成するアセンブラを見てください。

編集：ループの内側部分を示した後。

索引計算の式をループ外にできるだけ置く可能性が少しあります。これはループ変数と混在しているため、これはおそらく最適化できません。 （または、コンパイラがそれを見て、できるだけ事前計算するように、インデックスの計算を並べ替えるだけです）。

ほとんどの場合、パフォーマンスの問題はベクトルへのアクセスに起因します。インデックスをより正確に計算すると、コンパイラ/システムは実際にベクトルに通常のパターンでアクセスすることが実際に分かるため、これも改善される可能性があります。

これが役立たない場合は、ベクターの負荷が増分でストアではないようにループを再構成してください。ロードは、データが操作を実行するまで常に待機しなければならず、ストアはそれほど賢明ではありません。

Answer 2

SSEのようなベクトル化命令を使用しない限り、それほど多くのことはできません。

Answer 3

外側のループのheight-1をループの前の割り当てに持ち上げて勝利するかもしれません。しかし、私は、最近の標準的なコンパイラが、標準的な最適化としてこれを行うだろうと考えています。それはまた、別のポインタを持っているかもしれません、私は[indr]に設定してからインデックスを付けて小さな勝利かもしれません。

これらの両方に注意するのはかなり慎重なベンチマークが必要です。

Answer 4

あなたはよく見えますか？組み立てを避けたい場合は、シンプルなループをシンプルに保つことが最善です。 GCCはスマートです。あなたのコードが何をしたいのかが分かっていれば、それを最適化するのが一般的です。しかし、プロダクションコードでは一般的ではない派手なやり方をすれば、あなたが「本当に意味する」ものを推測するのは難しいかもしれません。実際、そのようにあなたのコードが何かのように見える一時的にキャッシュI[indr+indc]でいくつかの勝利を見つけるかもしれないものをdostuffによって

...

char t = I[indr+indc]; 
// do stuff 
I[indr+indc] = t; 

このコードは（私はあなたがでていると仮定悪化し実行しません少なくとも基本的な最適化はオンになっていますが）do stuffが十分に上手くいれば、より良い結果が得られます（必要な場合は私が詳しく説明できます）。

他の人が単純な数学をループから取り除くのを聞かないでください。本当に必要はありません。 -O1で生成されたアセンブリを見ると、毎回これが実行されることがわかります。これは、最も安価な最適化の1つです。

Answer 5

最も内側のループをアンロールできます。読みやすさは失われますが、CPUのキャッシュとプリフェッチキューはより良い処理を行います。これはいつも真実ですが、どれくらいのスピードが得られるか分かりません。 indcとindrの両方をレジスタ変数として宣言し、(height-1)*widthの再計算を避けて、代わりに一時変数に保持してください。あなたがループ内INDRを使用する必要がある、またはpostdecrementingの代わりにpredecrementingない場合は

Answer 6

// DragonLord style: 
float *ic_p = I + (width * height) - 1; // fencepost 
// Start at the end, and work backwards 
// assumes I is 0-based and wraps, is contiguous 

for (indr=(height -1) * width; indr>=0; indr-=width) { 
// Sadly cannot test on indr -= width here 
// as the 0 pass is needed for the loop 
     for (indc=width; indc--;){ 
     // Testing on postdecrement 
     // allows you to use the 0 value one last time before testing it FTW 
      // indr and indc are both 0-based inside the loop for you 
      // e.g. indc varies from (width-1) down to 0 
      // due to postdecrement before usage 
      printf("I[ %d + %d ] == %f \n", indr, indc, *ic_p); 
      // always use pointers in C/C++ for speed, we are not Java 
      *ic_p-- = dostuff ; 
     } 
    } 

パフォーマンスがわずかに0に向けて高さからカウントダウンすることによって改善することができる...乗算がクロックサイクルをたくさん食べて、知っていますindcは1のベースのindcで取得できる場合、indcは（幅+1）で初期化する必要があります。

for (indc=(width+1); --indc;){