2

Dipperstein の bitarray.cpp クラスを使用して、画像データが 1 ピクセル 1 ビットとしてネイティブに保存される 2 値 (白黒) 画像を処理しています。

次のような for ループを使用して、画像ごとに 4 ～ 9 メガピクセルのオーダーで、数百の画像にわたって、すべてのビットを反復処理する必要があります。

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

パフォーマンスは使用可能ですが、驚くほどではありません。gprof を使用してプログラムを実行すると、かなりの時間と、std::vectoriterator や begin などのメソッドへの数百万回の呼び出しがあることがわかりました。トップサンプル関数は次のとおりです。

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::vector::begin() が数百万回呼び出されている理由を誰かが明らかにすることはできますか? そしてもちろん、それをスピードアップするために何かできることはありますか?

編集：代わりに検索機能（ループ）をあきらめて最適化しました。

4

5 に答える 5

6

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

最適化されたコードと最適化されていないコードの実行プロファイルは完全に異なる可能性が高いため、最適化されていないコードのプロファイルを作成する価値はほとんどありません.33

于 2009-08-09T03:47:36.917 に答える
2

bitarray.cpp のコードを簡単に説明すると、次のようになります。

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

m_Array は std::vector 型です

STL ベクトルの [] 演算子は一定の複雑さですが、 vector::begin への呼び出しとして実装されている可能性が高く、配列のベースアドレスを取得し、オフセットを計算して必要な値を取得します。bitarray.cpp は EVERY BIT ACCESS で [] 演算子を呼び出すため、多くの呼び出しが発生します。

あなたのユースケースを考えると、bitarray.cppに含まれる機能のカスタム実装を作成し、順次、ビットごとのアクセスパターンに合わせて調整します。

  • unsigned char を使用しないでください。32 ビットまたは 64 ビットの値を使用して、必要なメモリ アクセスの数を減らしてください。
  • ルックアップのオーバーヘッドを避けるために、ベクトルではなく通常の配列を使用します
  • すべての検索を行わない順次アクセス関数 nextbit() を作成します。現在の「値」へのポインターを格納するだけで、32/64 ビット境界でインクリメントする必要があります。境界間のすべてのアクセスは単純なマスク/シフト操作であり、非常に高速です。
于 2009-08-09T05:49:30.480 に答える
1

コードを見なければ、実行中の処理を高速化する方法について具体的なコメントをすることは困難です。ただし、vector::begin()ベクトルの最初の要素に反復子を返すために使用されます。これは、ベクトルを反復処理するときの標準ルーチンです。

実際には、 OProfileなどのより最新のプロファイラーを使用することをお勧めします。これにより、プログラムが時間を費やしている場所に関する詳細な情報が得られます-実際の C++ 行、または方法に応じて個々の asm 命令までそれを実行します。

余談ですが、なぜバニラの代わりにbitarray.cppstd::vector<bool>を使用することにしたのですか? 私はそれを自分で使用したことはありませんが、上記のリンクを簡単にスキャンすると、 が をbitarray.cpp超える追加機能をサポートしていることが示唆されstd::vector<bool>ます。これを使用しない場合、STL ベクトル クラスと比較してオーバーヘッドが追加される可能性があります...

于 2009-08-09T00:31:45.677 に答える
0

次のように、ポインタ/イテレータ（bitarray.cppが正確に何をするのかわかりません）を使用することで、パフォーマンスを向上させることができます。

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

ここではintiのみを使用します。これは、ビット配列がnullで終了するかどうかわからないためです。この場合、条件は単純に次のようになります。

*myBitArray != '\0';

または、より良い終了条件をハックアウトすることもできます。std :: iteratorを使用するのが最善ですが、ビット配列がそれをサポートするとは思えません。

編集：

通常、これはマイクロ最適化ですが、十分な量をループすると、パフォーマンスがわずかに向上する可能性があります。

于 2009-08-09T02:52:27.810 に答える
0

パフォーマンスが十分に重要で、個々のビットへのアクセスについて心配する必要がある場合は、コードを並列化する必要があります。これを画像処理として説明しているので、ビットiの状態がビットi+1からi+6の処理方法に影響を与えない可能性があります。したがって、一度にバイトとワードを操作するようにコードを書き直すことができます。カウンターを8〜64倍少なくインクリメントできるだけで、測定可能なパフォーマンスの向上が得られ、コンパイラーがコードを最適化するのも簡単になります。

于 2009-08-09T03:00:54.910 に答える