☰

ちょうど 8192 個の要素をループするときにプログラムが遅くなるのはなぜですか? 質問する

tag-icon • tag-icon c++ performance memory-management gcc
ちょうど 8192 個の要素をループするときにプログラムが遅くなるのはなぜですか? 質問する

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

ベストアンサー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.5GHz

元のコード:

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

交換された外側のループ:

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

おすすめ記事