Ich habe eine STL-Implementierung einer populären XmlRpc-Bibliothek mit einer Implementierung verglichen, die meistens STL vermeidet. Die STL-Implementierung ist viel langsamer - ich habe 47s runter auf 4,5s. Ich habe einige der Gründe diagnostiziert: es liegt teilweise daran, dass std :: string falsch verwendet wird (zB sollte der Autor "const std :: string & amp;" verwenden, wo immer möglich - nicht einfach std :: string verwenden) sie waren Java-Strings), aber auch, weil Kopierkonstrukte immer dann aufgerufen wurden, wenn der Vektor seine Grenzen sprengte, was sehr oft vorkam. Die Kopierkonstruktoren waren sehr langsam, weil sie Tiefenkopien von Bäumen (von XmlRpc-Werten) gemacht haben.
Ich wurde von jemand anderem in StackOverflow darauf hingewiesen, dass std :: vector-Implementierungen die Größe des Puffers normalerweise jedes Mal verdoppeln, wenn sie größer werden. Dies scheint bei VisualStudio 2008 nicht der Fall zu sein: Um einem std :: vector 50 Elemente hinzuzufügen, wurden 177 Aufrufe des Kopierkonstruktors benötigt. Verdoppeln Sie jedes Mal den Kopierkonstruktor 64 Mal. Wenn Sie sehr daran interessiert sind, die Speichernutzung gering zu halten, sollten Sie den Kopierkonstruktor jeweils 121 Mal aufrufen, um jedes Mal um 50% zu erhöhen. Woher kommt die 177?
Meine Frage ist: (a) Warum wird der Kopierkonstruktor so oft aufgerufen? (b) Gibt es eine Möglichkeit, den Kopierkonstruktor zu vermeiden, wenn Sie ein Objekt nur von einem Ort zu einem anderen verschieben ? (In diesem Fall und in den meisten Fällen hätte ein memcpy () ausgereicht - und das macht einen großen Unterschied).
(NB: Ich weiß über vector :: reserve (), ich bin nur ein wenig enttäuscht, dass Anwendungsprogrammierer den Doubling-Trick implementieren müssen, wenn sowas schon Teil einer guten STL-Implementierung ist.)
Mein Testprogramm:
%Vor%Die STL neigt dazu, so etwas zu verursachen. Die Spezifikation erlaubt kein Mempy'ing, da dies nicht immer funktioniert. Es gibt ein Dokument, das EASTL beschreibt, eine Reihe von Änderungen von EA, um es für ihre Zwecke besser geeignet zu machen, die eine Methode hat, zu erklären, dass ein Typ zu memcpy sicher ist. Leider ist es nicht Open-Source-AFAIK, so dass wir nicht damit spielen können.
IIRC Dinkumware STL (die in VS) wächst Vektoren jedes Mal um 50%.
Eine Reihe von push_backs auf einem Vektor ist jedoch eine häufige Ineffizienz. Sie können entweder Reserve verwenden, um es zu lindern (auf Kosten der möglicherweise Speicher zu verschwenden, wenn Sie deutlich überschätzen) oder einen anderen Container verwenden - Deque funktioniert besser für eine Reihe von Einfügungen wie diese, ist aber etwas langsamer in Random Access, die möglicherweise / kann nicht ein guter Kompromiss für dich sein.
Oder Sie könnten Zeiger anstelle von Werten speichern, wodurch die Größenanpassung beim Speichern großer Elemente viel billiger wird. Wenn Sie große Objekte speichern, wird dies immer gewinnen, da Sie sie nicht immer kopieren müssen - Sie werden immer mindestens eine Kopie für jedes Element beim Einfügen speichern.
Vergessen Sie nicht, die Aufrufe des Kopierkonstruktors, die für push_back ein temporäres C -Objekt benötigt werden, in den Vektor zu zählen. Jede Iteration ruft den Kopienkonstruktor C mindestens einmal auf.
Wenn Sie mehr Druckcode hinzufügen, ist es etwas klarer, was passiert:
%Vor%Dies hat die folgende Ausgabe:
%Vor%Also ja, die Kapazität erhöht sich jedes Mal um 50% und das macht 127 Kopien aus:
%Vor% Fügen Sie die 50 zusätzlichen Kopien von 50 Aufrufen zu push_back hinzu und Sie haben 177:
Meine Frage ist:
(a) Warum wird der Kopierkonstruktor so oft aufgerufen?
Wenn der Vektor neu skaliert wird, müssen Sie alle Elemente aus dem alten Puffer in den neuen Puffer kopieren. Dies liegt daran, dass der Vektor garantiert, dass die Objekte in aufeinanderfolgenden Speicherorten gespeichert sind.
(b) Gibt es eine Möglichkeit, den Kopierkonstruktor zu vermeiden, wenn Sie gerade umziehen? ein Objekt von einem Ort zum anderen?
Nein, es gibt keine Möglichkeit, die Verwendung des Kopierkonstruktors zu vermeiden.
Dies, weil das Objekt mehrere Member hat, die korrekt initialisiert werden müssen.
Wenn Sie memcpy verwendet haben, wissen Sie, dass das Objekt korrekt für das Objekt initialisiert wurde!
Zum Beispiel. WENN das Objekt einen intelligenten Zeiger enthielt. Sie können nicht nur einen intelligenten Zeiger speichern. Es muss zusätzliche Arbeit leisten, um das Eigentum zu verfolgen. Andernfalls, wenn das Original den Gültigkeitsbereich verlässt, wird der Speicher gelöscht und das neue Objekt hat einen ungeeigneten Zeiger. Dasselbe Prinzip gilt für alle Objekte, die einen Konstruktor (Kopierkonstruktor) haben, den der Konstruktor tatsächlich benötigt.
Der Weg, die Kopie des Inhalts zu stoppen, ist, den Platz zu reservieren.
Dadurch reserviert der Vektor genügend Speicherplatz für alle Objekte, die er speichern soll. Daher muss der Hauptpuffer nicht erneut zugewiesen werden. Es kopiert nur die Objekte in den Vektor.
Jede Verdopplung sollte den Kopierkonstruktor 64 mal aufrufen. Wenn Sie sehr daran interessiert sind, die Speichernutzung gering zu halten, erhöhen Sie sich um Jedesmal sollten 50% den Kopierkonstruktor 121 mal aufrufen. Woher kommt die 177?
Vektor zugewiesene Größe = 1:
Element 1 hinzufügen: (keine Neuzuweisung) Kopiert jedoch Element 1 in Vektor.
Element 2 hinzufügen: Puffer neu zuweisen (Größe 2): Element 1 übergreifend kopieren. Kopiere Element 2 in Vektor.
Element 3 hinzufügen: Puffer neu zuweisen (Größe 4): Element 1-2 übergreifend kopieren. Kopiere Element 3 in Vektor.
Fügen Sie Element 4 hinzu: Kopieren Sie Element 4 in Vektor
Element 5 hinzufügen: Puffer neu zuweisen (Größe 8): Element 1-4 übergreifend kopieren. Kopiere Element 5 in Vektor.
Element 6 hinzufügen: Element 6 in Vektor kopieren
Element 7 hinzufügen: Element 7 in Vektor kopieren
Element 8 hinzufügen: Element 8 in Vektor kopieren
Element 9 hinzufügen: Puffer neu zuweisen (Größe 16): Element 1-8 übergreifend kopieren. Kopiere Element 9 in Vektor.
Element 10 hinzufügen: Element 10 in Vektor kopieren
usw.
Die ersten 10 Elemente haben 25 Kopierkonstruktionen übernommen.
Wenn du zuerst die Reserve benutzt hättest, hättest du nur 10 Kopien benötigt.
Wenn ich mich richtig erinnere, kann C ++ 0x eine Verschiebungssemantik haben (zusätzlich zur Kopiesemantik), das heißt, Sie können einen effizienteren Kopierkonstruktor implementieren, wenn Sie das wirklich wollen.
Wenn der Kopierkonstruktor nicht komplex ist, ist er normalerweise sehr effizient - schließlich soll man nicht viel mehr tun als nur das Objekt kopieren, und das Kopieren von Speicher ist heutzutage sehr schnell.
Es sieht so aus, als ob Additionen zu C ++ 0x hier helfen; siehe Rvalue und STL-Upgrades .
Um dieses Problem zu umgehen, warum nicht einen Vektor von Zeigern anstelle eines Vektors von Objekten verwenden? Dann delete jedes Element beim Zerstören des Vektors.
Mit anderen Worten std::vector<C*> anstelle von std::vector<C> . Memcpy'ing Zeiger ist sehr schnell.
Nur eine Anmerkung, seien Sie vorsichtig beim Hinzufügen von Zeigern zum Vektor, um die Kopierkosten zu minimieren, da
Verwenden Sie häufiger den Vektor oder fügen Sie hinzu?