我正在編譯一個C++庫，它定義了從一組數據點中隨機抽樣的單個函數。數據點存儲在std::vector中。有126,272 std::vector push_back語句，其中所討論的向量類型爲double。編譯需要很長時間。爲什麼編譯超過100,000行的std :: vector :: push_back需要很長時間？
這爲什麼會這麼長？ （所有比std::vector的push_back語句中使用的代碼將需要不到1秒的編譯，因爲有很少的其他代碼的。）
有一個在海灣合作委員會-ftime-report選項，打印的時間每個編譯階段浪費了詳細的報告。
我使用的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();
}
有用於各種N- -ftime-report輸出（wall時間是不準確的，因爲背景負荷的PC，所以看上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 = 100 000
$ 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
因此，存在鉅額ň一些額外的工作「擴大瓦爾」階段。這一階段正好在這一行：cfgexpand.c:4463（在TV_VAR_EXPAND宏之間）。有趣的事實：我用我自定義編譯的32位g ++ 4.6.2編譯時間非常短（對於N = 100000約20秒）。
my g ++和ubuntu g ++有什麼區別？其中一個是turning on by default Ubuntu中的Gcc Stack Protection（-fstack-protect選項）。而這種保護僅增加了「擴大瓦爾」階段（來源cfgexpand.c:1644,expand_used_vars()發現;提到here）：
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
UPDATE下來：
內callgrind開始後的gcc （來自Valgrind的調用圖分析工具），我可以說有N個堆棧變量。如果啓用了堆棧保護器，則會使用三個O（N^2）算法在「擴展變量」階段處理它們。實際上有N^2個成功的衝突檢測和1,5 * N^2位操作加上一些嵌套的循環邏輯。
爲什麼堆棧變量的數量如此之高？因爲代碼中的每個雙常數都保存在堆棧中的不同插槽中。然後它從插槽中加載並按照調用約定的規定傳遞（通過x86中的堆棧頂部;通過x86_64中的寄存器）。有趣的事實：與-fstack-protector或-fno-stack-protector編譯的所有代碼push_back是相同的;常量的堆棧佈局也是一樣的。只有一些非push_back代碼的堆棧佈局偏移會受到影響（使用-S和diff -u檢查兩次運行）。啓用的堆棧保護程序未創建其他代碼。
啓用堆棧保護器致命地改變了編譯器內部的一些行爲。不能確切地說（注意：可以通過比較堆棧軌跡與Juan M.Bello Rivas的callgraph.tar.gz找到這個轉折點）。
首先大N *（N + 1）/ 2 = O（N^2）步行處於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)變爲
有第二N^2走在add_alias_set_conflicts。它確實輸入了與objects_must_conflict_p的每一對的支票。它檢查，如果兩個變量是相同類型（大多數對是;這是基於類型的別名分析，TBAA）。如果不是，則調用add_stack_var_conflict;這個N^2循環嵌套只有N個這樣的調用。
最後一個巨大的步行是在partition_stack_vars()函數與qsort堆棧變量（O（NlogN））和N *（N-1）/ 2 = O（N^2）步行找到所有非衝突對。下面是從cfgexpand.c文件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觸發。
UPDATE2：
看來，轉折點是expand_one_varcfgexpand.c from 4.6，在檢查堆棧上的變量立即或延遲分配：
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裏面添加這個邏輯。
夢幻般的答案。可以說GCC的性能問題值得報告...... – Nemo
@Nemo：如果瘋狂的代碼需要大量的時間來編譯，我不會看到它是一個性能問題。如果合理的代碼需要不合理的時間，這是一個不同的故事，但是對push_back的10萬次調用真的值得緩慢。我寧願讓GCC開發人員專注於一些有用的東西，而不是將不合適的代碼編譯得更好。 – Damon
@Damon：首先，「格式不正確」是C++中的一個術語 - 由標準定義 - 並且您使用不正確。這個程序完美組織良好。其次，你不是什麼「瘋狂」的仲裁者;不是每個人的需求都與你的相同。如果簡單的線性代碼在編譯器中引起O（n^2）行爲，那麼我稱之爲編譯器中的性能錯誤。我非常懷疑我是孤獨的。 – Nemo
我相信很長一段時間涉及矢量是一個模板。編譯器需要用相應的函數重寫每個發生的push_back。這就像有許多重載函數，其中編譯需要進行名稱修改以解決正確的功能。與簡單地編譯非重載函數相比，這是一項額外的工作。
編譯器的哪個階段需要做很多工作來處理模板？ 「解析器」和「名稱查找」？但是在'-ftime-report'的結果中，兩個階段都花了不到2秒鐘的時間。 – osgx
這個問題完全由osgx的回答完全回答。
也許一個額外的方面：push_back() VS初始化列表
當100000個push_backs運行上面的測試中，我得到以下結果用GCC 4.4.6在Debian 6.0.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倍！
多久了？ –
大多數編譯器並不是針對100,000多行文件進行優化的。 –
我的四核機器需要幾分鐘的時間才能使用8 GB的內存。幸運的是，它最終成功編譯了。 – synaptik