C++のパフォーマンス：特定のセルに特定の値を持つメモリブロックをチェックする

Question

私は2Dビンパッキングアルゴリズムを研究しています。私はPHPの性能に関してsimilar questionに質問しました。パックするのが遅すぎました。そして、コードはC++に変換されました。

まだかなり遅いです。どのような私のプログラムが行うことは、結果として動的メモリのブロックを割り当てると「O」の文字でそれらを移入され

char* bin; 
bin = new (nothrow) char[area]; 
if (bin == 0) { 
    cout << "Error: " << area << " bytes could not be allocated"; 
    return false; 
} 
for (int i=0; i<area; i++) { 
    bin[i]='o'; 
} 

の

次に、プログラムチェックの異なる組み合わせ（その大きさは、私のデータセットの1キロバイトと30キロバイトの間にあります）現在のメモリブロックの中の 'x'文字。

void place(char* bin, int* best, int width) 
{ 
    for (int i=best[0]; i<best[0]+best[1]; i++) 
     for (int j=best[2]; j<best[2]+best[3]; j++) 
      bin[i*width+j] = 'x'; 
} 

非重複をチェックする関数の1つは、実行時に何百万回も呼び出されます。

bool fits(char* bin, int* pos, int width) 
{ 
    for (int i=pos[0]; i<pos[0]+pos[1]; i++) 
     for (int j=pos[2]; j<pos[2]+pos[3]; j++) 
      if (bin[i*width+j] == 'x') 
       return false; 
    return true; 
} 

他のすべてのものは、実行時の唯一のパーセントを取るので、私はこれらの2人の男（フィットと場所）より速くを作成する必要があります。犯人は誰ですか？

私は2つのオプション 'x'と 'o'しか持っていないので、charがとるバイト全体の代わりにちょうど1ビットを使うことができます。しかし、私はスピードにもっと関心があります、あなたはそれが物事をより速くすると思いますか？

ありがとうございます！

更新：int* posをrect pos（bestと同じ）に置き換えました。これは推奨されるMSalterのとおりです。最初は改善が見られましたが、より大きなデータセットでさらにテストしました。通常のランタイムに戻っているようです。他のテクニックを試してみましょう。

更新：memsetとmemchrを使用して約2回スピードアップしました。 'x'と 'o'を '\ 1'と '\ 0'に置き換えても改善は見られませんでした。 __restrictも役に立たなかった。全体的に、私はアルゴリズム自体にいくつかの改良を加えたので、プログラムのパフォーマンスに満足しています。私はまだビットマップを使って-02（-03）でコンパイルしようとしています...もう一度皆さんに感謝します。

Answer 1

ビットマップは、メモリの消費量が少ないため、キャッシュからのメモリ参照が増えるため、速度も向上します。また、placeにbestの要素をローカル変数にコピーして、binへの書き込みがbestに変更されないことをコンパイラーが認識できるようにすることができます。あなたのコンパイラがrestrictのいくつかのスペルをサポートしている場合は、それを使うこともできます。 placeの内部ループをmemsetライブラリ関数に置き換えて、fitsの内部ループをmemchrに置き換えることもできます。しかし、それらは大きなパフォーマンスの改善ではないかもしれません。

Answer 2

最高の可能性は、より複雑なアルゴリズムを使用することです。

でも、現在のアルゴリズムでもスピードアップが可能です。一度に〜16バイトをテストするためにSSE命令を使用してみてください。また、1つの大きな割り当てを自分で分割することもできます。これはライブラリアロケータを使用するよりも速くなります（ライブラリアロケータはブロックを個別に解放する利点があります。あなたはその機能が必要と思わない）。

Answer 3

[もちろん：それをプロファイルしてください！]

バイトではなくビットを使用すると、最初のインスタンスでは高速になりません。

ただし、文字を使用すると、4〜8バイトのブロックを符号なし32ビットまたは64ビットの整数にキャストできます（アラインメントを処理することを確認してください）。その値を 'oooo'または 'oooooooo'ブロック内でそれは非常に速い比較を可能にする。

整数アプローチを廃止したことで、ビットアプローチで同じことができ、1回の比較で64ビットと言うことができることがわかります。それは確かに本当のスピードアップを与えるはずです。

Answer 4

まず、コンパイラに最適化するように覚えていますか？

そして、ゆっくりとした配列のインデックス境界チェックなどをオフにしますか？

これで、一度に32ビットまたは64ビットを設定またはクリアできるので、バイナリ値を個々のビットとして表すことで大幅なスピードアップが実現します。

また、私は動的割り当てがかなりのオーバーヘッドを与えると想定する傾向がありますが、明らかに測定して、そうでないことがわかりました。しかし、メモリ管理が実際に時間に大きく貢献している場合、ソリューションは使用パターンに少し依存します。しかし、おそらくあなたのコードは、スタックのようなalloc/freeの振る舞いを生成します。その場合、割り当てをほぼ無駄なく最適化することができます。ちょうど大きなチャンクを最初に割り振り、そこからスタック状のものをサブアロケートしてください。その例を実現しないかもしれないコンパイラをエイリアシング可能に

void place(char* bin, int* best, int width) 
{ 
    for (int i=best[0]; i<best[0]+best[1]; i++) 
     for (int j=best[2]; j<best[2]+best[3]; j++) 
      bin[i*width+j] = 'x'; 
} 

：

あなたの現在のコードを考慮するとbest[0]はループ中に一定になります。だから、

、それを伝える：

void place(char* bin, int const* best, int const width) 
{ 
    int const maxY = best[0] + best[1]; 
    int const maxX = best[2] + best[3]; 

    for(int y = best[0]; y < maxY; ++y) 
    { 
     for(int x = best[2]; x < maxX; ++x) 
     { 
      bin[y*width + x] = 'x'; 
     } 
    } 
} 

おそらくあなたのコンパイラが内部ループの外にy*width計算をホイストしますが、なぜそれがまたそれを行うこと言わないで：

void place(char* bin, int* best, int const width) 
{ 
    int const maxY = best[0]+best[1]; 
    int const maxX = best[2]+best[3]; 

    for(int y = best[0]; y < maxY; ++y) 
    { 
     int const startOfRow = y*width; 

     for(int x = best[2]; x < maxX; ++x) 
     { 
      bin[startOfRow + x] = 'x'; 
     } 
    } 
} 

このマニュアルの最適化を（他のルーチンにも適用されます）場合によっては、コンパイラーの賢さに依存します。

次に、十分に役に立たない場合は、内部ループをstd::fill（またはmemset）に置き換えて、1つの行全体をスワップしてください。

そして、それが助けにならないか、またはそれほど助けにならない場合は、ビットレベル表現に切り替えます。

すべてのPCにはビットレベルの操作を最適化するためのハードウェアサポート、つまりグラフィックスアクセラレータカード（以前はブリッタチップと呼ばれていました）があります。したがって、画像ライブラリと白黒ビットマップを使用するだけでよいでしょう。しかし、あなたの長方形が小さいので、私はセットアップのオーバーヘッドが実際の操作の速度を超過するかどうかわからない–を測定する必要があります。 ;-)

乾杯& hth。、私が期待する

Answer 5

最大の改善は非自明な変化からです：

// changed pos to class rect for cleaner syntax 
bool fits(char* bin, rect pos, int width) 
{ 
    if (bin[pos.top()*width+pos.left()] == 'x') 
       return false; 
    if (bin[(pos.bottom()-1*width+pos.right()] == 'x') 
       return false; 
    if (bin[(pos.bottom()*width+pos.left()] == 'x') 
       return false; 
    if (bin[pos.top()*width+pos.right()] == 'x') 
       return false; 

    for (int i=pos.top(); i<=pos.bottom(); i++) 
     for (int j=pos.left(); j<=pos.right(); j++) 
      if (bin[i*width+j] == 'x') 
       return false; 
    return true; 
} 

確かに、あなたは二回bin[(pos.bottom()-1*width+pos.right()]をテストしています。しかし、最初に行うことはアルゴリズムのほうがはるかに早いです。ボックスを追加すると、隣接するビン間に強い相関があることを意味します。そのため、最初にコーナーを確認することで、多くの場合早く返されることがあります。途中で5番目の小切手を追加することも考えられます。

Answer 6

プロファイラを使用することについての義務的な声明を超えて、 ビットマップで物を置き換える上のアドバイスは、非常に良いアイデアです。それは..あなたにアピールしていない場合、それはより少ないマシンコードにコンパイルするよう

、通常memsetのが速くなります

memset(bin, 'o', area); 

では

for (int i=0; i<area; i++) { 
    bin[i]='o'; 
} 

交換を検討してください。

また

void place(char* bin, int* best, int width) 
{ 
    for (int i=best[0]; i<best[0]+best[1]; i++) 
     for (int j=best[2]; j<best[2]+best[3]; j++) 
      bin[i*width+j] = 'x'; 
} 

ループの1つを除去することによってroom.for改善

void place(char* bin, int* best, int width) 
{ 
    for (int i=best[0]; i<best[0]+best[1]; i++) 

     memset(      (i * width) + best[2], 
       'x', 
       (best[2] + best[3]) - (((i * width)) + best[2]) + 1); 
} 

のビットを有しています。

最後のアイデアは、データ表現を変更することです。 あなたの 'x'文字の代わりにあなたの 'o'と '\ 1'の代わりに '\ 0'文字を使用することを検討してください。これはビットマップのようなものです。

このようにテストすることができます。

if (best[1]) 
{ 
    // Is a 'x' 
} 
else 
{ 
    // Is a 'o' 
} 

これにより、高速なコードが生成される可能性があります。再びプロファイラーはあなたの友人です:)

この表現は、単純に一連の文字を合計して、いくつの「x」と「o」があるかを判断することもできます。あなたに

int sum = 0; 
for (int i = 0; i < 12; i++) 
{ 
    sum += best[i]; 
} 

cout << "There are " << sum << "'x's in the range" << endl; 

運のベストを

悪。

Answer 7

基本タイプに2つの値がある場合は、まずboolを使用します。コンパイラでは2つの値があることが分かり、いくつかのものを最適化することができます。 可能な限りconstを追加します（例えば、fits（bool const *、...）のパラメータ）。

Answer 8

私はメモリキャッシュブレイクについて考えるでしょう。これらの関数は、より大きな行列の中の部分行列を通って実行されます。幅と高さが何倍にもなると思います。 これは、小さな行列の行が連続したメモリであることを意味しますが、行間ではメモリキャッシュのページが壊れる可能性があります。 可能な限りサブ行列要素を互いに近づけるような順序で大きな行列セルをメモリ内に表現することを検討してください。これは、連続するフルラインのベクトルを保持する代わりに行われます。最初の選択肢は私の頭に浮かびます。大行列を{2^i、2^i}の行列{左上、右上、左下、右下}の行列に再帰的に分割することです。

1） すなわち、あなたの行列は、サイズX * Yの配列で表されるサイズ[X、Y]は、要素[X、Y]はアレイ内の位置（x、y）である場合：

代わりに（のy * X + X）の

使用：

unsigned position(rx, ry) 
{ 
    unsigned x = rx; 
    unsigned y = rx; 
    unsigned part = 1; 
    unsigned pos = 0; 
    while((x != 0) && (y != 0)) { 
    unsigned const lowest_bit_x = (x % 2); 
    unsigned const lowest_bit_y = (y % 2); 
    pos += (((2*lowest_bit_y) + lowest_bit_x) * part); 
    x /= 2; //throw away lowest bit 
    y /= 2; 
    part *= 4; //size grows by sqare(2) 
    } 
    return pos; 
} 

は、私はちょうど私が何を意味するかを説明するために、このコードをチェックしませんでした。 必要な場合は、より速く実装する方法も見つけてください。

あなたが割り当てる配列はX * Yよりも大きく、可能な限り小さい（2 ^（2 * k））でなければならないことに注意してください.XとYがほぼ同じ大きさのスケールでなければ無駄です。しかし、それは最初に大きな行列をsqauresにさらに分割することで解決できます。

そして、キャッシュベンチは、より複雑な位置（x、y）を上回るかもしれません。

2）次に、fits（）およびplace（）でサブ行列の要素を実行する最適な方法を見つけようとします。それが何であるかはまだ分かりませんが、必ずしも今のようにはなりません。基本的に、サイズ[x、y]の部分行列は、配列表現内で連続しているy * log（x）* log（y）ブロック以下に分割する必要がありますが、 4 * x * y。最終的に、メモリキャッシュページよりも小さい行列の場合、元のコードがy回に壊れることがありますが、4つ以上のメモリキャッシュブレークは発生しません。