2

gprof を使用してコードをプロファイリングし、レポートから、トップ 20 程度のすべてではないにしても、ほとんどがベクトルに関するものでした

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ms/call  ms/call  name    
 14.71      0.05     0.05  3870399     0.00     0.00  std::vector<bool, std::allocator<bool> >::size() const
 11.76      0.09     0.04 10552897     0.00     0.00  std::_Bit_reference::_Bit_reference(unsigned long*, unsigned long)
 11.76      0.13     0.04  7890323     0.00     0.00  std::_Bit_const_iterator::_Bit_const_iterator(std::_Bit_iterator const&)
  5.88      0.15     0.02 10089215     0.00     0.00  std::_Bit_iterator::operator*() const
  5.88      0.17     0.02  6083600     0.00     0.00  std::vector<bool, std::allocator<bool> >::operator[](unsigned int)
  5.88      0.19     0.02  3912611     0.00     0.00  std::vector<bool, std::allocator<bool> >::end() const
  5.88      0.21     0.02                             std::istreambuf_iterator<char, std::char_traits<char> > std::num_get<char, std::istreambuf_iterator<char, std::char_traits<char> > >::_M_extract_int<unsigned long long>(std::istreambuf_iterator<char, std::char_traits<char> >, std::istreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, std::_Ios_Iostate&, unsigned long long&) const
  2.94      0.22     0.01  6523499     0.00     0.00  std::_Bit_reference::operator bool() const
  2.94      0.23     0.01  3940406     0.00     0.00  std::vector<bool, std::allocator<bool> >::begin() const
  2.94      0.24     0.01  2807828     0.00     0.00  std::_Bit_iterator::operator++()
  2.94      0.25     0.01   146917     0.00     0.00  std::_Bit_iterator_base::_M_incr(int)
  2.94      0.26     0.01   121706     0.00     0.00  std::__miter_base<unsigned long*, false>::__b(unsigned long*)
  2.94      0.27     0.01    46008     0.00     0.00  std::_Bvector_base<std::allocator<bool> >::~_Bvector_base()
  2.94      0.28     0.01    22596     0.00     0.00  std::_Bit_iterator std::__copy_move<false, false, std::random_access_iterator_tag>::__copy_m<std::_Bit_iterator, std::_Bit_iterator>(std::_Bit_iterator, std::_Bit_iterator, std::_Bit_iterator)
  2.94      0.29     0.01     4525     0.00     0.05  integer::operator+(integer)
  2.94      0.30     0.01     1382     0.01     0.01  void std::_Destroy<unsigned int*, unsigned int>(unsigned int*, unsigned int*, std::allocator<unsigned int>&)
  2.94      0.31     0.01                             std::string::size() const
  2.94      0.32     0.01                             std::basic_string<char, std::char_traits<char>, std::allocator<char> >::~basic_string()
  2.94      0.33     0.01                             std::locale::locale()
  2.94      0.34     0.01                             __dynamic_cast

私の関数の残りの部分がかなり効率的であること、または vector< bool > からの値へのアクセスが本当に遅いことを意味するので、それは良い兆候ですか?

gcc -std=c++0x でコンパイルしています

4

5 に答える 5

8

vector<bool>sを格納しませんbool。基本的にはビットフィールドです。単一の値を変更するのに必要な少しの手間がかかります。

実行時のパフォーマンスが問題になる場合は、代わりにvector<char>orを検討してください。deque<bool>

于 2011-06-23T22:47:08.063 に答える
2

それは私の関数の残りの部分がかなり効率的であること、またはベクトルからの値へのアクセスが本当に遅いことを意味するからですか?

「遅い」と「効率的」は相対的な値であるため、これは本質的に無意味な区別です。レポートを解釈する最も客観的な方法は次のとおりです。

std::vector の操作は最も多くの時間を消費するため、コードをさらに高速化するには、ここから開始する必要があります。

は、実際の s ではなくビットマスクのセットを格納std::vector<bool>するため、一般に a よりも少し遅いことに注意してください(つまり、理想的には、エントリごとに 1 ビットしか必要としません)。これはスペースを節約しますが、遅くなります。より高速にする必要がある場合は、代わりに(または、必要に応じて ..) を使用してみてください。std::vector<int>boolstd::vector<int>char

デバッグ ビルドの影響が大きいと思われるstd::vector<bool>ので、最適化フラグをまだ行っていない場合は試してみてください (常にプロファイリングを行う必要があります)。

于 2011-06-23T22:47:35.393 に答える
1

それはあなたのプログラムについて多くを語っていますか? ビジネス以外は、vector<bool>基本的に何も伝えていません。

gprofの問題を直接見ています。

一部の関数の「セルフ タイム」が高いことがわかっているとします。これは、プログラム カウンターが十分な回数サンプリングされたことを意味しますが、それは作成した関数でも変更できる関数でもありません。

それについてできる唯一のことは、呼び出しを減らすか、それを呼び出すルーチンの呼び出しを減らすか、そのルーチンの呼び出しを減らすことです。

gprofは、ルーチンの包括時間、呼び出された回数、およびコール グラフも推測することで、ユーザーを支援しようとします。再帰がなく、10 個ほどの関数しかなく、I/O をまったく行っていない場合、これは役立つ可能性があります。

Zoomのようなプロファイラーで具現化された、少し異なるアプローチがあります。プログラム カウンターだけをサンプリングする代わりに、コール スタック全体をサンプリングします。なんで？費やされた時間の原因となるコード行は、その間スタック上にあるため、注目されるように求めているだけです。

ウォール クロック タイムにコール スタックをサンプリングし、どのコード行がほとんどの時間スタックで見つかったかを示すプロファイラーが最も効果的です。さらに効果的なのは、スタックの個々のサンプルを調べることができる場合です。これにより、それらの行が呼び出されている量だけでなく、なぜ呼び出されているかもわかるため、本当に必要でないかどうかを簡単に判断できます。

于 2011-06-24T02:25:38.163 に答える
1

vector<bool>実際には、各bool値が単一のビットとして格納されるテンプレートの特殊化です。intただし、 "normal" を使用した場合と同じように個々のビットを直接操作することはできませんbool。したがって、 で使用されるアルゴリズムvector<bool>は「通常の」 とは大きく異なります。インターフェイスを可能な限りvector<>維持するために、 のような関数を呼び出したときにビットを操作するプロキシ オブジェクトを返す場合があります。コンパイラの構成方法と問題のコードによっては、gprof レポートの結果に貢献する場合があります。vectoroperator[]

于 2011-06-23T22:46:26.773 に答える
1

あなたの時間の 14.71% がvector<bool>::size()!?!に費やされているからです。サイズはおそらく指定されています。

size() の呼び出し回数を減らすか、事前にサイズがわかっている場合は固定サイズのベクトルを使用してください。bitset

質問の更新を読んだ後に編集します。

必須の変更: g++ --std=c++0x -g -O3(これは2 つのタイプミスと最適化フラグ、再プロファイルです!); テンプレート クラスはインライン化を頻繁に使用し、これにより、無数の他の最適化が可能になります。高速化の順序は簡単に 10 倍です

于 2011-06-23T22:49:46.300 に答える