正確に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

「水曜日」シーズン1の中心には大きなミステリーがあります

「水曜日」シーズン1の中心には大きなミステリーがあります

Netflixの「水曜日」は、典型的な10代のドラマ以上のものであり、実際、シーズン1にはその中心に大きなミステリーがあります.

ボディーランゲージの専門家は、州訪問中にカミラ・パーカー・ボウルズが輝くことを可能にした微妙なケイト・ミドルトンの動きを指摘しています

ボディーランゲージの専門家は、州訪問中にカミラ・パーカー・ボウルズが輝くことを可能にした微妙なケイト・ミドルトンの動きを指摘しています

ケイト・ミドルトンは、州の夕食会と州の訪問中にカミラ・パーカー・ボウルズからスポットライトを奪いたくなかった、と専門家は言う.

一部のファンがハリー・スタイルズとオリビア・ワイルドの「非常に友好的な」休憩が永続的であることを望んでいる理由

一部のファンがハリー・スタイルズとオリビア・ワイルドの「非常に友好的な」休憩が永続的であることを望んでいる理由

一部のファンが、オリビア・ワイルドが彼女とハリー・スタイルズとの間の「難しい」が「非常に友好的」な分割を恒久的にすることを望んでいる理由を見つけてください.

エリザベス女王の死後、ケイト・ミドルトンはまだ「非常に困難な時期」を過ごしている、と王室の専門家が明らかにする 

エリザベス女王の死後、ケイト・ミドルトンはまだ「非常に困難な時期」を過ごしている、と王室の専門家が明らかにする&nbsp;

エリザベス女王の死後、ケイト・ミドルトンが舞台裏で「非常に困難な時期」を過ごしていたと伝えられている理由を調べてください.

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セント ヘレナ島のジェイコブズ ラダーは 699 段の真っ直ぐ上る階段で、頂上に到達すると証明書が発行されるほどの難易度です。

The Secrets of Airline Travel Quiz

The Secrets of Airline Travel Quiz

Air travel is far more than getting from point A to point B safely. How much do you know about the million little details that go into flying on airplanes?

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

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

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

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

Total War:Warhammer:Kotakuレビュー

Total War:Warhammer:Kotakuレビュー

私はこのゲームを嫌う準備ができていました。先週の前に、Total War:Warhammerについての私の考えがありました:それでもここに私は、私の手にある完成品であり、私は変わった男です。

涙の道:軍事化された帝国主義勢力がスタンディングロックキャンプを占領

涙の道:軍事化された帝国主義勢力がスタンディングロックキャンプを占領

スタンディングロックスー族のメンバーと水の保護者は、ノースダコタ州のスタンディングロックにあるオセティサコウィンキャンプを去ります。(Twitter経由のCNNスクリーンショット)火と煙がスカイラインを覆い、スタンディングロックスー族のメンバーと水の保護者が、聖なるものを守りながら建てた家、オセティサコウィン(セブンカウンシルファイアーズ)キャンプから行進し、太鼓を打ち、歌い、祈りました。ダコタアクセスパイプラインとしても知られる「ブラックスネーク」からの土地。

シアーズとKマートはイヴァンカ・トランプの商品を自分たちで取り除いています

シアーズとKマートはイヴァンカ・トランプの商品を自分たちで取り除いています

写真:APシアーズとKマートは、イヴァンカ・トランプのトランプホームアイテムのコレクションも、誰も購入したくないために削除しました。シアーズとKマートの両方の親会社であるシアーズホールディングスは、土曜日のABCニュースへの声明で、彼らが気にかけていると辛抱強く説明しましたトランプラインを売り続けるにはお金を稼ぐことについてあまりにも多く。

ポテトチップスでたった10分でスペインのトルティーヤを作る

ポテトチップスでたった10分でスペインのトルティーヤを作る

伝統的なスペインのトルティーヤは通常、オリーブオイルで柔らかくなるまで調理されたポテトから始まります(30分以上かかる場合があります)が、ケトルで調理されたポテトチップスの助けを借りてわずか10分でテーブルに置くことができます。上のビデオはすべてがバラバラにならないように裏返す方法を含め、レシピ全体を説明しますが、必要なのは4〜5個の卵と3カップのケトルチップスだけです。

ケイト・ミドルトンとウィリアム王子は、彼らが子供たちと行っているスパイをテーマにした活動を共有しています

ケイト・ミドルトンとウィリアム王子は、彼らが子供たちと行っているスパイをテーマにした活動を共有しています

ケイト・ミドルトンとウィリアム王子は、子供向けのパズルの本の序文を書き、ジョージ王子、シャーロット王女、ルイ王子と一緒にテキストを読むと述べた.

事故で押しつぶされたスイカは、動物を喜ばせ水分補給するために野生生物保護団体に寄付されました

事故で押しつぶされたスイカは、動物を喜ばせ水分補給するために野生生物保護団体に寄付されました

Yak's Produce は、数十個のつぶれたメロンを野生動物のリハビリ専門家であるレスリー グリーンと彼女のルイジアナ州の救助施設で暮らす 42 匹の動物に寄付しました。

デミ・ロヴァートは、新しいミュージシャンのボーイフレンドと「幸せで健康的な関係」にあります: ソース

デミ・ロヴァートは、新しいミュージシャンのボーイフレンドと「幸せで健康的な関係」にあります: ソース

8 枚目のスタジオ アルバムのリリースに向けて準備を進めているデミ ロヴァートは、「スーパー グレート ガイ」と付き合っている、と情報筋は PEOPLE に確認しています。

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

イーサン プラスの誕生日のお祝いは、TLC のウェルカム トゥ プラスビルのシーズン 4 のフィナーレで、戦争中の母親のキム プラスと妻のオリビア プラスを結びつけました。

仕事の生産性を高める 8 つのシンプルなホーム オフィスのセットアップのアイデア

仕事の生産性を高める 8 つのシンプルなホーム オフィスのセットアップのアイデア

ホームオフィスのセットアップ術を極めよう!AppExert の開発者は、家族全員が一緒にいる場合でも、在宅勤務の技術を習得しています。祖父や曽祖父が共同家族で暮らしていた頃の記憶がよみがえりました。

2022 年、私たちのデジタル ライフはどこで終わり、「リアル ライフ」はどこから始まるのでしょうか?

20 年前のタイムトラベラーでさえ、日常生活におけるデジタルおよびインターネットベースのサービスの重要性に驚くことでしょう。MySpace、eBay、Napster などのプラットフォームは、高速化に焦点を合わせた世界がどのようなものになるかを示してくれました。

ニューロマーケティングの秘密科学

ニューロマーケティングの秘密科学

マーケティング担当者が人間の欲望を操作するために使用する、最先端の (気味が悪いと言う人もいます) メソッドを探ります。カートをいっぱいにして 3 桁の領収書を持って店を出る前に、ほんの数点の商品を買いに行ったことはありませんか? あなたは一人じゃない。

地理情報システムの日: GIS 開発者として学ぶべき最高の技術スタック

地理情報システムの日: GIS 開発者として学ぶべき最高の技術スタック

私たちが住んでいる世界を確実に理解するには、データが必要です。ただし、空間参照がない場合、このデータは地理的コンテキストがないと役に立たなくなる可能性があります。

Language