データポイントのセットからランダムにサンプリングする単一の関数を定義するC++ライブラリをコンパイルしています。データポイントはに保存されますstd::vector。126,272個std::vectorのpush_backステートメントがあり、問題のベクトルはタイプdoubleです。コンパイルに時間がかかります。
なぜこれほど時間がかかるのでしょうか？（push_backステートメント以外のすべてのコードは、std::vector他のコードがほとんどないため、コンパイルに1秒もかかりません。）
-ftime-reportgcc には、各コンパイラ フェーズで浪費された時間の詳細なレポートを出力するオプションがあります。
私はubuntu 12.04 64ビットとgcc 4.6.3を使用しており、このコードを使用して状況を再現しています:
#include <vector>
using namespace std;
int main()
{
vector<double> d;
d.push_back(5.7862517058766);
/* ... N lines generated with
perl -e 'print(" d.push_back(",rand(10),");\n") for 1..100000'
*/
d.push_back(3.77195464257674);
return d.size();
}
-ftime-reportさまざまな N の出力があります ( PCwallのバックグラウンド負荷のために時間が不正確だったので、 を参照してくださいuser time) usr。
N=10000
$ g++ -ftime-report ./pb10k.cpp
Execution times (seconds)
...
expand vars : 1.48 (47%) usr 0.01 ( 7%) sys 1.49 (44%) wall 1542 kB ( 2%) ggc
expand : 0.11 ( 3%) usr 0.01 ( 7%) sys 0.10 ( 3%) wall 19187 kB (30%) ggc
...
TOTAL : 3.18 0.15 3.35 64458 kB
N=100000
$ g++ -ftime-report ./pb100k.cpp
Execution times (seconds)
....
preprocessing : 0.49 ( 0%) usr 0.28 ( 5%) sys 0.59 ( 0%) wall 6409 kB ( 1%) ggc
parser : 0.96 ( 0%) usr 0.39 ( 6%) sys 1.41 ( 0%) wall 108217 kB (18%) ggc
name lookup : 0.06 ( 0%) usr 0.07 ( 1%) sys 0.24 ( 0%) wall 1023 kB ( 0%) ggc
inline heuristics : 0.13 ( 0%) usr 0.00 ( 0%) sys 0.20 ( 0%) wall 0 kB ( 0%) ggc
integration : 0.03 ( 0%) usr 0.00 ( 0%) sys 0.04 ( 0%) wall 4095 kB ( 1%) ggc
tree gimplify : 0.22 ( 0%) usr 0.00 ( 0%) sys 0.23 ( 0%) wall 36068 kB ( 6%) ggc
tree eh : 0.06 ( 0%) usr 0.00 ( 0%) sys 0.14 ( 0%) wall 5678 kB ( 1%) ggc
tree CFG construction : 0.08 ( 0%) usr 0.01 ( 0%) sys 0.10 ( 0%) wall 38544 kB ( 7%) ggc
....
expand vars : 715.98 (97%) usr 1.62 (27%) sys 718.32 (83%) wall 18359 kB ( 3%) ggc
expand : 1.04 ( 0%) usr 0.09 ( 1%) sys 1.64 ( 0%) wall 190836 kB (33%) ggc
post expand cleanups : 0.09 ( 0%) usr 0.01 ( 0%) sys 0.15 ( 0%) wall 43 kB ( 0%) ggc
....
rest of compilation : 1.94 ( 0%) usr 2.56 (43%) sys 102.42 (12%) wall 63620 kB (11%) ggc
TOTAL : 739.68 6.01 866.46 586293 kB
そのため、" expand vars " フェーズで巨大な N に対して追加の作業が行われます。このフェーズは、まさにこの行にあります: cfgexpand.c:4463 (TV_VAR_EXPAND マクロの間)。
興味深い事実: カスタム コンパイルされた 32 ビット g++ 4.6.2 (N = 100000 で約 20 秒) のコンパイル時間は非常に短いです。
g++ と ubuntu g++ の違いは何ですか? 1つは、デフォルトでUbuntuのGccスタック保護（オプション）をオンにしています。-fstack-protectそして、この保護は "expand vars" フェーズにのみ追加されます (ソースcfgexpand.c:1644,expand_used_vars() にあります。ここで言及されています):
N=100000、オプションでスタック プロテクターを無効にします-fno-stack-protector(コードに使用します):
$ g++ -ftime-report -fno-stack-protector pb100k.cpp 2>&1 |egrep 'TOTAL|expand vars'
expand vars : 0.08 ( 0%) usr 0.01 ( 1%) sys 0.09 ( 0%) wall 18359 kB ( 3%) ggc
TOTAL : 23.05 1.48 24.60 586293 kB
実行時間は 24 秒で、800 秒から短縮されています。
アップデート：
内部で gcc を起動した後callgrind(Valgrind のコールグラフ プロファイリング ツール)、N 個のスタック変数があると言えます。スタック プロテクターが有効になっている場合、それらは 3 つの O(N^2) アルゴリズムを使用して「expand vars」フェーズで処理されます。実際には、N^2 の競合検出が成功し、1.5 * N^2 ビットの操作が行われ、ネストされたループ ロジックがいくつかあります。
スタック変数の数が非常に多いのはなぜですか? コード内のすべての double 定数がスタック内の異なるスロットに保存されるためです。次に、そのスロットからロードされ、呼び出し規則が示すように渡されます (x86 ではスタックのトップを介して、x86_64 ではレジスタを介して)。おもしろい事実: でコンパイルされた s を含むコードはすべて同じpush_backです。定数のスタック レイアウトも同じです。push_back 以外のコードの一部のスタック レイアウト オフセットのみが影響を受けます ( と で 2 つの実行を確認) 。有効なスタック プロテクターによって追加のコードは作成されませんでした。-fstack-protector-fno-stack-protector-Sdiff -u
スタック プロテクターを有効にすると、コンパイラ内の一部の動作が致命的に変更されます。正確な場所はわかりません (注: Juan M. Bello Rivas によるスタック トレースとcallgraph.tar.gzを比較すると、このターニング ポイントを見つけることができます)。
最初の大きな N*(N+1)/2 = O(N^2) walk は、expand_used_vars_for_block (tree block, level)スタック変数のペア間の競合に関する情報を設定する関数です。
/* Since we do not track exact variable lifetimes (which is not even
possible for variables whose address escapes), we mirror the block
tree in the interference graph. Here we cause all variables at this
level, and all sublevels, to conflict. */
if (old_sv_num < this_sv_num)
{
new_sv_num = stack_vars_num;
for (i = old_sv_num; i < new_sv_num; ++i)
for (j = i < this_sv_num ? i : this_sv_num; j-- > old_sv_num ;)
add_stack_var_conflict (i, j);
}
}
へのadd_stack_var_conflict(i,j)ターン
2 番目の N^2 walk in がありadd_alias_set_conflictsます。とのすべてのペアの型チェックを行いobjects_must_conflict_pます。2 つの変数が同じ型であるかどうかをチェックします (ほとんどのペアは同じです。これは型ベースのエイリアス分析、TBAA です)。そうでない場合add_stack_var_conflictは呼び出されます。この N^2 ループ ネストからのそのような呼び出しは N 個だけです。
最後の巨大なウォークは、スタック変数 ( O(NlogN) ) および N*(N-1)/2 = O(N^2) ウォークを使用して機能し、競合しないすべてのペアを見つけますpartition_stack_vars()。cfgexpand.c ファイルからqsortの疑似コードを次に示します。partition_stack_vars
Sort the objects by size.
For each object A {
S = size(A)
O = 0
loop {
Look for the largest non-conflicting object B with size <= S.
/* There is a call to stack_var_conflict_p to check for
* conflict between 2 vars */
UNION (A, B)
offset(B) = O
O += size(B)
S -= size(B)
}
}
関数stack_var_conflict_pは、いくつかの i 番目の変数に競合ビットマスクがあるかどうか、および j 番目のビットが j 番目の変数との競合フラグとして設定されているかどうかを確認します ( への呼び出しを使用bitmap_bit_p(i->conflict_mask,j))。ここでの本当に悪いニュースは、callgrind がすべての競合チェックが成功したことを示しており、UNION ロジックがすべてのペアでスキップされていることです。
そのため、O(N^2) ビット セットと O(N^2/2) ビット チェックで多くの時間が浪費されます。このすべての作業は、最適化には何の役にも立ちません。はい、これはすべて の一部で-O0あり、 によってトリガーされ -fstack-protectorます。
更新 2:
どうやら、ターニングポイントはexpand_one_var 4.6 からの cfgexpand.cで、スタック上の変数の即時割り当てまたは遅延割り当てのチェックにおいて次のようになります。
1110 else if (defer_stack_allocation (var, toplevel))
1111 add_stack_var (origvar);
1112 else
1113 {
1114 if (really_expand)
1115 expand_one_stack_var (origvar);
1116 return tree_low_cst (DECL_SIZE_UNIT (var), 1);
1117 }
(expand_one_stack_var は、callgrind によると、ここでは高速バリアントでのみ呼び出されました)
が有効な場合、遅延割り当てが強制され-fstack-protectます (すべてのスタック変数の並べ替えが必要になる場合があります)。いくつかの「二次問題」についてのコメントもありますが、これは今ではあまりにもよく知られているように見えます。
969 /* A subroutine of expand_one_var. VAR is a variable that will be
970 allocated to the local stack frame. Return true if we wish to
971 add VAR to STACK_VARS so that it will be coalesced with other
972 variables. Return false to allocate VAR immediately.
973
974 This function is used to reduce the number of variables considered
975 for coalescing, which reduces the size of the quadratic problem. */
976
977 static bool
978 defer_stack_allocation (tree var, bool toplevel)
979 {
980 /* If stack protection is enabled, *all* stack variables must be deferred,
981 so that we can re-order the strings to the top of the frame. */
982 if (flag_stack_protect)
983 return true;
(スタック割り当てはあまりにも延期され-O2ています)
これはコミットです: http://gcc.gnu.org/ml/gcc-patches/2005-05/txt00029.txtこのロジックを追加しました。
この質問は、osgx からの素晴らしい回答によって完全に回答されました。
おそらく1つの追加の側面：push_back()vs初期化リスト
100000 push_backs で上記のテストを実行すると、Debian 6.0.6 システムで gcc 4.4.6 を使用して次の結果が得られます。
$ time g++ -std=c++0x -ftime-report ./pb100k.cc
Execution times (seconds)
garbage collection : 0.55 ( 1%) usr 0.00 ( 0%) sys 0.55 ( 1%) wall 0 kB ( 0%) ggc
...
reload : 33.95 (58%) usr 0.13 ( 6%) sys 34.14 (56%) wall 65723 kB ( 9%) ggc
thread pro- & epilogue: 0.66 ( 1%) usr 0.00 ( 0%) sys 0.66 ( 1%) wall 84 kB ( 0%) ggc
final : 1.82 ( 3%) usr 0.01 ( 0%) sys 1.81 ( 3%) wall 21 kB ( 0%) ggc
TOTAL : 58.65 2.13 60.92 737584 kB
real 1m2.804s
user 1m0.348s
sys 0m2.328s
初期化リストを使用すると、はるかに高速になります。
$ cat pbi100k.cc
#include <vector>
using namespace std;
int main()
{
vector<double> d {
0.190987822870774,
/* 100000 lines with doubles generated with:
perl -e 'print(rand(10),",\n") for 1..100000'
*/
7.45608614801021};
return d.size();
}
$ time g++ -std=c++0x -ftime-report ./pbi100k.cc
Execution times (seconds)
callgraph construction: 0.02 ( 2%) usr 0.00 ( 0%) sys 0.02 ( 1%) wall 25 kB ( 0%) ggc
preprocessing : 0.72 (59%) usr 0.06 (25%) sys 0.80 (54%) wall 8004 kB (12%) ggc
parser : 0.24 (20%) usr 0.12 (50%) sys 0.36 (24%) wall 43185 kB (65%) ggc
name lookup : 0.01 ( 1%) usr 0.05 (21%) sys 0.03 ( 2%) wall 1447 kB ( 2%) ggc
tree gimplify : 0.01 ( 1%) usr 0.00 ( 0%) sys 0.02 ( 1%) wall 277 kB ( 0%) ggc
tree find ref. vars : 0.01 ( 1%) usr 0.00 ( 0%) sys 0.01 ( 1%) wall 15 kB ( 0%) ggc
varconst : 0.19 (15%) usr 0.01 ( 4%) sys 0.20 (14%) wall 11288 kB (17%) ggc
integrated RA : 0.02 ( 2%) usr 0.00 ( 0%) sys 0.02 ( 1%) wall 74 kB ( 0%) ggc
reload : 0.01 ( 1%) usr 0.00 ( 0%) sys 0.01 ( 1%) wall 61 kB ( 0%) ggc
TOTAL : 1.23 0.24 1.48 66378 kB
real 0m1.701s
user 0m1.416s
sys 0m0.276s
これは約 30 倍以上高速です。
長い時間は、ベクトルがテンプレートであることに関連していると思います。push_backコンパイラは、対応する関数ですべての出現を書き直す必要があります。これは、オーバーロードされた関数が多数あるようなもので、正しい関数をアドレス指定するためにコンパイルで名前マングリングを実行する必要があります。これは、オーバーロードされていない関数を単純にコンパイルするのに比べて余分な作業です。