Ответ 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();
}
Выходы -ftime-report для разных N (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
Итак, есть дополнительная работа для огромного N в фазе expand vars. Эта фаза находится именно в этой строке: cfgexpand.c: 4463 (между макросом TV_VAR_EXPAND).
Интересный факт: у меня очень короткое время компиляции с моим настраиваемым 32-разрядным g++ 4.6.2 (~ 20 секунд для N = 100000).
В чем разница между моим g++ и ubuntu g++? Один включил по умолчанию защиту Gcc Stack Protection (-fstack-protect) в Ubuntu. И эта защита добавляется только для фазы "expand vars" (найдена в источниках 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.
UPDATE:
После запуска gcc внутри callgrind (инструмент профилирования вызовов-графов от Valgrind) могу сказать, что существует N стековых переменных. Если включен защитник стека, они обрабатываются фазой "expand vars" с тремя алгоритмами O (N ^ 2). На самом деле есть N ^ 2 успешных обнаружения конфликтов и 1,5 * N ^ 2-битных манипуляций, сделанных плюс некоторые логики вложенных циклов.
Почему число переменных стека настолько велико? Потому что каждая двойная константа в вашем коде сохраняется в другом слоте в стеке. Затем он загружается из своего слота и передается, как говорится в соглашении о вызовах (через вершину стека в x86, через регистры в x86_64). Смешной факт: весь код с push_back, скомпилированный с помощью -fstack-protector или с -fno-stack-protector, тот же; так же, как и для компоновки стека. Возникают только некоторые смещения компоновки стека кода non-push_back (проверено два прогона с -S и diff -u). Никакой дополнительный код не был создан с помощью защитника стека.
Включение защитника стека фатально меняет поведение внутри компилятора. Не могу сказать, где именно (примечание: этот поворотный пункт можно найти с сравнением трассировок стека с 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
Существует вторая прогулка N ^ 2 в add_alias_set_conflicts. Он выполняет проверку типов для каждой пары с помощью objects_must_conflict_p. Он проверяет, являются ли две переменные одного и того же типа (большинство пар - это анализ псевдонимов на основе типа, TBAA). Если нет, то add_stack_var_conflict вызывается; существует только N таких вызовов из этого N ^ 2 петлевого гнезда.
Последняя огромная прогулка находится в partition_stack_vars() функции с qsort ing стеков стека (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 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 }
(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, который добавил эту логику.