780

問題のプログラムからの抜粋です。行列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 については既に知っていますが、問題はメモリの使用量ではなく、単に実行時間であるため、それがどのように役立つかわかりません。

4

2 に答える 2

986

違いは、次の関連する質問からの同じスーパーアライメントの問題によって引き起こされます。

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

元のループから始めます。

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 つの外側のループが残りました。

これで、この質問でも問題が同じであることがわかります。なぜループの順序が 2D 配列を反復処理するときにパフォーマンスに影響するのですか?

行単位ではなく列単位で行列を反復しています。

この問題を解決するには、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
于 2012-09-04T14:43:25.417 に答える
57

次のテストは、デフォルトの Qt Creator インストールで使用される Visual C++ コンパイラで行われました (最適化フラグはないと思います)。GCC を使用する場合、Mystical のバージョンと私の「最適化された」コードの間に大きな違いはありません。したがって、結論は、コンパイラの最適化は人間よりもマイクロ最適化をうまく処理するということです（ついに私）。残りの回答は参照用に残します。

この方法で画像を処理するのは効率的ではありません。1 次元配列を使用することをお勧めします。すべてのピクセルの処理は、1 つのループで行われます。ポイントへのランダムアクセスは、次を使用して実行できます。

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

この特定のケースでは、3 つのピクセル グループの合計を水平方向に計算してキャッシュすることをお勧めします。これらはそれぞれ 3 回使用されるからです。

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

user1615209 による元のコード:

8193: 4392 ms
8192: 9570 ms

Mystical のバージョン:

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

2 つは 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 倍の速度を実現できます。

もっとうまくやれると確信しています。

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

于 2012-09-04T17:00:36.953 に答える