c++ - 为什么编译超过100,000行的std::vector::push_back需要很长时间？

Question

我正在编译一个C++库，该库定义了一个从一组数据点中随机采样的函数。数据点存储在std::vector中。有126,272个std::vector push_back语句，其中所涉及的 vector 的类型为double。编译需要很长时间。

为什么要花这么长时间？ (除了std::vector push_back语句外，所有其他代码的编译时间都将少于1秒，因为其他代码很少。)

Answer 1

gcc中有-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输出(由于PC上的背景负载， wall时间不准确，因此请查看 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++有什么区别？一个是 turning on by default Ubuntu中的Gcc堆栈保护( -fstack-protect选项)。并且此保护仅添加到“expand vars”阶段(在源 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秒降低到24秒。

更新:

在 callgrind(Valgrind的调用图分析工具)中启动gcc之后，我可以说有N个堆栈变量。如果启用了堆栈保护器，则会使用三种O(N ^ 2)算法在“扩展变量”阶段对其进行处理。实际上，已经完成了N ^ 2个成功的冲突检测，并且完成了1,5 * N ^ 2位操作以及一些嵌套循环逻辑。

为什么堆栈变量的数量如此之大？因为代码中的每个 double 常量都保存到堆栈中的其他插槽中。然后按照调用约定的说明(通过x86的堆栈顶部；通过x86_64的寄存器)将其从其插槽加载并传递。有趣的事实:所有使用 push_back或 -fstack-protector编译的 -fno-stack-protector的代码都是相同的；常量的堆栈布局也相同。仅会影响non-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位

在i'th var的位掩码中设置一些位以与j

冲突

设置第j个var的位掩码中的某个位以与i

冲突

在 add_alias_set_conflicts中还有第二个N ^ 2步。它使用 objects_must_conflict_p对每个对进行类型检查。它检查两个变量是否具有相同的类型(大多数对是；这是基于类型的别名分析 TBAA)。如果不是，则调用 add_stack_var_conflict；该N ^ 2循环嵌套中只有N个此类调用。

最后一个大步是在 partition_stack_vars()函数中，堆栈变量(O(NlogN))的 qsorting和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_var cfgexpand.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        }

(根据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添加了此逻辑。