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

763
Noname 2012-09-05 03:51.

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

2 answers

962
Mysticial 2012-09-05 04:43.

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

  • 512x512のマトリックスの転置が、513x513のマトリックスの転置よりもはるかに遅いのはなぜですか?
  • 行列の乗算:行列のサイズのわずかな違い、タイミングの大きな違い

しかし、それはコードにもう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の累乗でランダムに速度が低下することはなくなります。


Core 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
57
bokan 2012-09-05 07:00.

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


この方法で画像を処理するのは効率的ではありません。単一次元配列を使用することをお勧めします。すべてのピクセルの処理は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

1D配列を使用し、次のようにアドレス指定する2つのパス:

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の優れた回答で説明されているキャッシュの問題ではなく、一般的なパフォーマンスの問題を対象として作成したことに注意してください。当初、それは単なる擬似コードでした。コメントでテストを行うように依頼されました...これは、テストを含む完全にリファクタリングされたバージョンです。

Related questions

MORE COOL STUFF

ケイト・ブランシェットは3日間一緒に夫と一緒に寝て、25年経ってもまだ夫と結婚しています

ケイト・ブランシェットは3日間一緒に夫と一緒に寝て、25年経ってもまだ夫と結婚しています

ケイト・ブランシェットは、夫に会ったとき、典型的な交際のアドバイスに逆らいました。

マイケルシーンが非営利の俳優である理由

マイケルシーンが非営利の俳優である理由

マイケルシーンは非営利の俳優ですが、それは正確にはどういう意味ですか?

ホールマークスターのコリンエッグレスフィールドがRomaDramaLiveでスリル満点のファンと出会う![エクスクルーシブ]

ホールマークスターのコリンエッグレスフィールドがRomaDramaLiveでスリル満点のファンと出会う![エクスクルーシブ]

特徴的なスターのコリン・エッグレスフィールドは、RomaDrama Liveでのスリル満点のファンとの出会いについて料理しました!加えて、大会での彼のINSPIREプログラム。

「たどりつけば」をオンラインでストリーミングできない理由

「たどりつけば」をオンラインでストリーミングできない理由

ノーザンエクスポージャーが90年代の最も人気のある番組の1つになった理由を確認するには、Blu-rayまたはDVDプレーヤーをほこりで払う必要があります。

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

ドミニカのボイリング湖:アクセスは簡単ではありませんが、ハイキングする価値があります

ドミニカのボイリング湖:アクセスは簡単ではありませんが、ハイキングする価値があります

ドミニカのボイリング湖は、世界で2番目に大きいボイリング湖です。そこにたどり着くまでのトレッキングは大変で長いですが、努力する価値は十分にあります。

私たちの水をきれいに保つのを助けるためにあなたの髪を寄付してください

私たちの水をきれいに保つのを助けるためにあなたの髪を寄付してください

サロンからのヘアトリミングや個人的な寄付は、油流出を吸収して環境を保護するのに役立つマットとして再利用できます。

ホワイトハウスの最も記憶に残る結婚式を見てください

ホワイトハウスの最も記憶に残る結婚式を見てください

過去200年以上の間にホワイトハウスで結婚したのはほんの数人です。彼らは誰でしたか、そしてそこで結婚式を獲得するために何が必要ですか?

Netflixのジョエルマクヘイルとのジョエルマクヘイルショーは、ジョエルマクヘイルにぴったりの車を復活させます

Netflixのジョエルマクヘイルとのジョエルマクヘイルショーは、ジョエルマクヘイルにぴったりの車を復活させます

ジョエル・マクヘイル、マイク・コルター(スクリーンショット:Netflix)「私の神よ、これは1つのことを変えます。」これは、ジョエル・マクヘイルとのジョエル・マクヘイルショーの最後のジョークです。リアリティ番組の嘲笑と寛大なスナキネスの時間は、なじみのある顔を見つけます。

チームロケットは20年ぶりにポケモンシリーズでアッシュを破った

チームロケットは20年ぶりにポケモンシリーズでアッシュを破った

画像経由:@pancakeparadox(Twitter)。1997年にポケモンシリーズが初公開されて以来、チームロケット(またはラテンアメリカではチームロケット)として知られる悪役のグループは、何度もアッシュに直面してきました。

今週の科学技術でトランプがめちゃくちゃになったことすべて

今週の科学技術でトランプがめちゃくちゃになったことすべて

画像:ゲッティ私たち全員が千年もの間生きていて、私たちの体が燃える風によってほこりと長引く悲鳴だけに押し流されたと考えるのは驚くべきことです。私たちがそうしていないことを除いて、それはトランプ政権の最初の週の終わりであり、驚くほど多くの恐ろしいことがすでに起こっています。

あなたの「マイクロピッグ」が代わりに通常のピッグになってしまったとしても驚かないでください

あなたの「マイクロピッグ」が代わりに通常のピッグになってしまったとしても驚かないでください

そして今、あることを手に入れていると思っていたが、まったく別のことをしてしまった男の話。CBSニュースは、彼女が「ミニブタ」であるという誤ったふりをしてエスターを養子にしたカナダ人のスティーブジェンキンスの心温まる物語をもたらします。これは、特にせいぜいゴールデンレトリバーまたはセントバーナードをストラップします。

Zendaya Wishes Boyfriend Tom Holland Happy Birthday with Cuddly Photo: He 'Makes Me the Happiest'

Zendaya Wishes Boyfriend Tom Holland Happy Birthday with Cuddly Photo: He 'Makes Me the Happiest'

Zendaya shared a sweet photo in honor of boyfriend Tom Holland's 26th birthday Wednesday

小さな女性:脳卒中を患った後に病院から解放されたアトランタのジューシーな赤ちゃん:「まだ癒し」

小さな女性:脳卒中を患った後に病院から解放されたアトランタのジューシーな赤ちゃん:「まだ癒し」

シーレン「Ms.JuicyBaby」ピアソンは、先月脳卒中で入院した後、「もう一度たくさんのことをする方法を学ばなければならない」ため、言語療法を受けていることを明らかにしました。

エマストーンは彼女のクリフサイドマリブビーチハウスを420万ドルでリストアップしています—中を見てください!

エマストーンは彼女のクリフサイドマリブビーチハウスを420万ドルでリストアップしています—中を見てください!

オスカー受賞者の世紀半ばの家には、3つのベッドルーム、2つのバス、オーシャンフロントの景色があります。

ジーニー・メイ・ジェンキンスは、母乳育児の経験の中で、彼女は「本当に、本当に落ち込んでいる」と言います

ジーニー・メイ・ジェンキンスは、母乳育児の経験の中で、彼女は「本当に、本当に落ち込んでいる」と言います

ジーニー・メイ・ジェンキンスは、生後4か月の娘、モナコに母乳育児をしていると語った。

投資ノート:Bioscout AU$300万シード

投資ノート:Bioscout AU$300万シード

Bioscoutは、農家を運転席に置くという使命を負っています。Artesian(GrainInnovate)やUniseedと並んで、最新のシードラウンドでチームを支援できることをうれしく思います。問題真菌症による重大な作物の損失は、農民にとって試練であることが証明されています。

リトルマーケットリサーチ1| 2022年のクイックグリンプス遠隔医療市場

リトルマーケットリサーチ1| 2022年のクイックグリンプス遠隔医療市場

遠隔医療は、パンデミック後の時代では新しいものではなく、時代遅れの分野でもありません。しかし、業界を詳しく見ると、需要と供給の強力な持続可能性と、米国で絶え間ない革命となる強力な潜在的成長曲線を示しています。

スタートアップ資金調達環境:タイのスタートアップエコシステムの次は何ですか?

スタートアップ資金調達環境:タイのスタートアップエコシステムの次は何ですか?

2021年は、世界的なベンチャーキャピタル(VC)の資金調達にとって記録的な年でした。DealStreetAsiaによると、東南アジアも例外ではなく、この地域では年間で記録的な25の新しいユニコーンが採掘されました。

ムーアの法則を超えて

ムーアの法則を超えて

計算に対する私たちの欲求とムーアの法則が提供できるものとの間には、指数関数的に増大するギャップがあります。私たちの文明は計算に基づいています—建築と想像力の現在の限界を超える技術を見つけなければなりません。

Language