我正在编译一个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