[解決済み] 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は既に知っていますが、問題は使用するメモリの量ではなく、単に実行時間なので、それがどう役に立つのかわかりません。

解決方法は？

この違いは、以下の関連質問と同じスーパーアライメントの問題によるものです。

• 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のべき乗でランダムにスローダウンすることがなくなりました。

Core i7 920 @ 3.5 GHz

オリジナルのコードです。

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

Outer-Loopsを入れ替えたもの。

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