Dlaczego kompilowanie ponad 100 000 linii std:: vector:: push back zajmuje dużo czasu?

Istnieje opcja -ftime-report w gcc, która wypisuje szczegółowy raport czasu zmarnowanego przez każdą fazę kompilatora.

Używam ubuntu 12.04 64-bit z gcc 4.6.3 i tym kodem, aby odtworzyć twoją sytuację:

#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();
}

Istnieją -ftime-report wyjścia dla różnych N (wall Czas był niedokładny z powodu obciążenia tła na komputerze, więc spójrz na 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

Więc jest jakaś dodatkowa praca dla ogromnego N w "rozwiń vars" phase. Ta faza jest dokładnie w tej linii: cfgexpand.c: 4463 (pomiędzy makrem TV_VAR_EXPAND).

Ciekawostka: mam bardzo krótkie czasy kompilacji z moim niestandardowym skompilowanym 32-bitowym g++ 4.6.2 (~20 SEK dla N = 100000).

Jaka jest różnica między moim g++ A ubuntu g++? Jedną z nich jest włączenie domyślnie opcji Gcc Stack Protection (-fstack-protect) W Ubuntu. I ta ochrona jest dodawana tylko do fazy "expand vars" (znajdujÄ ... cej siÄ ™ w ĹşrĂłdeĹ' cfgexpand.c: 1644, expand_used_vars () ; wspomniany tutaj):

N=100000, ochraniacz stosu wyłączony z opcją -fno-stack-protector (użyj go do swojego kodu):

$ 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

Czas trwania to 24 sekundy, mniej niż 800.

Aktualizacja:

Po uruchomieniu gcc wewnątrz callgrind (narzędzie do profilowania Wykresów wywołania z Valgrind), mogę powiedzieć, że jest N zmiennych stosu. Jeśli stack protector jest włączony, są one obsługiwane w fazie "expand vars" z trzema O (N^2) algorytmy. W rzeczywistości są N^2 udane wykrywanie konfliktów i 1,5 * N^2 bitowe manipulacje wykonane plus trochę zagnieżdżonej logiki pętli.

Dlaczego liczba zmiennych stosu jest tak wysoka? Ponieważ każda Podwójna stała w Twoim kodzie jest zapisywana w innym miejscu w stosie. Następnie jest on ładowany ze swojego gniazda i przekazywany zgodnie z konwencją wywołującą (przez górną część stosu w x86; przez rejestry w x86_64). Ciekawostka: cały kod z push_backs skompilowany z -fstack-protector lub z -fno-stack-protector jest taki sam; układ stosu stałe też są takie same. Dotyczy to tylko niektórych przesunięć układu stosu kodu nie-push_back (zaznaczone dwa biegi z -S i diff -u). Żaden dodatkowy kod nie został utworzony przez enabled stack protector.

Włączenie stack protector fatalnie zmienia pewne zachowanie wewnątrz kompilatora. Nie można powiedzieć, gdzie dokładnie (Uwaga: można znaleźć ten punkt zwrotny, porównując ślady stosu z callgraph.smoła.GZ by Juan M. Bello Rivas).

Pierwszy duży N*(N+1)/2 = O(N^2) Spacer jest w funkcji expand_used_vars_for_block (tree block, level) do ustawiania informacji o konfliktach między parami zmiennych stosu:

  /* 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) zamienia się w

• przydzielanie (raz na zmienną) bitmapy o rozmiarze ... o, z dynamicznym rozmiarem, który będzie rosnąć do N bitów
W przeciwieństwie do innych funkcji, nie jest to możliwe.]}
• ustawianie bitu w Masku bitowym j ' TH var dla konfliktu z i

Jest drugi spacer N^2 add_alias_set_conflicts. Sprawdza typ dla każdej pary z objects_must_conflict_p. Sprawdza, Jeśli dwie zmienne są tego samego typu (większość par jest; jest to analiza aliasów opartych na typie, TBAA ). Jeśli nie, wywołane jest add_stack_var_conflict; istnieje tylko N takich wywołań z N^2 gniazda pętli.

Ostatni wielki spacer jest w partition_stack_vars() funkcji z qsort ING stack vars(O(NlogN) ) i N*(N-1)/2 = O (N^2) chodzić, aby znaleźć wszystkie pary nie sprzeczne. Oto pseudokod partition_stack_vars Z cfgexpand.plik 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)
          }
        }

Funkcja stack_var_conflict_p po prostu sprawdza czy istnieje konfliktowa maska bitowa w jakiejś i-tej zmiennej i jest tam j-ten bit ustawiony jako flaga konfliktu z J-tą zmienną(z wywołaniem do bitmap_bit_p(i->conflict_mask,j)). Naprawdę zła wiadomość jest taka, że callgrind mówi, że każda kontrola konfliktu zakończyła się sukcesem, a logika Unii jest pomijana dla każdej pary.

Tak więc, dużo czasu marnują zestawy bitów O(N^2) i sprawdzanie bitów O(N^2/2); i cała ta praca nie pomaga w optymalizacji czegokolwiek. I tak, to wszystko jest częścią -O0 I wywołane przez -fstack-protector.

UPDATE2:

Wydaje się, że punktem zwrotnym jest expand_one_var cfgexpand.c od 4.6 , W sprawdzeniu natychmiastowego lub odroczonego przydzielenia zmiennej na stosie:

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        }

Deferred allocation jest wymuszone, gdy -fstack-protect jest włączona (czasami trzeba zmienić kolejność wszystkich zmiennych stosu). Jest nawet komentarz o jakimś "problemie kwadratowym", który wygląda nam teraz zbyt znajomo: {]}

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;

(przydział stosu jest również odroczony na -O2 i greater)

Oto commit: http://gcc.gnu.org/ml/gcc-patches/2005-05/txt00029.txt który dodał tę logikę.