1 
for (int i = 0; i < 5000; i++)
   for (int j = 0; j < 5000; j++)
   {
      for (int ii = 0; ii < 20; ii++)
          for (int jj = 0; jj < 20; jj++)
           {
               int num = matBigger[i+ii][j+jj];
               // Extract range from this.
               int low = num & 0xff;
               int high = num >> 8;
               if (low < matSmaller[ii][jj] && matSmaller[ii][jj] > high)
                  // match found
           }
   }

マシンは x86_64、32kb L1 キャッシュ、256Kb L2 キャッシュです。

このコードを最適化するにはどうすればよいかについての指針はありますか?

EDIT元の問題の背景: MXN マトリックスで amxn サブマトリックスを見つける最速の方法

4

6 に答える 6

4

私が最初に試みることは、andループをandループの外側に移動するiiことjjです。このようにして、とループの2500万回の反復で同じ要素を使用します。つまり、あなた（または運が良ければコンパイラ）は、これらのループの外でそれらへのアクセスを増やすことができます。ijmatSmallerij

for (int ii = 0; ii < 20; ii++)
  for (int jj = 0; jj < 20; jj++)
    int smaller = matSmaller[ii][jj];
    for (int i = 0; i < 5000; i++)
      for (int j = 0; j < 5000; j++) {
        int num = matBigger[i+ii][j+jj];
        int low = num & 0xff;
        if (low < smaller && smaller > (num >> 8)) {
          // match found
        }
      }

これは速いかもしれません（配列へのアクセスが少ないためmatSmaller）、または遅いかもしれません（matBigger配列へのアクセスのパターンを変更したため、キャッシュフレンドリーではなくなった可能性があります）。同様の方法は、iiループを外側iに移動してj巻き上げることですが、ループは内側matSmaller[ii]のままにしておきます。jj経験則では、以前のインデックスよりも、内部ループ内の多次元配列の最後のインデックスをインクリメントする方がキャッシュに適しています。ですから、私たちは修正するよりも「幸せ」でjjあり、修正するjよりもiiですi。

私が試してみたい2番目のこと-タイプはmatBigger何ですか？その中の値は16ビットしかないように見えるので、asintとasの両方を試してください(u)int16_t。int整列アクセスが高速であるため、前者の方が高速である可能性があります。一度に多くのアレイがキャッシュに収まるため、後者の方が高速になる可能性があります。

の初期の分析で検討できるより高いレベルの事柄がいくつかありますsmaller。たとえば、その場合、との値を0調べる必要はありません。これは常にfalseであるためです。matBiggeriijjnum & 0xff < 0

「物事を推測し、それらがより速いかどうかを確認する」よりもうまくやるには、どのラインが最もホットであるかをスターターが知る必要があります。つまり、プロファイラーが必要です。

于 2012-05-16T13:22:55.443 に答える
2

基本的なアドバイス:

  1. プロファイルを作成して、ホットスポットがどこにあるかを知ることができます。
  2. キャッシュの局所性と、ループ順序から生じるアドレスについて考えてください。
  3. moreconstを最も内側のスコープで使用して、コンパイラにさらにヒントを与えます。
  4. テストが失敗したhighかどうかを計算しないように、分割してみてください。low
  5. 単純なインクリメントへの最も内側のステップへのオフセットを明示的に維持してみてくださいmatBigger。matSmaller
于 2012-05-16T12:27:01.643 に答える
1

最善の方法は、コードが何をすべきかを理解し、この問題に対して別のアルゴリズムが存在するかどうかを確認することです。

それとは別に：

  • 一致するエントリが存在するかどうかだけに関心がある場合は、 の位置で 3 つのループすべてから抜け出すようにして// match foundください。
  • データが最適な方法で保存されていることを確認してください。operator()(int,int,int)それはすべてあなたの問題に依存しますが、要素にアクセスするためのサイズ 5000*5000*20 の配列とオーバーロードを 1 つだけ持つ方が効率的です。
于 2012-05-16T12:27:36.883 に答える
0

ここには繰り返しがたくさんあるようです。最適化の1つは、重複する作業の量を減らすことです。ペンと紙を使用して、matBigger「i」インデックスを次のように繰り返し表示しています。

[0 + 0], [0 + 1], [0 + 2], ..., [0 + 19],
         [1 + 0], [1 + 1], ..., [1 + 18], [1 + 19]
                  [2 + 0], ..., [2 + 17], [2 + 18], [2 + 19]

ご覧のとおり、何度もアクセスされる場所があります。また、反復回数を掛けると、内部コンテンツがアクセスされることを示します：20 * 20 * 5000 * 5000、または10000000000（10E + 9）回。それは沢山！

したがって、10E9命令（実行（パイプライン）キャッシュやデータキャッシュの最適化など）の実行を高速化するのではなく、反復回数を減らしてみてください。

コードは、範囲内の数値（最小値より大きく、最大範囲値より小さい）のマトリックスを検索しています。

これに基づいて、別のアプローチを試してください。

  1. 検索値が低い値よりも大きいすべての座標を見つけて覚えておいてください。これらをアンカーポイントと呼びましょう。
  2. アンカーポイントごとに、範囲外のアンカーポイントの後の最初の値の座標を見つけます。

目的は、重複アクセスの数を減らすことです。アンカーポイントにより、ワンパススキャンが可能になり、範囲の検索やアンカー値を含むMxNマトリックスの決定などの他の決定が可能になります。

matBiggerもう1つのアイデアは、とを含む新しいデータ構造を作成することです。これらのデータ構造はmatSmaller、検索用にさらに最適化されています。

たとえば、次の一意の値ごとに{値、座標リスト}エントリを作成しますmatSmaller。

  Value    coordinate list
    26 -> (2,3), (6,5), ..., (1007, 75)
    31 -> (4,7), (2634, 5), ...

これで、このデータ構造を使用して、値を検索しmatSmaller、それらの場所をすぐに知ることができます。matBiggerしたがって、このデータ構造で一意の値をそれぞれ検索できます。これにより、マトリックスへのアクセス数が再び減少します。

于 2012-05-16T18:32:21.260 に答える
0

matSmallerととは何matBiggerですか? それらをに変更してみてくださいmatBigger[i+ii * COL_COUNT + j+jj]

于 2012-05-16T13:42:39.397 に答える
0

ループを再配置して、内側のループとしてより多くのカウントを持たせることについて、Steve に同意します。コードはロードと比較のみを行っているため、時間のかなりの部分がポインター演算に使用されていると思います。スティーブの答えを次のように変えてみてください:

for (int ii = 0; ii < 20; ii++)
  {
  for (int jj = 0; jj < 20; jj++)
    {
    int smaller = matSmaller[ii][jj];
    for (int i = 0; i < 5000; i++)
      {
      int *pI = &matBigger[i+ii][jj];
      for (int j = 0; j < 5000; j++)
        {
        int num = *pI++;
        int low = num & 0xff;
        if (low < smaller && smaller > (num >> 8)) {
          // match found
        } // for j
      } // for i
    } // for jj
  } // for ii

64 ビット モードであっても、C コンパイラは必ずしもすべてを適切にレジスタに保持できるとは限りません。配列へのアクセスを単純なポインターのインクリメントに変更することで、コンパイラーの仕事が効率的なコードを生成しやすくなります。

編集: @unwind が基本的に同じことを提案していることに気付きました。考慮すべきもう 1 つの問題は、比較の統計です。低い比較と高い比較のどちらがより可能性が高いですか? 可能性の低いテストが最初になるように、条件ステートメントを配置します。

于 2012-05-16T16:37:15.307 に答える