Frage Leistung von pIter! = Cont.end () in for-Schleife


Ich habe in letzter Zeit "Exceptional C ++" von Herb Sutter durchgemacht, und ich habe ernsthafte Zweifel an einer bestimmten Empfehlung, die er in Punkt 6 - Temporäre Objekte gibt.

Er bietet an, unnötige temporäre Objekte im folgenden Code zu finden:

string FindAddr(list<Employee> emps, string name) 
{
  for (list<Employee>::iterator i = emps.begin(); i != emps.end(); i++)
  {
    if( *i == name )
    {
      return i->addr;
    }
  }
  return "";
}

Als ein Beispiel empfiehlt er, den Wert von vorzurechnen emps.end() vor der Schleife, da bei jeder Iteration ein temporäres Objekt erstellt wird:

Bei den meisten Containern (einschließlich der Liste) gibt der Aufruf von end () den Wert a zurück   temporäres Objekt, das konstruiert und zerstört werden muss. Weil das   Wert ändert sich nicht, Neuberechnung (und Rekonstruktion und   es zu zerstören) es auf jeder Schleife Iteration ist beide unnötig   ineffizient und unästhetisch. Der Wert sollte nur einmal berechnet werden,   in einem lokalen Objekt gespeichert und wiederverwendet.

Und er schlägt vor, durch folgendes zu ersetzen:

list<Employee>::const_iterator end(emps.end());
for (list<Employee>::const_iterator i = emps.begin(); i != end; ++i)

Für mich ist das eine unnötige Komplikation. Selbst wenn man hässliche Typdeklarationen durch compact ersetzt auto, er erhält immer noch zwei Codezeilen statt einer. Mehr noch, er hat das end Variable im äußeren Bereich.

Ich war mir sicher, dass moderne Compiler dieses Stück Code sowieso optimieren werden, weil ich es tatsächlich benutze const_iterator Hier ist es leicht zu überprüfen, ob der Inhalt der Schleife irgendwie auf den Container zugreift. Compiler wurden in den letzten 13 Jahren schlauer, oder?

Wie auch immer, ich werde die erste Version mit bevorzugen i != emps.end() In den meisten Fällen, in denen ich nicht so sehr um die Leistung besorgt bin. Aber ich möchte sicher wissen, ob dies eine Art von Konstruktion ist, auf die ich mich verlassen könnte, um einen Compiler zu optimieren?

Aktualisieren

Vielen Dank für Ihre Vorschläge, wie Sie diesen nutzlosen Code verbessern können. Bitte beachten Sie, meine Frage bezieht sich auf Compiler, nicht auf Programmiertechniken. Die einzigen relevanten Antworten für jetzt sind von NPE und Ellioh.


19
2018-03-15 13:10


Ursprung


Antworten:


UPD: Das Buch, von dem du sprichst, wurde 1999 veröffentlicht, es sei denn, ich irre es. Das ist vor 14 Jahren, und in der modernen Programmierung ist 14 Jahre viel Zeit. Viele Empfehlungen, die 1999 gut und zuverlässig waren, können inzwischen völlig veraltet sein. Obwohl meine Antwort sich auf einen einzelnen Compiler und eine einzelne Plattform bezieht, gibt es auch eine allgemeinere Idee.

Sich um zusätzliche Variablen zu kümmern, den Rückgabewert trivialer Methoden und ähnlicher Tricks von altem C ++ wiederzuverwenden, ist ein Schritt zurück in Richtung C ++ der 1990er Jahre. Triviale Methoden wie end() sollte gut inline sein, und das Ergebnis des Inlinens sollte als Teil des Codes optimiert werden, von dem es aufgerufen wird. 99% ige Situationen erfordern keine manuellen Aktionen wie das Erstellen eines end Variable überhaupt. Solche Dinge sollten nur getan werden, wenn:

  1. Sie wissen, dass auf einigen der Compiler / Plattformen, die Sie ausführen sollten, der Code nicht gut optimiert ist.
  2. Es ist zu einem Engpass in Ihrem Programm geworden ("vermeiden Sie vorzeitige Optimierung").

Ich habe untersucht, was von 64-Bit-g ++ erzeugt wird:

gcc version 4.6.3 20120918 (prerelease) (Ubuntu/Linaro 4.6.3-10ubuntu1)

Anfangs dachte ich, dass mit Optimierungen darauf sollte es in Ordnung sein und es sollte keinen Unterschied zwischen zwei Versionen geben. Aber es sieht so aus als wären die Dinge seltsam: die Version, die Sie als nicht optimal betrachten, ist tatsächlich besser. Ich denke, die Moral ist: Es gibt keinen Grund zu versuchen, schlauer zu sein als ein Compiler. Lass uns beide Versionen sehen.

#include <list>

using namespace std;

int main() {
  list<char> l;
  l.push_back('a');

  for(list<char>::iterator i=l.begin(); i != l.end(); i++)
      ;

  return 0;
}

int main1() {
  list<char> l;
  l.push_back('a');
  list<char>::iterator e=l.end();
  for(list<char>::iterator i=l.begin(); i != e; i++)
      ;

  return 0;
}

Dann sollten wir das mit Optimierungen kompilieren (ich benutze 64-Bit g++, können Sie Ihren Compiler versuchen) und disassemblieren main und main1:

Zum main:

(gdb) disas main
Dump of assembler code for function main():
   0x0000000000400650 <+0>: push   %rbx
   0x0000000000400651 <+1>: mov    $0x18,%edi
   0x0000000000400656 <+6>: sub    $0x20,%rsp
   0x000000000040065a <+10>:    lea    0x10(%rsp),%rbx
   0x000000000040065f <+15>:    mov    %rbx,0x10(%rsp)
   0x0000000000400664 <+20>:    mov    %rbx,0x18(%rsp)
   0x0000000000400669 <+25>:    callq  0x400630 <_Znwm@plt>
   0x000000000040066e <+30>:    cmp    $0xfffffffffffffff0,%rax
   0x0000000000400672 <+34>:    je     0x400678 <main()+40>
   0x0000000000400674 <+36>:    movb   $0x61,0x10(%rax)
   0x0000000000400678 <+40>:    mov    %rax,%rdi
   0x000000000040067b <+43>:    mov    %rbx,%rsi
   0x000000000040067e <+46>:    callq  0x400610 <_ZNSt8__detail15_List_node_base7_M_hookEPS0_@plt>
   0x0000000000400683 <+51>:    mov    0x10(%rsp),%rax
   0x0000000000400688 <+56>:    cmp    %rbx,%rax
   0x000000000040068b <+59>:    je     0x400698 <main()+72>
   0x000000000040068d <+61>:    nopl   (%rax)
   0x0000000000400690 <+64>:    mov    (%rax),%rax
   0x0000000000400693 <+67>:    cmp    %rbx,%rax
   0x0000000000400696 <+70>:    jne    0x400690 <main()+64>
   0x0000000000400698 <+72>:    mov    %rbx,%rdi
   0x000000000040069b <+75>:    callq  0x400840 <std::list<char, std::allocator<char> >::~list()>
   0x00000000004006a0 <+80>:    add    $0x20,%rsp
   0x00000000004006a4 <+84>:    xor    %eax,%eax
   0x00000000004006a6 <+86>:    pop    %rbx
   0x00000000004006a7 <+87>:    retq   

Sehen Sie sich die Befehle 0x0000000000400683-0x000000000040068b an. Das ist der Loop-Body und es scheint perfekt zu sein:

   0x0000000000400690 <+64>:    mov    (%rax),%rax
   0x0000000000400693 <+67>:    cmp    %rbx,%rax
   0x0000000000400696 <+70>:    jne    0x400690 <main()+64>

Zum main1:

(gdb) disas main1
Dump of assembler code for function main1():
   0x00000000004007b0 <+0>: push   %rbp
   0x00000000004007b1 <+1>: mov    $0x18,%edi
   0x00000000004007b6 <+6>: push   %rbx
   0x00000000004007b7 <+7>: sub    $0x18,%rsp
   0x00000000004007bb <+11>:    mov    %rsp,%rbx
   0x00000000004007be <+14>:    mov    %rsp,(%rsp)
   0x00000000004007c2 <+18>:    mov    %rsp,0x8(%rsp)
   0x00000000004007c7 <+23>:    callq  0x400630 <_Znwm@plt>
   0x00000000004007cc <+28>:    cmp    $0xfffffffffffffff0,%rax
   0x00000000004007d0 <+32>:    je     0x4007d6 <main1()+38>
   0x00000000004007d2 <+34>:    movb   $0x61,0x10(%rax)
   0x00000000004007d6 <+38>:    mov    %rax,%rdi
   0x00000000004007d9 <+41>:    mov    %rsp,%rsi
   0x00000000004007dc <+44>:    callq  0x400610 <_ZNSt8__detail15_List_node_base7_M_hookEPS0_@plt>
   0x00000000004007e1 <+49>:    mov    (%rsp),%rdi
   0x00000000004007e5 <+53>:    cmp    %rbx,%rdi
   0x00000000004007e8 <+56>:    je     0x400818 <main1()+104>
   0x00000000004007ea <+58>:    mov    %rdi,%rax
   0x00000000004007ed <+61>:    nopl   (%rax)
   0x00000000004007f0 <+64>:    mov    (%rax),%rax
   0x00000000004007f3 <+67>:    cmp    %rbx,%rax
   0x00000000004007f6 <+70>:    jne    0x4007f0 <main1()+64>
   0x00000000004007f8 <+72>:    mov    (%rdi),%rbp
   0x00000000004007fb <+75>:    callq  0x4005f0 <_ZdlPv@plt>
   0x0000000000400800 <+80>:    cmp    %rbx,%rbp
   0x0000000000400803 <+83>:    je     0x400818 <main1()+104>
   0x0000000000400805 <+85>:    nopl   (%rax)
   0x0000000000400808 <+88>:    mov    %rbp,%rdi
   0x000000000040080b <+91>:    mov    (%rdi),%rbp
   0x000000000040080e <+94>:    callq  0x4005f0 <_ZdlPv@plt>
   0x0000000000400813 <+99>:    cmp    %rbx,%rbp
   0x0000000000400816 <+102>:   jne    0x400808 <main1()+88>
   0x0000000000400818 <+104>:   add    $0x18,%rsp
   0x000000000040081c <+108>:   xor    %eax,%eax
   0x000000000040081e <+110>:   pop    %rbx
   0x000000000040081f <+111>:   pop    %rbp
   0x0000000000400820 <+112>:   retq   

Der Code für die Schleife ist ähnlich, es ist:

   0x00000000004007f0 <+64>:    mov    (%rax),%rax
   0x00000000004007f3 <+67>:    cmp    %rbx,%rax
   0x00000000004007f6 <+70>:    jne    0x4007f0 <main1()+64>

Aber es gibt viel zusätzliches Zeug um die Schleife herum. Anscheinend hat zusätzlicher Code die Dinge SCHLECHT gemacht.


9
2018-03-15 13:47



Ich habe den folgenden leicht hacky Code mit verwendet g++ 4.7.2 mit -O3 -std=c++11und bekam identische Assembly für beide Funktionen:

#include <list>
#include <string>

using namespace std;

struct Employee: public string { string addr; };

string FindAddr1(list<Employee> emps, string name)
{
  for (list<Employee>::const_iterator i = emps.begin(); i != emps.end(); i++)
  {
    if( *i == name )
    {
      return i->addr;
    }
  }
  return "";
}

string FindAddr2(list<Employee> emps, string name)
{
  list<Employee>::const_iterator end(emps.end());
  for (list<Employee>::const_iterator i = emps.begin(); i != end; i++)
  {
    if( *i == name )
    {
      return i->addr;
    }
  }
  return "";
}

Auf jeden Fall sollte die Wahl zwischen den beiden Fassungen in erster Linie auf Gründen der Lesbarkeit beruhen. Ohne Profilerstellung sind mir solche Mikrooptimierungen zu früh erschienen.


8
2018-03-15 13:22



Entgegen der landläufigen Meinung sehe ich in dieser Hinsicht keinen Unterschied zwischen VC ++ und gcc. Ich habe eine kurze Überprüfung mit g ++ 4.7.2 und MS C ++ 17 (aka VC ++ 2012) gemacht.

In beiden Fällen habe ich den generierten Code mit dem Code in der Frage (mit Kopfzeilen und so hinzugefügt, um ihn kompilieren zu lassen) mit dem folgenden Code verglichen:

string FindAddr(list<Employee> emps, string name) 
{
    auto end = emps.end();
    for (list<Employee>::iterator i = emps.begin(); i != end; i++)
    {
        if( *i == name )
        {
            return i->addr;
        }
    }
    return "";
}

In beiden Fällen war das Ergebnis für die beiden Codeteile im Wesentlichen identisch. VC ++ enthält Zeilennummernkommentare im Code, die wegen der zusätzlichen Zeile geändert wurden, aber das war der einzige Unterschied. Mit g ++ waren die Ausgabedateien identisch.

Das gleiche tun mit std::vector Anstatt von std::list, gab fast das gleiche Ergebnis - keinen signifikanten Unterschied. Aus irgendeinem Grund hat g ++ die Reihenfolge der Operanden für eine Anweisung von geändert cmp esi, DWORD PTR [eax+4] zu cmp DWORD PTR [eax+4], esi, aber (wieder) das ist völlig irrelevant.

Fazit: Nein, Sie werden wahrscheinlich nichts davon bekommen, wenn Sie den Code mit einem modernen Compiler manuell aus der Schleife hissen (zumindest mit optimierter Optimierung, die ich verwendete) /O2b2 mit VC ++ und /O3 mit g ++; Optimieren mit optimierter Optimierung zu vergleichen, erscheint mir ziemlich sinnlos).


4
2018-03-15 14:59



Ein paar Dinge ... die erste ist, dass im Allgemeinen die Kosten für die Erstellung eines Iterators (im Freigabemodus, ungeprüfte Allokatoren) minimal sind. Sie sind normalerweise Wrapper um einen Zeiger. Mit überprüften Zuordnern (Standard in VS) können Sie Kosten haben, aber wenn Sie wirklich die Leistung benötigen, nach dem Testen der Neuerstellung mit ungeprüften Allokatoren.

Der Code muss nicht so hässlich sein wie das, was du gepostet hast:

for (list<Employee>::const_iterator it=emps.begin(), end=emps.end(); 
                                    it != end; ++it )

Die wichtigste Entscheidung darüber, ob Sie den einen oder anderen Ansatz verwenden möchten, sollte darin bestehen, welche Vorgänge auf den Container angewendet werden. Wenn der Container seine Größe ändert, möchten Sie möglicherweise den Wert neu berechnen end Iterator in jeder Iteration. Wenn nicht, können Sie die Vorberechnung nur einmal durchführen und wie im obigen Code wiederverwenden.


3
2018-03-15 13:16



Container wie Vektor gibt Variable zurück, die den Zeiger bis zum Ende speichert, an end() Ruf, das optimiert. Wenn Sie einen Container geschrieben haben, der einige Suchvorgänge usw. durchführt end()Anruf in Betracht ziehen schreiben

for (list<Employee>::const_iterator i = emps.begin(), end = emps.end(); i != end; ++i)
{
...
}

für Geschwindigkeit


2
2018-03-15 13:15



Wenn Sie wirklich die Leistung brauchen, lassen Sie Ihren glänzenden neuen C ++ 11 Compiler es für Sie schreiben:

for (const auto &i : emps) {
    /* ... */
}

Ja, das ist augenzwinkernd (so). Herbs Beispiel hier ist jetzt veraltet. Aber da Ihr Compiler es noch nicht unterstützt, kommen wir zur eigentlichen Frage:

Ist das eine Art von Konstruktion, auf die ich mich verlassen könnte, um einen Compiler zu optimieren?

Meine Faustregel ist, dass die Compiler-Autoren viel schlauer sind als ich. Ich kann mich nicht darauf verlassen, dass ein Compiler ein einzelnes Codeelement optimiert, weil es möglicherweise optimiert wird etwas anderes Das hat eine größere Wirkung. Der einzige Weg, um sicher zu wissen, ist, beide Ansätze an zu probieren Ihre Compiler auf Ihre System und sehen, was passiert. Überprüfen Sie Ihre Profilergebnisse. Wenn der Anruf an .end() ragt heraus, speichern Sie es in einer separaten Variablen. Ansonsten mach dir keine Sorgen.


2
2018-03-15 13:20



Benutzen std Algorithmen

Er hat natürlich Recht; Berufung end kann ein temporäres Objekt instanziieren und zerstören, was in der Regel schlecht ist.

Natürlich kann der Compiler dies in vielen Fällen optimieren.

Es gibt eine bessere und robustere Lösung: kapseln Sie Ihre Schleifen ein.

Das Beispiel, das Sie gegeben haben, ist tatsächlich std::findGeben oder nehmen Sie den Rückgabewert. Viele andere Loops haben auch std Algorithmen, oder zumindest etwas ähnliches, das Sie anpassen können - meine Utility-Bibliothek hat eine transform_if Implementierung zum Beispiel.

Blenden Sie also Schleifen in einer Funktion aus und nehmen Sie eine const& zu end. Das gleiche Problem wie Ihr Beispiel, aber viel viel sauberer.


0
2018-03-15 13:25