Es ist die -ftime-report Option in gcc, die den ausführlichen Bericht der Zeit für jede Compilerphase verschwendet druckt .
Ich bin es gewohnt, ubuntu 12.04 64-bit mit gcc 4.6.3 und diesem Code Ihre Situation zu reproduzieren:
#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();
}
Es gibt -ftime-report Ausgänge für verschiedene N (wall Zeit wegen der Hintergrundbelastung ungenau war auf der PC, sehen so auf 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 = 100 000
$ 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
So gibt es einige zusätzliche Arbeit für große N in "erweitern Vars" Phase. Diese Phase ist genau in dieser Zeile: cfgexpand.c:4463 (zwischen TV_VAR_EXPAND Makro).
Die interessante Tatsache: Ich habe sehr kurze Kompilierungszeiten mit meinem benutzerdefinierten kompilierten 32-Bit-g ++ 4.6.2 (~ 20 Sekunden für N = 100000).
Was ist der Unterschied zwischen meinem g ++ und ubuntu g ++? Die eine ist turning on by default der Gcc Stack Protection (-fstack-protect Option) in Ubuntu. Und dieser Schutz wird hinzugefügt, nur um "zu erweitern Vars" Phase (in den Quellen gefunden cfgexpand.c:1644,expand_used_vars(); erwähnt here):
N = 100000, Stapelschutz mit Option deaktiviert -fno-stack-protector (verwenden Sie es für Ihren Code):
$ 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
Laufzeit beträgt 24 Sekunden nach unten von 800.
UPDATE:
Nach gcc innerhalb callgrind Start (Call-Graph-Profiling-Tool von Valgrind), kann ich sagen, dass es N Stack-Variablen gibt. Wenn Stack Protector aktiviert ist, werden sie in der Phase "expand vars" mit drei O (N^2) Algorithmen behandelt. Tatsächlich gibt es N^2 erfolgreiche Konflikterkennungen und 1,5 * N^2-Bit-Manipulationen sowie einige Nested-Loop-Logik.
Warum die Anzahl der Stapelvariablen so hoch ist? Weil jede doppelte Konstante in Ihrem Code in einem anderen Slot im Stack gespeichert wird. Dann wird es aus seinem Slot geladen und übergeben, wie Aufrufkonvention sagt (über den Stapel in x86; über Register in x86_64). Die komische Tatsache: der gesamte Code mit push_back s kompiliert mit -fstack-protector oder mit -fno-stack-protector ist das gleiche; Stack-Layout von Konstanten ist auch gleich.Es sind nur einige Stapellayout-Offsets des Nicht-Push-Back-Codes betroffen (geprüft wurden zwei Läufe mit -S und). Kein zusätzlicher Code wurde von aktiviertem Stapelschutz erstellt.
Die Aktivierung des Stack Protectors verändert das Verhalten im Compiler. Kann nicht genau sagen, wo genau (Anmerkung: es ist möglich, diesen Wendepunkt mit dem Vergleich der Stapelspuren mit von Juan M. Bello Rivas zu finden).
Erste große N * (N + 1)/2 = O (N^2) entfernt ist in expand_used_vars_for_block (tree block, level) Funktion Informationen über Konflikte zwischen Paaren von Stapelvariablen einzustellen:
/* 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);
}
}
Die add_stack_var_conflict(i,j) wendet sich an
- Zuteilung (einmal pro Variable) eine Bitmap mit einer Größe von ... oh, mit dynamischer Größe, die
- auf N Bits wachsen wird in ein wenig Einstellung i'th bitmask des var für Konflikt mit j
- ein bisschen in j-ten var der Bitmaske für Konflikte mit i
Es gibt zweite N^2 Fuß in add_alias_set_conflicts Einstellung. Es gibt Prüfungen für jedes Paar mit objects_must_conflict_p. Es prüft, ob zwei Variablen vom selben Typ sind (die meisten Paare sind; das ist Typ-basierte Alias-Analyse, TBAA). Wenn nicht, wird add_stack_var_conflict aufgerufen; es gibt nur N solche Aufrufe von diesem N^2-Schleifen-Nest.
Letzte große Wanderung ist in partition_stack_vars() Funktion mit qsort ing des Stapel Vars (O (NlogN)) und N * (N-1)/2 = O (N^2) gehen alle nicht miteinander in Konflikt stehende Paare zu finden. Hier ist Pseudo-Code von partition_stack_vars aus cfgexpand.c Datei:
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)
}
}
Funktion stack_var_conflict_p gerade überprüft wird Konflikt bitmask in einem i-te Variable und ist dort j-te Bit gesetzt als Konflikt-Flag mit j-ten Variable (mit Anruf an bitmap_bit_p(i->conflict_mask,j)). Die wirklich schlechte Nachricht hier ist, dass Callgrind sagt, dass jede Konfliktüberprüfung erfolgreich war und die UNION-Logik für jedes Paar übersprungen wird.
So wird viel Zeit verschwendet durch O (N^2) Bitmengen und O (N^2/2) Bitprüfungen; und all diese Arbeit hilft nicht, irgendetwas zu optimieren. Und ja, das ist alles Teil von -O0 und ausgelöst durch -fstack-protector.
UPDATE2:
scheint, ist der Wendepunkt expand_one_varcfgexpand.c from 4.6, in der Prüfung zur sofortigen oder späteren Aufteilung der Variablen auf dem Stapel:
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 hier nur in der schnellen Variante genannt wurde, (nach Callgrind)
Die verzögerte Zuweisung wird erzwungen, wenn -fstack-protect aktiviert ist (manchmal müssen alle Stapelvariablen neu angeordnet werden).Es sogar ein Kommentar über einig „quadratisches Problem“, die jetzt zu uns sieht auch vertraut ist:
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;
(Stapelreservierung bei -O2 zu aufgeschoben wird und größer)
ist hier ein commit: http://gcc.gnu.org/ml/gcc-patches/2005-05/txt00029.txt, die hinzugefügt diese Logik.
Wie lange ist lang? –
Die meisten Compiler sind einfach nicht für mehr als 100.000 Zeilen Dateien optimiert. –
Es dauerte einige Minuten auf meiner Quad-Core-Maschine mit 8 GB Speicher. Zum Glück hat es am Ende erfolgreich kompiliert. – synaptik