c++ - 条件 - プログラミング 無限ループ




正確に8192個の要素をループするとき、プログラムが遅くなるのはなぜですか? (2)

Visual C ++コンパイラでは、デフォルトのQt Creatorのインストールで使用されているので、以下のテストが行​​われています(最適化フラグがないと思います)。 GCCを使用している場合、Mysticalのバージョンと私の「最適化された」コードに大きな違いはありません。 結論として、コンパイラの最適化は、人間よりもマイクロ最適化を優先して扱うことになります(私が最後に)。 残りの部分は参考にしておきます。

このように画像を処理するのは効率的ではありません。 単一次元の配列を使用する方がよいでしょう。 すべてのピクセルを処理することは、1つのループで行われます。 ポイントへのランダムアクセスは、以下を使用して行うことができます。

pointer + (x + y*width)*(sizeOfOnePixel)

この特定のケースでは、3つのピクセルグループの合計を3回ずつ使用するため、3つのピクセルグループの合計を計算してキャッシュする方が優れています。

私はいくつかのテストをしたし、共有する価値があると思う。 各結果は平均5回のテストです。

user1615209のオリジナルコード:

8193: 4392 ms
8192: 9570 ms

神秘的なバージョン:

8193: 2393 ms
8192: 2190 ms

1D配列を使用した2回のパス:最初は水平総和、2番目は垂直和と平均です。 3つのポインタを持つ2回のアドレス指定と、このようなインクリメントのみ:

imgPointer1 = &avg1[0][0];
imgPointer2 = &avg1[0][SIZE];
imgPointer3 = &avg1[0][SIZE+SIZE];

for(i=SIZE;i<totalSize-SIZE;i++){
    resPointer[i]=(*(imgPointer1++)+*(imgPointer2++)+*(imgPointer3++))/9;
}

8193: 938 ms
8192: 974 ms

2Dは1D配列を使用し、次のようにアドレス指定します。

for(i=SIZE;i<totalSize-SIZE;i++){
    resPointer[i]=(hsumPointer[i-SIZE]+hsumPointer[i]+hsumPointer[i+SIZE])/9;
}

8193: 932 ms
8192: 925 ms

1回のキャッシュで水平にキャッシュすると1行だけ加算され、キャッシュに残ります。

// Horizontal sums for the first two lines
for(i=1;i<SIZE*2;i++){
    hsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];
}
// Rest of the computation
for(;i<totalSize;i++){
    // Compute horizontal sum for next line
    hsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];
    // Final result
    resPointer[i-SIZE]=(hsumPointer[i-SIZE-SIZE]+hsumPointer[i-SIZE]+hsumPointer[i])/9;
}

8193: 599 ms
8192: 652 ms

結論:

  • いくつかのポインタとちょうど増分を使用する利点はありません(私はそれが速かったと思いました)
  • 水平の合計をキャッシュすることは、それらを数回計算するよりも優れています。
  • 2回のパスは3倍速くはなく、2回だけです。
  • シングルパスと中間結果のキャッシュの両方を使用して3.6倍高速化することが可能です

はるかに良いことができると確信しています。

NOTE私は、Mysticalの優れた答えで説明されたキャッシュの問題ではなく、一般的なパフォーマンスの問題を対象とするためにこの答えを書いたことに注意してください。 最初は疑似コードでした。 私はコメントでテストをするように求められました...ここでは、完全にリファクタリングされたバージョンのテストがあります。

ここに問題のプログラムからの抜粋があります。 行列img[][]はサイズSIZE×SIZEを持ち、次のときに初期化されます。

img[j][i] = 2 * j + i

次に、行列res[][]作成します。ここの各フィールドは、imgマトリックス内の9個のフィールドの平均値になります。 単純化のため、境界線は0のままです。

for(i=1;i<SIZE-1;i++) 
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        for(k=-1;k<2;k++) 
            for(l=-1;l<2;l++) 
                res[j][i] += img[j+l][i+k];
        res[j][i] /= 9;
}

それがプログラムのすべてです。 完全性のために、これは前に来るものです。 後にコードはありません。 ご覧のとおり、初期化だけです。

#define SIZE 8192
float img[SIZE][SIZE]; // input image
float res[SIZE][SIZE]; //result of mean filter
int i,j,k,l;
for(i=0;i<SIZE;i++) 
    for(j=0;j<SIZE;j++) 
        img[j][i] = (2*j+i)%8196;

基本的に、このプログラムは、SIZEが2048の倍数であるとき、例えば実行時間のように遅いです:

SIZE = 8191: 3.44 secs
SIZE = 8192: 7.20 secs
SIZE = 8193: 3.18 secs

コンパイラはGCCです。 私が知っていることから、これはメモリ管理のためですが、私はその件についてあまり気にしていません。私はここでそれを求めています。

またこれを修正する方法もいいかもしれませんが、誰かがこれらの実行時間を説明できるとすれば、私はすでに十分満足できるでしょう。

私はすでにmalloc / freeについて知っていますが、問題は使用されるメモリの量ではなく、単に実行時間なので、どのように役立つか分かりません。


この違いは、次の関連する質問と同じスーパーアライメントの問題が原因です。

  • なぜ512x512の行列を転置するのが513x513の行列を転置するよりもずっと遅いのですか?
  • 行列の乗算:行列のサイズの差が小さく、タイミングの差が大きい

しかしそれは、コードにもう一つの問題があるからです。

元のループから開始:

for(i=1;i<SIZE-1;i++) 
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        for(k=-1;k<2;k++) 
            for(l=-1;l<2;l++) 
                res[j][i] += img[j+l][i+k];
        res[j][i] /= 9;
}

最初に、2つの内部ループが自明であることに気づく。 次のように展開できます。

for(i=1;i<SIZE-1;i++) {
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        res[j][i] += img[j-1][i-1];
        res[j][i] += img[j  ][i-1];
        res[j][i] += img[j+1][i-1];
        res[j][i] += img[j-1][i  ];
        res[j][i] += img[j  ][i  ];
        res[j][i] += img[j+1][i  ];
        res[j][i] += img[j-1][i+1];
        res[j][i] += img[j  ][i+1];
        res[j][i] += img[j+1][i+1];
        res[j][i] /= 9;
    }
}

それで、私たちが興味を持っている2つの外側ループを残します。

今度は、この問題で同じ問題が発生していることがわかります.2次元配列を反復処理するときに、ループの順序がパフォーマンスに影響を与えるのはなぜですか?

行単位ではなく列単位で行列を繰り返します。

この問題を解決するには、2つのループを交換する必要があります。

for(j=1;j<SIZE-1;j++) {
    for(i=1;i<SIZE-1;i++) {
        res[j][i]=0;
        res[j][i] += img[j-1][i-1];
        res[j][i] += img[j  ][i-1];
        res[j][i] += img[j+1][i-1];
        res[j][i] += img[j-1][i  ];
        res[j][i] += img[j  ][i  ];
        res[j][i] += img[j+1][i  ];
        res[j][i] += img[j-1][i+1];
        res[j][i] += img[j  ][i+1];
        res[j][i] += img[j+1][i+1];
        res[j][i] /= 9;
    }
}

これにより、すべての非シーケンシャルアクセスが完全に排除されるため、2の大きな累乗でランダムなスローダウンが発生しなくなりました。

コアi7 920 @ 3.5 GHz

元のコード:

8191: 1.499 seconds
8192: 2.122 seconds
8193: 1.582 seconds

交換された外部ループ:

8191: 0.376 seconds
8192: 0.357 seconds
8193: 0.351 seconds




gcc