我正在编译一个 C++ 库，它定义了一个从一组数据点中随机采样的函数。数据点存储在std::vector. 有 126,272 个std::vectorpush_back 语句，其中所讨论的向量的类型为double. 编译需要很长时间。
为什么这需要这么长时间？（除了 push_back 语句之外的所有代码std::vector都需要不到 1 秒的时间来编译，因为几乎没有其他代码。）
问问题
2437 次
3 回答
45
gcc 中有一个-ftime-report选项可以打印每个编译器阶段浪费的时间的详细报告。
我使用 ubuntu 12.04 64-bit 和 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 的输出（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=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
因此，在“扩展变量”阶段对于巨大的 N 有一些额外的工作。这个阶段正好在这一行：cfgexpand.c:4463（在 TV_VAR_EXPAND 宏之间）。
有趣的事实：我的自定义编译 32 位 g++ 4.6.2 的编译时间非常短（对于 N = 100000，大约 20 秒）。
我的 g++ 和 ubuntu g++ 有什么区别？一个是默认打开Ubuntu 中的 Gcc 堆栈保护（-fstack-protect选项）。并且此保护仅添加到“扩展变量”阶段（在源代码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 个堆栈变量。如果启用了堆栈保护器，它们将在“扩展变量”阶段使用三个 O(N^2) 算法进行处理。实际上有 N^2 成功的冲突检测和 1,5 * N^2 位操作以及一些嵌套循环逻辑。
为什么堆栈变量的数量如此之多？因为代码中的每个双精度常量都保存到堆栈中的不同位置。然后它从它的插槽加载并按照调用约定传递（通过 x86 中的堆栈顶部；通过 x86_64 中的寄存器）。有趣的事实：所有带有 s 的代码都是用s或 withpush_back编译的；常量的堆栈布局也是一样的。只有非 push_back 代码的一些堆栈布局偏移受到影响（使用和检查两次运行）。启用的堆栈保护器没有创建其他代码。-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)转向_
- 分配（每个变量一次）大小为...的位图哦，动态大小将增长到 N 位
- 在第 i 个 var 的位掩码中设置一个位以与 j 发生冲突
- 在第 j 个 var 的位掩码中设置一个位以与 i 发生冲突
有第二个 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) 步行一起寻找所有不冲突的对。这是partition_stack_vars来自 cfgexpand.c 文件的伪代码：
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 cfgexpand.c 来自 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 }
（根据 callgrind，expand_one_stack_var 仅在快速变体中被调用）
启用延迟分配时会强制执行-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添加了这个逻辑。
于 2012-12-25T22:19:53.120 回答
5
osgx 的出色回答完全回答了这个问题。
也许还有一个方面：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 倍以上！
于 2012-12-26T00:17:43.477 回答
0
我相信很长一段时间都与向量作为模板有关。push_back编译器需要用相应的函数重写每一次出现。这就像有许多重载的函数，编译需要进行名称修改来处理正确的函数。与简单地编译非重载函数相比，这是一项额外的工作。
于 2012-12-25T22:41:30.430 回答