有的是-ftime-report
gcc 中的选项打印每个编译器阶段浪费的时间的详细报告。
我使用 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 (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 http://code.metager.de/source/xref/DragonFly-BSD/contrib/gcc-4.7/gcc/cfgexpand.c#4463(TV_VAR_EXPAND 宏之间)。
有趣的事实:我使用自定义编译的 32 位 g++ 4.6.2 的编译时间非常短(N = 100000 时约为 20 秒)。
我的 g++ 和 ubuntu g++ 有什么区别?其一是默认开启 https://wiki.ubuntu.com/ToolChain/CompilerFlagsGcc 堆栈保护 (-fstack-protect
选项)在 Ubuntu 中。这种保护只是添加到“扩展变量”阶段(在源代码中找到)cfgexpand.c:1644,expand_used_vars() http://code.metager.de/source/xref/DragonFly-BSD/contrib/gcc-4.7/gcc/cfgexpand.c#1644;提及here http://en.wikibooks.org/wiki/GNU_C_Compiler_Internals/Stackguard_4_1):
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
运行时间从 800 秒缩短为 24 秒。
UPDATE:
里面启动gcc之后callgrind
(来自 Valgrind 的调用图分析工具),我可以说有 N 个堆栈变量。如果启用了堆栈保护器,它们将在“扩展变量”阶段使用三个 O(N^2) 算法进行处理。实际上有 N^2 成功的冲突检测和 1,5 * N^2 位操作完成加上一些嵌套循环逻辑。
为什么堆栈变量的数量如此之多?因为代码中的每个双常量都保存到堆栈中的不同槽中。然后它从其槽中加载并按照调用约定进行传递(通过 x86 中的堆栈顶部;通过 x86_64 中的寄存器)。有趣的事实:所有代码都带有push_back
编译为-fstack-protector
或与-fno-stack-protector
是一样的;常量的堆栈布局也相同。只有非push_back代码的一些堆栈布局偏移量受到影响(检查了两次运行-S
and diff -u
)。启用的堆栈保护器没有创建任何额外的代码。
启用堆栈保护器会致命地改变编译器内部的某些行为。不能确切地说在哪里(注意:通过比较堆栈跟踪可以找到这个转折点调用图.tar.gz https://stackoverflow.com/a/1980770/196561作者:胡安·M·贝洛·里瓦斯)。
第一个大 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);
}
}
The add_stack_var_conflict(i,j)
转向
- 分配(每个变量一次)大小为...哦,动态大小将增长到 N 位的位图
- 在第 i 个变量的位掩码中设置一个位以防止与 j 冲突
- 在第 j 个变量的位掩码中设置一个位以防止与 i 冲突
有第二个 N^2 走进add_alias_set_conflicts
。它对每一对进行类型检查objects_must_conflict_p
。它检查两个变量是否属于同一类型(大多数对都是;这是基于类型的别名分析,TBAA http://en.wikipedia.org/wiki/Alias_analysis#Type-based_alias_analysis)。如果不,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
.
UPDATE2:
看来,转折点是expand_one_var
,在检查堆栈上变量的立即分配或延迟分配时:
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 http://gcc.gnu.org/ml/gcc-patches/2005-05/txt00029.txt添加了这个逻辑。