In C ++ ist es nach wie vor schlechte Praxis einen Vektor aus einer Funktion zurückgeben?
https://stackoverflow.com/questions/3134831
-
01-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Kurzversion: Es ist üblich, große Objekte-wie Vektoren / Matrizen-in vielen Programmiersprachen zurückzukehren. Ist dieser Stil jetzt akzeptabel in C ++ 0x, wenn die Klasse einen Zug Konstruktor hat, oder tut C ++ Programmierer es komisch / hässlich / Gräuel betrachten?
Lange Version: In C ++ 0x ist dies immer noch als schlechte Form
std::vector<std::string> BuildLargeVector();
...
std::vector<std::string> v = BuildLargeVector();
Die traditionelle Version würde wie folgt aussehen:
void BuildLargeVector(std::vector<std::string>& result);
...
std::vector<std::string> v;
BuildLargeVector(v);
In der neueren Version, wird der Wert von BuildLargeVector zurückgegeben wird, ist ein R-Wert, so v konstruiert werden, würde die Bewegung Konstruktor std::vector verwenden, vorausgesetzt, (N) RVO nicht stattfindet.
Auch vor dem C ++ 0x die erste Form wäre oft als "effizient" wegen (N) RVO. Jedoch (N) RVO liegt im Ermessen des Compilers. Nun, da wir rvalue Referenzen haben, ist es garantiert , dass keine tiefe Kopie stattfinden wird.
Bearbeiten : Ihre Frage ist wirklich nicht über die Optimierung. Beiden Formen gezeigt haben nahezu identische Leistung in der realen Welt-Programmen. Während in der Vergangenheit konnte die erste Form hat, um-of-Größenordnung schlechte Leistung hat. Als Ergebnis war die erste Form ein Hauptcodegeruch in C ++ Programmierung für eine lange Zeit. Nicht mehr, hoffe ich?
Lösung
Dave Abrahams hat eine ziemlich umfassende Analyse von die Geschwindigkeit vorbei / Rückkehr Wert .
Kurze Antwort, wenn Sie einen Wert zurückgeben müssen dann einen Wert zurückgeben. Verwenden Sie Ausgangsreferenzen nicht, weil der Compiler es trotzdem tut. Natürlich gibt es Einschränkungen, so dass Sie diesen Artikel lesen sollten.
Andere Tipps
Mindestens IMO, es ist in der Regel eine schlechte Idee, aber nicht aus Effizienzgründen. Es ist eine schlechte Idee, weil die betreffende Funktion in der Regel als ein generischer Algorithmus geschrieben werden sollte, der seine Leistung über einen Iterator erzeugt. Fast jeder Code, der auf Iteratoren annimmt oder zurück soll einen Behälter statt Betrieb Verdächtiger betrachtet werden.
Sie mich nicht falsch. Es gibt Zeiten, macht es Sinn, Sammlung ähnliche Objekte passieren um (zB Strings), aber für das Beispiel angeführt, würde ich prüfen, vorbei oder der Vektor eine schlechte Idee Rückkehr
Der Kern ist:
Kopieren Elision und RVO können vermeiden, dass die „scary Kopien“ (der Compiler ist nicht erforderlich, diese Optimierungen zu implementieren und in manchen Situationen ist es nicht angewendet werden kann)
C ++ 0x rvalue Referenzen erlaubt ein String / Vektor-Implementierungen, die Garantien das.
Wenn Sie ältere Compiler / STL-Implementierungen verlassen können, Rückkehr Vektoren frei (und stellen Sie sicher, dass Ihre eigenen Objekte, die es unterstützen, auch). Wenn Ihre Code-Basis Bedürfnisse unterstützen „kleinere“ Compiler-Stick an den alten Stil.
Leider hat, dass die großen Einfluss auf Ihre Schnittstellen. Wenn C ++ 0x ist keine Option, und Sie Garantien benötigen, können Sie stattdessen mit Referenzzählung oder copy-on-write Objekte in einigen Szenarien verwenden. Sie haben Nachteile mit Multithreading, though.
(Ich wünschte nur eine Antwort in C ++ wäre einfach und unkompliziert und ohne Bedingungen).
Ja, da C ++ 11, die Kosten von Kopieren die std::vector in den meisten Fällen verschwunden ist.
Allerdings sollte man bedenken, dass die Kosten für die Konstruktion der neue Vektor (dann destructing es) noch vorhanden ist, und Ausgang mit Hilfe von Parametern anstelle von Wert der Rücksendung ist noch nützlich, wenn Sie wünschen, den Vektor der Fähigkeit zur Wiederverwendung. Dies wird als Ausnahme dokumentiert in F.20 die C ++ Basisrichtlinien.
Lassen Sie uns vergleichen:
std::vector<int> BuildLargeVector1(size_t vecSize) {
return std::vector<int>(vecSize, 1);
}
mit:
void BuildLargeVector2(/*out*/ std::vector<int>& v, size_t vecSize) {
v.assign(vecSize, 1);
}
Nun, nehmen wir an, diese Methoden numIter mal in einer engen Schleife anrufen müssen, und eine Aktion ausführen. Zum Beispiel wollen wir die Summe aller Elemente berechnen.
Mit BuildLargeVector1, würden Sie tun:
size_t sum1 = 0;
for (int i = 0; i < numIter; ++i) {
std::vector<int> v = BuildLargeVector1(vecSize);
sum1 = std::accumulate(v.begin(), v.end(), sum1);
}
Mit BuildLargeVector2, würden Sie tun:
size_t sum2 = 0;
std::vector<int> v;
for (int i = 0; i < numIter; ++i) {
BuildLargeVector2(/*out*/ v, vecSize);
sum2 = std::accumulate(v.begin(), v.end(), sum2);
}
Im ersten Beispiel gibt es viele unnötigen dynamische Zuweisungen / Zuordnungsaufhebungen passieren, die in dem zweiten Beispiel verhindert werden durch einen Ausgabeparameter der alten Art und Weise verwenden, die Wiederverwendung bereits zugewiesenen Speicher. Unabhängig davon, ob diese Optimierung ist wert, hängt von den relativ Kosten der Zuordnung / Aufhebung der Zuordnung im Vergleich zu den Kosten der Berechnung / Mutieren des Wertes.
Benchmark
Lassen Sie uns spielen mit den Werten von vecSize und numIter. Wir werden vecSize * numIter konstant halten, so dass „in der Theorie“, es die gleiche Zeit in Anspruch nehmen soll (= gibt es die gleiche Anzahl von Zuweisungen und Ergänzungen, mit den exakt gleichen Werten) und die Differenzzeit kann nur von den Kosten Zuweisungen, Freigaben, und eine bessere Nutzung der Cache.
Genauer gesagt, wollen wir nutzen vecSize * numIter = 2 ^ 31 = 2147483648, weil ich 16 GB RAM und diese Zahl stellt sicher haben, dass nicht mehr als 8 GB zugewiesen wird (sizeof (int) = 4), so dass ich nicht tauschen auf die Festplatte (alle anderen Programme geschlossen wurden, hatte ich ~ 15GB zur Verfügung, wenn der Test ausgeführt wird).
Hier ist der Code:
#include <chrono>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>
class Timer {
using clock = std::chrono::steady_clock;
using seconds = std::chrono::duration<double>;
clock::time_point t_;
public:
void tic() { t_ = clock::now(); }
double toc() const { return seconds(clock::now() - t_).count(); }
};
std::vector<int> BuildLargeVector1(size_t vecSize) {
return std::vector<int>(vecSize, 1);
}
void BuildLargeVector2(/*out*/ std::vector<int>& v, size_t vecSize) {
v.assign(vecSize, 1);
}
int main() {
Timer t;
size_t vecSize = size_t(1) << 31;
size_t numIter = 1;
std::cout << std::setw(10) << "vecSize" << ", "
<< std::setw(10) << "numIter" << ", "
<< std::setw(10) << "time1" << ", "
<< std::setw(10) << "time2" << ", "
<< std::setw(10) << "sum1" << ", "
<< std::setw(10) << "sum2" << "\n";
while (vecSize > 0) {
t.tic();
size_t sum1 = 0;
{
for (int i = 0; i < numIter; ++i) {
std::vector<int> v = BuildLargeVector1(vecSize);
sum1 = std::accumulate(v.begin(), v.end(), sum1);
}
}
double time1 = t.toc();
t.tic();
size_t sum2 = 0;
{
std::vector<int> v;
for (int i = 0; i < numIter; ++i) {
BuildLargeVector2(/*out*/ v, vecSize);
sum2 = std::accumulate(v.begin(), v.end(), sum2);
}
} // deallocate v
double time2 = t.toc();
std::cout << std::setw(10) << vecSize << ", "
<< std::setw(10) << numIter << ", "
<< std::setw(10) << std::fixed << time1 << ", "
<< std::setw(10) << std::fixed << time2 << ", "
<< std::setw(10) << sum1 << ", "
<< std::setw(10) << sum2 << "\n";
vecSize /= 2;
numIter *= 2;
}
return 0;
}
Und hier ist das Ergebnis:
$ g++ -std=c++11 -O3 main.cpp && ./a.out
vecSize, numIter, time1, time2, sum1, sum2
2147483648, 1, 2.360384, 2.356355, 2147483648, 2147483648
1073741824, 2, 2.365807, 1.732609, 2147483648, 2147483648
536870912, 4, 2.373231, 1.420104, 2147483648, 2147483648
268435456, 8, 2.383480, 1.261789, 2147483648, 2147483648
134217728, 16, 2.395904, 1.179340, 2147483648, 2147483648
67108864, 32, 2.408513, 1.131662, 2147483648, 2147483648
33554432, 64, 2.416114, 1.097719, 2147483648, 2147483648
16777216, 128, 2.431061, 1.060238, 2147483648, 2147483648
8388608, 256, 2.448200, 0.998743, 2147483648, 2147483648
4194304, 512, 0.884540, 0.875196, 2147483648, 2147483648
2097152, 1024, 0.712911, 0.716124, 2147483648, 2147483648
1048576, 2048, 0.552157, 0.603028, 2147483648, 2147483648
524288, 4096, 0.549749, 0.602881, 2147483648, 2147483648
262144, 8192, 0.547767, 0.604248, 2147483648, 2147483648
131072, 16384, 0.537548, 0.603802, 2147483648, 2147483648
65536, 32768, 0.524037, 0.600768, 2147483648, 2147483648
32768, 65536, 0.526727, 0.598521, 2147483648, 2147483648
16384, 131072, 0.515227, 0.599254, 2147483648, 2147483648
8192, 262144, 0.540541, 0.600642, 2147483648, 2147483648
4096, 524288, 0.495638, 0.603396, 2147483648, 2147483648
2048, 1048576, 0.512905, 0.609594, 2147483648, 2147483648
1024, 2097152, 0.548257, 0.622393, 2147483648, 2147483648
512, 4194304, 0.616906, 0.647442, 2147483648, 2147483648
256, 8388608, 0.571628, 0.629563, 2147483648, 2147483648
128, 16777216, 0.846666, 0.657051, 2147483648, 2147483648
64, 33554432, 0.853286, 0.724897, 2147483648, 2147483648
32, 67108864, 1.232520, 0.851337, 2147483648, 2147483648
16, 134217728, 1.982755, 1.079628, 2147483648, 2147483648
8, 268435456, 3.483588, 1.673199, 2147483648, 2147483648
4, 536870912, 5.724022, 2.150334, 2147483648, 2147483648
2, 1073741824, 10.285453, 3.583777, 2147483648, 2147483648
1, 2147483648, 20.552860, 6.214054, 2147483648, 2147483648
(Intel i7-7700K @ 4.20GHz; 16GB DDR4 2400MHz; Kubuntu 18.04)
Notation:. Mem (v) = Bildhöhe () * sizeof (int) = Bildhöhe () * 4 auf meiner Plattform
Nicht überraschend, wenn numIter = 1 (das heißt, mem (v) = 8 GB), sind die Zeiten vollkommen identisch. Denn in beiden Fällen sind die Zuteilung wir nur einmal eine große Vektor von 8 GB im Speicher. Dies beweist auch, dass keine Kopie passiert bei Verwendung von BuildLargeVector1 (!): Ich würde nicht genug RAM haben die Kopie zu tun
Wenn numIter = 2, Wiederverwendung der Vektor Kapazität statt einen zweiten Vektors Neuzuteilung ist Wert von 1,37x schneller.
Wenn numIter = 256, Wiederverwendung der Vektor-Kapazität (statt Zuweisung / Aufheben der Zuordnung eines Vektors immer und immer wieder 256 mal ...) ist 2.45x schneller :)
Wir können feststellen, dass time1 ist ziemlich konstant von numIter = 1 zu numIter = 256, was bedeutet, dass eine große Vektor von 8 GB Zuteilung ziemlich viel ist so teuer, wie die Zuteilung 256 Vektoren von 32 MB. Allerdings ist auf jeden Fall teurer als die Zuweisung eines Vektors von 32MB einem großen Vektor von 8 GB Zuteilung, so dass die Kapazität des Vektors Wiederverwendung Leistungssteigerungen bietet.
Von numIter = 512 (mem (v) = 16 MB) zu numIter = 8M (mem (v) = 1 KB) ist der Sweet Spot: Beide Methoden sind genau so schnell und schneller als alle anderen Kombinationen von numIter und vecSize. Das hat wahrscheinlich mit der Tatsache zu tun, dass die L3-Cache-Größe meines Prozessor 8 MB ist, so dass der Vektor ziemlich passt vollständig in Cache. Ich erklären nicht wirklich, warum der plötzliche Sprung von time1 ist für mem (v) = 16MB, wäre es logisch erscheinen, kurz nach passieren, wenn mem (v) = 8 MB. Beachten Sie, dass surschend, in diesem Sweet Spot, nicht wiederverwenden Kapazität ist in der Tat etwas schneller! Ich weiß nicht wirklich das erklären.
Wenn numIter > 8M Dinge beginnen, hässlich zu bekommen. Beide Methoden werden langsamer, aber der Vektor von Wert zurückgegeben wird noch langsamer. Im schlimmsten Fall mit einem Vektor, der nur eine einzige int enthält, Kapazität Wiederverwendung anstatt nach Wert der Rücksendung ist 3,3x schneller. Vermutlich ist dies auf die Fixkosten von malloc (), die zu dominieren beginnen.
Beachten Sie, wie die Kurve für time2 ist glatter als die Kurve für time1. Nicht nur die Wiederverwendung von Vektor-Kapazität im Allgemeinen schneller ist, aber vielleicht noch wichtiger ist, es ist berechenbar
Beachten Sie, dass in dem Sweet Spot, wir in der Lage waren 0,5s auszuführen 2 Milliarden Zugaben von 64-Bit-Integer in ~, die auf einem 64-Bit-Prozessor 4.2GHz ganz optimal ist. Wir sollten besser tun könnte durch die Berechnung, um Parallelisierung alle 8 Kerne zu verwenden (der Test oben verwendet nur einen Kern zu einer Zeit, die ich durch erneutes Ausführen überprüft haben, den Test, während die CPU-Auslastung Überwachung). Die beste Leistung wird erreicht, wenn mem (v) = 16kB, die in der Größenordnung des L1-Cache (L1-Daten-Cache für das i7-7700K ist 4x32kB) ist.
Natürlich werden die Unterschiede immer weniger relevant desto mehr Rechen Sie tatsächlich auf die Daten zu tun haben. Im Folgenden sind die Ergebnisse, wenn wir sum = std::accumulate(v.begin(), v.end(), sum); durch for (int k : v) sum += std::sqrt(2.0*k); ersetzen:
Schlussfolgerungen
- Verwenden von Ausgabeparameter anstelle der Rückkehr von Wert können bieten Performance-Gewinne durch die Wiederverwendung von Kapazitäten.
- Auf einem modernen Desktop-Computer, kann dies zu großen Vektoren nur anwendbar scheint (> 16 MB) und kleine Vektoren (<1 KB).
- Vermeiden Millionen / Milliarden von kleinen Vektoren Zuteilung (<1 kB). Wenn möglich, Wiederverwendungsfähigkeit, oder besser noch, gestalten Sie Ihre Architektur anders.
Die Ergebnisse können auf anderen Plattformen unterscheiden. Wie üblich, wenn Leistung zählt, Schreib Benchmarks für Ihren spezifischen Anwendungsfall.
Ich denke immer noch, es ist eine schlechte Praxis ist, aber es ist erwähnenswert, dass mein Team nutzt MSVC 2008 und GCC 4.1, so dass wir nicht die neuesten Compiler verwenden.
Bisher sind viele der in VTune mit MSVC gezeigt Hotspots 2008 kam zu bespannen Kopieren nach unten. Wir hatten Code wie folgt:
String Something::id() const
{
return valid() ? m_id: "";
}
... beachten Sie, dass wir unsere eigenen String-Typ verwendet (dies erforderlich war, weil wir ein Software Development Kit sind die Bereitstellung wo Plugin Autoren verschiedene Compiler verwendet werden könnten und daher unterschiedlichen, nicht kompatiblen Implementierungen von std :: string / std :: wstring).
Ich habe eine einfache Änderung in Reaktion auf den Aufruf Graph Profilierungs Sitzung Abtasten zeigt String :: String (const String &) eine erhebliche Menge an Zeit zu sein und schießt. Verfahren wie im obigen Beispiel waren die größten Mitwirkenden (eigentlich die Profilierungssitzungsspeicherzuweisung und Aufhebung der Zuordnung zeigten einer des größten Hotspots sein, mit dem String Copykonstruktor der Hauptbeitrag für die Zuweisungen zu sein).
Die Änderung, die ich machte, war einfach:
static String null_string;
const String& Something::id() const
{
return valid() ? m_id: null_string;
}
Doch hat dies einen großen Unterschied! Der Hotspot ging in der folgenden Profiler Sitzungen entfernt, und zusätzlich dazu wir eine Menge gründlicher Unit-Tests machen den Überblick über unsere Anwendungsleistung zu halten. Alle Arten von Performance-Testzeiten deutlich gesunken, nachdem diese einfachen Änderungen.
Fazit: Wir verwenden nicht die allerneuste Compiler, aber wir können immer noch nicht auf dem Compiler zu hängen scheinen das Kopieren für die Rückgabe von Wert zuverlässig Optimierung weg (zumindest nicht in allen Fällen). Das mag nicht der Fall für die neueren Compiler wie MSVC verwenden sein 2010. Ich würde mich freuen, wenn wir C ++ 0x verwenden können und einfach rvalue Referenzen verwenden und nicht immer zur Sorge haben, dass wir unseren Code sind pessimizing durch Rücksendung Komplex Klassen, die von Wert.
[Bearbeiten] Als Nate wies darauf hin, gilt RVO auf Provisorien erstellt innerhalb einer Funktion zurückkehrt. In meinem Fall gab es keine solche Provisorien (mit Ausnahme des ungültigen Zweig, wo wir einen leeren String konstruieren) und damit würde RVO nicht anwendbar gewesen.
Nur ein wenig kleinlich: Es ist in vielen Programmiersprachen nicht üblich Arrays von Funktionen zurückzukehren. In den meisten von ihnen ist ein Verweis auf Array zurückgegeben. In C ++ würde die nächste Analogie Rückkehr boost::shared_array
Wenn die Leistung ein echtes Problem ist, sollten Sie sich bewegen Semantik realisieren sind nicht immer schneller als das Kopieren. Zum Beispiel, wenn Sie eine Zeichenfolge, die die kleine String Optimierung dann für kleine Strings eines Schritt Konstruktor verwendet, muss genau die gleiche Menge an Arbeit als regulären Copykonstruktor tun.
