std :: vector-Leistungsregression beim Aktivieren von C ++ 11

235

Ich habe eine interessante Leistungsregression in einem kleinen C ++ - Snippet gefunden, wenn ich C ++ 11 aktiviere:

#include <vector>

struct Item
{
  int a;
  int b;
};

int main()
{
  const std::size_t num_items = 10000000;
  std::vector<Item> container;
  container.reserve(num_items);
  for (std::size_t i = 0; i < num_items; ++i) {
    container.push_back(Item());
  }
  return 0;
}

Mit g ++ (GCC) 4.8.2 20131219 (Vorabversion) und C ++ 03 bekomme ich:

milian:/tmp$ g++ -O3 main.cpp && perf stat -r 10 ./a.out

Performance counter stats for './a.out' (10 runs):

        35.206824 task-clock                #    0.988 CPUs utilized            ( +-  1.23% )
                4 context-switches          #    0.116 K/sec                    ( +-  4.38% )
                0 cpu-migrations            #    0.006 K/sec                    ( +- 66.67% )
              849 page-faults               #    0.024 M/sec                    ( +-  6.02% )
       95,693,808 cycles                    #    2.718 GHz                      ( +-  1.14% ) [49.72%]
  <not supported> stalled-cycles-frontend 
  <not supported> stalled-cycles-backend  
       95,282,359 instructions              #    1.00  insns per cycle          ( +-  0.65% ) [75.27%]
       30,104,021 branches                  #  855.062 M/sec                    ( +-  0.87% ) [77.46%]
            6,038 branch-misses             #    0.02% of all branches          ( +- 25.73% ) [75.53%]

      0.035648729 seconds time elapsed                                          ( +-  1.22% )

Wenn C ++ 11 aktiviert ist, verschlechtert sich die Leistung erheblich:

milian:/tmp$ g++ -std=c++11 -O3 main.cpp && perf stat -r 10 ./a.out

Performance counter stats for './a.out' (10 runs):

        86.485313 task-clock                #    0.994 CPUs utilized            ( +-  0.50% )
                9 context-switches          #    0.104 K/sec                    ( +-  1.66% )
                2 cpu-migrations            #    0.017 K/sec                    ( +- 26.76% )
              798 page-faults               #    0.009 M/sec                    ( +-  8.54% )
      237,982,690 cycles                    #    2.752 GHz                      ( +-  0.41% ) [51.32%]
  <not supported> stalled-cycles-frontend 
  <not supported> stalled-cycles-backend  
      135,730,319 instructions              #    0.57  insns per cycle          ( +-  0.32% ) [75.77%]
       30,880,156 branches                  #  357.057 M/sec                    ( +-  0.25% ) [75.76%]
            4,188 branch-misses             #    0.01% of all branches          ( +-  7.59% ) [74.08%]

    0.087016724 seconds time elapsed                                          ( +-  0.50% )

Kann das jemand erklären? Bisher habe ich die Erfahrung gemacht, dass die STL durch die Aktivierung von C ++ 11 schneller wird, insb. dank Bewegungssemantik.

BEARBEITEN: Wie vorgeschlagen, wird container.emplace_back();die Leistung stattdessen mit der C ++ 03-Version gleichgesetzt. Wie kann die C ++ 03-Version dasselbe erreichen push_back?

milian:/tmp$ g++ -std=c++11 -O3 main.cpp && perf stat -r 10 ./a.out

Performance counter stats for './a.out' (10 runs):

        36.229348 task-clock                #    0.988 CPUs utilized            ( +-  0.81% )
                4 context-switches          #    0.116 K/sec                    ( +-  3.17% )
                1 cpu-migrations            #    0.017 K/sec                    ( +- 36.85% )
              798 page-faults               #    0.022 M/sec                    ( +-  8.54% )
       94,488,818 cycles                    #    2.608 GHz                      ( +-  1.11% ) [50.44%]
  <not supported> stalled-cycles-frontend 
  <not supported> stalled-cycles-backend  
       94,851,411 instructions              #    1.00  insns per cycle          ( +-  0.98% ) [75.22%]
       30,468,562 branches                  #  840.991 M/sec                    ( +-  1.07% ) [76.71%]
            2,723 branch-misses             #    0.01% of all branches          ( +-  9.84% ) [74.81%]

   0.036678068 seconds time elapsed                                          ( +-  0.80% )
milianw
quelle
1
Wenn Sie zur Assembly kompilieren, können Sie sehen, was unter der Haube vor sich geht. Siehe auch stackoverflow.com/questions/8021874/…
Zahnrad
8
Was passiert , wenn Sie ändern , push_back(Item())um emplace_back()in der C ++ 11 - Version?
Zahnrad
8
Siehe oben, das "behebt" die Regression. Ich frage mich immer noch, warum die Leistung von push_back zwischen C ++ 03 und C ++ 11 nachlässt.
Milianw
1
@milianw Es stellte sich heraus, dass ich das falsche Programm kompiliert habe. Ignoriere meine Kommentare.
2
Mit clang3.4 ist die C ++ 11-Version schneller, 0.047s vs 0.058 für die C ++ 98-Version
Praetorian

Antworten:

247

Ich kann Ihre Ergebnisse auf meinem Computer mit den Optionen reproduzieren, die Sie in Ihrem Beitrag geschrieben haben.

Wenn ich jedoch auch die Optimierung der Verbindungszeit aktiviere (ich übergebe das -fltoFlag auch an gcc 4.7.2), sind die Ergebnisse identisch:

(Ich kompiliere Ihren Originalcode mit container.push_back(Item());)

$ g++ -std=c++11 -O3 -flto regr.cpp && perf stat -r 10 ./a.out 

 Performance counter stats for './a.out' (10 runs):

         35.426793 task-clock                #    0.986 CPUs utilized            ( +-  1.75% )
                 4 context-switches          #    0.116 K/sec                    ( +-  5.69% )
                 0 CPU-migrations            #    0.006 K/sec                    ( +- 66.67% )
            19,801 page-faults               #    0.559 M/sec                  
        99,028,466 cycles                    #    2.795 GHz                      ( +-  1.89% ) [77.53%]
        50,721,061 stalled-cycles-frontend   #   51.22% frontend cycles idle     ( +-  3.74% ) [79.47%]
        25,585,331 stalled-cycles-backend    #   25.84% backend  cycles idle     ( +-  4.90% ) [73.07%]
       141,947,224 instructions              #    1.43  insns per cycle        
                                             #    0.36  stalled cycles per insn  ( +-  0.52% ) [88.72%]
        37,697,368 branches                  # 1064.092 M/sec                    ( +-  0.52% ) [88.75%]
            26,700 branch-misses             #    0.07% of all branches          ( +-  3.91% ) [83.64%]

       0.035943226 seconds time elapsed                                          ( +-  1.79% )



$ g++ -std=c++98 -O3 -flto regr.cpp && perf stat -r 10 ./a.out 

 Performance counter stats for './a.out' (10 runs):

         35.510495 task-clock                #    0.988 CPUs utilized            ( +-  2.54% )
                 4 context-switches          #    0.101 K/sec                    ( +-  7.41% )
                 0 CPU-migrations            #    0.003 K/sec                    ( +-100.00% )
            19,801 page-faults               #    0.558 M/sec                    ( +-  0.00% )
        98,463,570 cycles                    #    2.773 GHz                      ( +-  1.09% ) [77.71%]
        50,079,978 stalled-cycles-frontend   #   50.86% frontend cycles idle     ( +-  2.20% ) [79.41%]
        26,270,699 stalled-cycles-backend    #   26.68% backend  cycles idle     ( +-  8.91% ) [74.43%]
       141,427,211 instructions              #    1.44  insns per cycle        
                                             #    0.35  stalled cycles per insn  ( +-  0.23% ) [87.66%]
        37,366,375 branches                  # 1052.263 M/sec                    ( +-  0.48% ) [88.61%]
            26,621 branch-misses             #    0.07% of all branches          ( +-  5.28% ) [83.26%]

       0.035953916 seconds time elapsed  

Aus den Gründen muss man sich den generierten Assemblycode ( g++ -std=c++11 -O3 -S regr.cpp) ansehen . Im C ++ 11-Modus ist der generierte Code wesentlich übersichtlicher als im C ++ 98-Modus, und das Inlining der Funktion
void std::vector<Item,std::allocator<Item>>::_M_emplace_back_aux<Item>(Item&&)
schlägt im C ++ 11-Modus standardmäßig fehlinline-limit .

Diese fehlgeschlagene Inline hat einen Dominoeffekt. Nicht weil diese Funktion aufgerufen wird (sie wird nicht einmal aufgerufen!), Sondern weil wir vorbereitet sein müssen: Wenn sie aufgerufen wird, müssen die Funktionsargumente ( Item.aund Item.b) bereits an der richtigen Stelle sein. Dies führt zu einem ziemlich chaotischen Code.

Hier ist der relevante Teil des generierten Codes für den Fall, dass Inlining erfolgreich ist :

.L42:
    testq   %rbx, %rbx  # container$D13376$_M_impl$_M_finish
    je  .L3 #,
    movl    $0, (%rbx)  #, container$D13376$_M_impl$_M_finish_136->a
    movl    $0, 4(%rbx) #, container$D13376$_M_impl$_M_finish_136->b
.L3:
    addq    $8, %rbx    #, container$D13376$_M_impl$_M_finish
    subq    $1, %rbp    #, ivtmp.106
    je  .L41    #,
.L14:
    cmpq    %rbx, %rdx  # container$D13376$_M_impl$_M_finish, container$D13376$_M_impl$_M_end_of_storage
    jne .L42    #,

Dies ist eine schöne und kompakte for-Schleife. Vergleichen wir dies nun mit dem des fehlgeschlagenen Inline- Falls:

.L49:
    testq   %rax, %rax  # D.15772
    je  .L26    #,
    movq    16(%rsp), %rdx  # D.13379, D.13379
    movq    %rdx, (%rax)    # D.13379, *D.15772_60
.L26:
    addq    $8, %rax    #, tmp75
    subq    $1, %rbx    #, ivtmp.117
    movq    %rax, 40(%rsp)  # tmp75, container.D.13376._M_impl._M_finish
    je  .L48    #,
.L28:
    movq    40(%rsp), %rax  # container.D.13376._M_impl._M_finish, D.15772
    cmpq    48(%rsp), %rax  # container.D.13376._M_impl._M_end_of_storage, D.15772
    movl    $0, 16(%rsp)    #, D.13379.a
    movl    $0, 20(%rsp)    #, D.13379.b
    jne .L49    #,
    leaq    16(%rsp), %rsi  #,
    leaq    32(%rsp), %rdi  #,
    call    _ZNSt6vectorI4ItemSaIS0_EE19_M_emplace_back_auxIIS0_EEEvDpOT_   #

Dieser Code ist unübersichtlich und in der Schleife ist viel mehr los als im vorherigen Fall. Vor der Funktion call(letzte Zeile) müssen die Argumente entsprechend platziert werden:

leaq    16(%rsp), %rsi  #,
leaq    32(%rsp), %rdi  #,
call    _ZNSt6vectorI4ItemSaIS0_EE19_M_emplace_back_auxIIS0_EEEvDpOT_   #

Obwohl dies nie ausgeführt wird, ordnet die Schleife die Dinge vorher an:

movl    $0, 16(%rsp)    #, D.13379.a
movl    $0, 20(%rsp)    #, D.13379.b

Dies führt zu dem unordentlichen Code. Wenn es keine Funktion gibt, callweil das Inlining erfolgreich ist, haben wir nur 2 Verschiebungsanweisungen in der Schleife und es gibt kein Durcheinander mit dem %rsp(Stapelzeiger). Wenn das Inlining jedoch fehlschlägt, erhalten wir 6 Züge und wir spielen viel mit dem %rsp.

Nur um meine Theorie zu untermauern (beachten Sie die -finline-limit), beide im C ++ 11-Modus:

 $ g++ -std=c++11 -O3 -finline-limit=105 regr.cpp && perf stat -r 10 ./a.out

 Performance counter stats for './a.out' (10 runs):

         84.739057 task-clock                #    0.993 CPUs utilized            ( +-  1.34% )
                 8 context-switches          #    0.096 K/sec                    ( +-  2.22% )
                 1 CPU-migrations            #    0.009 K/sec                    ( +- 64.01% )
            19,801 page-faults               #    0.234 M/sec                  
       266,809,312 cycles                    #    3.149 GHz                      ( +-  0.58% ) [81.20%]
       206,804,948 stalled-cycles-frontend   #   77.51% frontend cycles idle     ( +-  0.91% ) [81.25%]
       129,078,683 stalled-cycles-backend    #   48.38% backend  cycles idle     ( +-  1.37% ) [69.49%]
       183,130,306 instructions              #    0.69  insns per cycle        
                                             #    1.13  stalled cycles per insn  ( +-  0.85% ) [85.35%]
        38,759,720 branches                  #  457.401 M/sec                    ( +-  0.29% ) [85.43%]
            24,527 branch-misses             #    0.06% of all branches          ( +-  2.66% ) [83.52%]

       0.085359326 seconds time elapsed                                          ( +-  1.31% )

 $ g++ -std=c++11 -O3 -finline-limit=106 regr.cpp && perf stat -r 10 ./a.out

 Performance counter stats for './a.out' (10 runs):

         37.790325 task-clock                #    0.990 CPUs utilized            ( +-  2.06% )
                 4 context-switches          #    0.098 K/sec                    ( +-  5.77% )
                 0 CPU-migrations            #    0.011 K/sec                    ( +- 55.28% )
            19,801 page-faults               #    0.524 M/sec                  
       104,699,973 cycles                    #    2.771 GHz                      ( +-  2.04% ) [78.91%]
        58,023,151 stalled-cycles-frontend   #   55.42% frontend cycles idle     ( +-  4.03% ) [78.88%]
        30,572,036 stalled-cycles-backend    #   29.20% backend  cycles idle     ( +-  5.31% ) [71.40%]
       140,669,773 instructions              #    1.34  insns per cycle        
                                             #    0.41  stalled cycles per insn  ( +-  1.40% ) [88.14%]
        38,117,067 branches                  # 1008.646 M/sec                    ( +-  0.65% ) [89.38%]
            27,519 branch-misses             #    0.07% of all branches          ( +-  4.01% ) [86.16%]

       0.038187580 seconds time elapsed                                          ( +-  2.05% )

Wenn wir den Compiler bitten, sich nur ein wenig mehr Mühe zu geben, um diese Funktion zu integrieren, verschwindet der Leistungsunterschied.


Was bringt diese Geschichte? Dass fehlgeschlagene Inlines viel kosten können und Sie die Compiler-Funktionen voll ausnutzen sollten: Ich kann nur die Optimierung der Verbindungszeit empfehlen. Es gab meinen Programmen einen signifikanten Leistungsschub (bis zu 2,5x) und alles was ich tun musste, war die -fltoFlagge zu übergeben. Das ist ein ziemlich guter Deal! ;)

Ich empfehle jedoch nicht, Ihren Code mit dem Inline-Schlüsselwort zu verwerfen. Lassen Sie den Compiler entscheiden, was zu tun ist. (Der Optimierer darf das Inline-Schlüsselwort ohnehin als Leerzeichen behandeln.)


Gute Frage, +1!

Ali
quelle
3
NB: inlinehat nichts mit Funktionsinlining zu tun; es bedeutet "definiert inline" nicht "bitte inline dies". Wenn Sie tatsächlich nach Inlining fragen möchten, verwenden Sie __attribute__((always_inline))oder ähnliches.
Jon Purdy
2
@ JonPurdy Nicht ganz, zum Beispiel sind Klassenmitgliedsfunktionen implizit inline. inlineDies ist auch eine Anfrage an den Compiler, dass die Funktion eingebunden werden soll, und beispielsweise, dass der Intel C ++ - Compiler Leistungswarnungen ausgibt, wenn er Ihre Anfrage nicht erfüllt. (Ich habe icc in letzter Zeit nicht überprüft, ob dies immer noch der Fall ist.) Leider habe ich gesehen, wie Leute ihren Code mit dem Papierkorb weggeworfen haben inlineund darauf gewartet haben, dass ein Wunder geschieht. Ich würde nicht verwenden __attribute__((always_inline)); Wahrscheinlich wissen die Compiler-Entwickler besser, was sie inline und was nicht. (Trotz des Gegenbeispiels hier.)
Ali
1
@JonPurdy Wenn Sie andererseits eine Funktion inline definieren, die keine Mitgliedsfunktion einer Klasse ist , haben Sie in der Tat keine andere Wahl, als sie inline zu markieren, da Sie sonst mehrere Definitionsfehler vom Linker erhalten. Wenn Sie das gemeint haben, dann OK.
Ali
1
Ja, das habe ich gemeint. Der Standard sagt: "Der inlineSpezifizierer gibt der Implementierung an, dass die Inline-Substitution des Funktionskörpers am Aufrufpunkt dem üblichen Funktionsaufrufmechanismus vorzuziehen ist." (§7.1.2.2) Für diese Optimierung sind jedoch keine Implementierungen erforderlich, da es größtenteils ein Zufall ist, dass inlineFunktionen häufig gute Kandidaten für Inlining sind. Es ist also besser, explizit zu sein und ein Compiler-Pragma zu verwenden.
Jon Purdy
3
@ JonPurdy Wie für die erste Hälfte: Ja, das habe ich mit "Der Optimierer darf das Inline-Schlüsselwort sowieso als Leerzeichen behandeln " gemeint . Was das Compiler-Pragma betrifft, würde ich das nicht verwenden, ich würde es der Optimierung der Verbindungszeit überlassen, ob inline oder nicht. Es macht einen ziemlich guten Job; Dieses hier in der Antwort beschriebene Problem wurde ebenfalls automatisch behoben.
Ali