ビット配列へのアクセスの最適化

Question

私はDippersteinのbitarray.cppクラスを使用して、イメージデータがネイティブに1ピクセル1ビットとして保存されるバイレベル（白黒）イメージで作業します。私はそれぞれ、すべてのビットを反復処理する必要が

は、画像あたり4--9万画素の順に、画像の何百もの上に、forループを使用して、何かのように：

for(int i = 0; i < imgLength; i++) { 
    if(myBitArray[i] == 1) { 
     // ... do stuff ... 
    } 
} 

パフォーマンスが使用可能です、驚くべきことではない。私はgpr​​ofを通してプログラムを実行し、イテレータとbeginのようなstd::vectorメソッドへのかなりの時間と何百万もの呼び出しがあることを確認します。ここでは、トップ・サンプリング機能があります：

Flat profile: 

Each sample counts as 0.01 seconds. 
    % cumulative self    self  total   
time seconds seconds calls s/call s/call name  
37.91  0.80  0.80  2  0.40  1.01 findPattern(bit_array_c*, bool*, int, int, int) 
12.32  1.06  0.26 98375762  0.00  0.00 __gnu_cxx::__normal_iterator<unsigned char const*, std::vector<unsigned char, std::allocator<unsigned char> > >::__normal_iterator(unsigned char const* const&) 
11.85  1.31  0.25 48183659  0.00  0.00 __gnu_cxx::__normal_iterator<unsigned char const*, std::vector<unsigned char, std::allocator<unsigned char> > >::operator+(int const&) const 
11.37  1.55  0.24 49187881  0.00  0.00 std::vector<unsigned char, std::allocator<unsigned char> >::begin() const 
    9.24  1.75  0.20 48183659  0.00  0.00 bit_array_c::operator[](unsigned int) const 
    8.06  1.92  0.17 48183659  0.00  0.00 std::vector<unsigned char, std::allocator<unsigned char> >::operator[](unsigned int) const 
    5.21  2.02  0.11 48183659  0.00  0.00 __gnu_cxx::__normal_iterator<unsigned char const*, std::vector<unsigned char, std::allocator<unsigned char> > >::operator*() const 
    0.95  2.04  0.02        bit_array_c::operator()(unsigned int) 
    0.47  2.06  0.01 6025316  0.00  0.00 __gnu_cxx::__normal_iterator<unsigned char*, std::vector<unsigned char, std::allocator<unsigned char> > >::__normal_iterator(unsigned char* const&) 
    0.47  2.06  0.01 3012657  0.00  0.00 __gnu_cxx::__normal_iterator<unsigned char*, std::vector<unsigned char, std::allocator<unsigned char> > >::operator*() const 
    0.47  2.08  0.01 1004222  0.00  0.00 std::vector<unsigned char, std::allocator<unsigned char> >::end() const 
... remainder omitted ... 

私はC++のSTLと本当に慣れていないんだけど、誰もが、なぜ、例えば、STDに光を当てることができます::ベクトル::（）を開始し、数万人と呼ばれています時間？そして、もちろん、私がそれをスピードアップするために何かできるかどうか？

編集：私はちょうどあきらめて、検索機能（ループ）を最適化しました。

Answer 1

なりますbitarray.cppためのコードへの迅速なピークを示すことから最適化されていないコードをプロファイリング

は、まれに価値がありますm_Arrayはstd :: vector型です

STLベクトルの[]演算子は複雑ではありますが、vector :: beginの呼び出しで実装されている可能性があります。次に、オフセットtを計算しますoあなたが望む価値に到達する。 bitarray.cppはすべてのビットアクセスで[]演算子を呼び出しているので、たくさんの呼び出しがあります。あなたのユースケース与え

私はそれはあなたのシーケンシャル、少しずつ、アクセスパターンのためのカスタムbitarray.cppに含まれる機能の実装や曲を作成します。

• unsigned charを使用しないでください。32または64ビットの値を使用して、必要なメモリアクセス数を減らしてください。
• 私は正常な配列を使用して、見越しオーバーヘッドを避けるためのベクトルではない
• すべてのルックアップを実行しない順次アクセス関数nextbit（）を作成します。現在の "値"へのポインタを32/64ビット境界上でインクリメントするために必要なすべてのものを格納します。境界間のすべてのアクセスは単純なマスク/シフト操作であり、非常に高速でなければなりません。あなたはそれの一部を掲載場合

Answer 2

あなたのコードを見ることなく、あなたがしていることをスピードアップする方法について具体的なコメントをするのは難しいです。しかし、vector::begin()は、イテレータをベクトルの最初の要素に戻すために使用されます。これは、ベクトルを反復処理する際の標準ルーチンです。

OProfileのようなより現代的なプロファイラを使用することをお勧めします。実際のC++ラインや個々のasm命令までの時間をプログラムが費やしている場所について細かい情報を提供します。あなたはそれをどのように実行するかによって異なります。

なぜ、bitarray.cppの代わりにバニラstd::vector<bool>を使用しましたか？私はそれを自分で使ったことはありませんが、上記のリンクを素早くスキャンするとbitarray.cppがstd::vector<bool>以上の追加機能をサポートしていることを示しています。これはSTLベクタークラスと比較してオーバーヘッドを追加する可能性があります...

Answer 3

あなたはこのように、（私は正確にbitarray.cppがあなたのために何をするかわからない）ポインタ/イテレータを使用してパフォーマンスを向上させることができます：私はもしわからないので

for (bool *ptr = myBitArray, int i = 0; i != imgLength; ++i, ++ptr) 
{ 
    if (*myBitArray == 1) 
    { 
     //handle 
    } 
} 

私はここで私をint使用あなたのビット配列はnullで終了します。この場合、あなたの状態は単純に

*myBitArray != '\0'; 

また、より良い終了条件をハックすることもできます。 std :: iteratorを使うのが一番良いかもしれませんが、あなたのビット配列がそれをサポートしているかどうかは疑問です。

編集：

通常、これは、マイクロ最適化になるが、十分なものの上に、あなたループならば、それはおそらく、少しパフォーマンスが向上します。

Answer 4

個々のビットにアクセスするのに十分なパフォーマンスが重要な場合は、おそらくコードを並列化する必要があります。これを画像処理と記述しているので、ビットiの状態がビットi + 1からi + 6をどのように扱うかに影響しないので、一度にバイトとワードで動作するようにコードを書き直すことができます。カウンターを8〜64倍少なくするだけで、パフォーマンスが大幅に向上し、コンパイラーがコードを最適化しやすくなります。

Answer 5

あなたのプロファイル出力にインライン関数の多くを見ているという事実は、彼らがインライン化されていないことを意味 - つまり、あなたがオンに最適化してコンパイルされていません。したがって、コードを最適化するためにできる最も簡単なことは、-O2または-O3を使用することです。

bool bit_array_c::operator[](const unsigned int bit) const 
{ 
    return((m_Array[BIT_CHAR(bit)] & BIT_IN_CHAR(bit)) != 0); 
} 

：最適化され、最適化されていないコードの実行プロファイルは、おそらく完全にdifferent.33