Kurzversion: Es ist üblich, große Objekte wie Vektoren / Arrays in vielen Programmiersprachen zurückzugeben. Ist dieser Stil jetzt in C ++ 0x akzeptabel, wenn die Klasse einen Verschiebungskonstruktor hat, oder halten C ++ - Programmierer ihn für seltsam / hässlich / abscheulich?

Lange Version: Wird dies in C ++ 0x immer noch als schlechte Form angesehen?

std::vector<std::string> BuildLargeVector();
...
std::vector<std::string> v = BuildLargeVector();

Die traditionelle Version würde so aussehen:

void BuildLargeVector(std::vector<std::string>& result);
...
std::vector<std::string> v;
BuildLargeVector(v);

In der neueren Version ist der zurückgegebene Wert BuildLargeVectorein r- Wert , daher würde v mit dem Verschiebungskonstruktor von erstellt std::vector, vorausgesetzt, (N) RVO findet nicht statt.

Selbst vor C ++ 0x war die erste Form aufgrund von (N) RVO oft "effizient". (N) RVO liegt jedoch im Ermessen des Compilers. Jetzt, da wir rWert-Referenzen haben, ist garantiert, dass keine tiefe Kopie stattfindet.

Edit : Bei der Frage geht es wirklich nicht um Optimierung. Beide gezeigten Formen weisen in realen Programmen eine nahezu identische Leistung auf. Während in der Vergangenheit die erste Form eine um eine Größenordnung schlechtere Leistung hätte erzielen können. Infolgedessen war die erste Form lange Zeit ein Hauptcodegeruch in der C ++ - Programmierung. Nicht mehr, hoffe ich?

Dave Abrahams hat eine ziemlich umfassende Analyse der Geschwindigkeit der Übergabe / Rückgabe von Werten .

Kurze Antwort: Wenn Sie einen Wert zurückgeben müssen, geben Sie einen Wert zurück. Verwenden Sie keine Ausgabereferenzen, da der Compiler dies trotzdem tut. Natürlich gibt es Vorbehalte, deshalb sollten Sie diesen Artikel lesen.

Zumindest IMO, es ist normalerweise eine schlechte Idee, aber nicht aus Effizienzgründen. Dies ist eine schlechte Idee, da die betreffende Funktion normalerweise als generischer Algorithmus geschrieben werden sollte, der ihre Ausgabe über einen Iterator erzeugt. Fast jeder Code, der einen Container akzeptiert oder zurückgibt, anstatt mit Iteratoren zu arbeiten, sollte als verdächtig angesehen werden.

Verstehen Sie mich nicht falsch: Manchmal ist es sinnvoll, sammlungsähnliche Objekte (z. B. Zeichenfolgen) weiterzugeben, aber für das angeführte Beispiel würde ich die Übergabe oder Rückgabe des Vektors als schlechte Idee betrachten.

Das Wesentliche ist:

Copy Elision und RVO können die "beängstigenden Kopien" vermeiden (der Compiler muss diese Optimierungen nicht implementieren und kann in einigen Situationen nicht angewendet werden).

C ++ 0x RValue-Referenzen ermöglichen eine String / Vektor-Implementierung, die dies garantiert .

Wenn Sie ältere Compiler / STL-Implementierungen aufgeben können, geben Sie Vektoren frei zurück (und stellen Sie sicher, dass auch Ihre eigenen Objekte dies unterstützen). Wenn Ihre Codebasis "kleinere" Compiler unterstützen muss, halten Sie sich an den alten Stil.

Leider hat dies großen Einfluss auf Ihre Schnittstellen. Wenn C ++ 0x keine Option ist und Sie Garantien benötigen, können Sie in einigen Szenarien stattdessen Objekte mit Referenzzählung oder Copy-on-Write verwenden. Sie haben jedoch Nachteile beim Multithreading.

(Ich wünschte, nur eine Antwort in C ++ wäre einfach und unkompliziert und ohne Bedingungen).

Tatsächlich, da C ++ 11, die Kosten für das Kopieren der std::vectorin den meisten Fällen verschwunden.

Beachten Sie jedoch, dass die Kosten für die Erstellung des neuen Vektors (und die anschließende Zerstörung ) weiterhin bestehen und die Verwendung von Ausgabeparametern anstelle der Rückgabe nach Wert weiterhin nützlich ist, wenn Sie die Kapazität des Vektors wiederverwenden möchten. Dies ist als Ausnahme in F.20 der C ++ - Kernrichtlinien dokumentiert .

Lass 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);
}

Angenommen, wir müssen diese Methoden numItermal in einer engen Schleife aufrufen und eine Aktion ausführen. Berechnen wir zum Beispiel die Summe aller Elemente.

Mit BuildLargeVector1wü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 BuildLargeVector2wü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 treten viele unnötige dynamische Zuweisungen / Freigaben auf, die im zweiten Beispiel verhindert werden, indem ein Ausgabeparameter auf die alte Weise verwendet wird und bereits zugewiesener Speicher wiederverwendet wird. Ob sich diese Optimierung lohnt oder nicht, hängt von den relativen Kosten der Zuweisung / Freigabe im Vergleich zu den Kosten für die Berechnung / Mutation der Werte ab.

Benchmark

Spielen wir mit den Werten von vecSizeund numIter. Wir werden vecSize * numIter konstant halten, so dass "theoretisch" dieselbe Zeit benötigt wird (= es gibt dieselbe Anzahl von Zuweisungen und Ergänzungen mit genau denselben Werten) und der Zeitunterschied nur aus den Kosten von resultieren kann Zuweisungen, Freigaben und bessere Verwendung des Cache.

Verwenden wir insbesondere vecSize * numIter = 2 ^ 31 = 2147483648, da ich 16 GB RAM habe und diese Nummer sicherstellt, dass nicht mehr als 8 GB zugewiesen werden (sizeof (int) = 4), um sicherzustellen, dass ich nicht auf die Festplatte wechsle ( Alle anderen Programme waren geschlossen, ich hatte ~ 15 GB zur Verfügung, als ich den Test ausführte.

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 bei 4,20 GHz; 16 GB DDR4 2400 MHz; Kubuntu 18.04)

Notation: mem (v) = v.size () * sizeof (int) = v.size () * 4 auf meiner Plattform.

Es überrascht nicht, wann numIter = 1 die Zeiten (dh mem (v) = 8 GB), vollkommen identisch sind. In beiden Fällen weisen wir nur einmal einen riesigen Vektor von 8 GB Speicher zu. Dies beweist auch, dass bei Verwendung von BuildLargeVector1 () keine Kopie stattgefunden hat: Ich hätte nicht genug RAM, um die Kopie zu erstellen!

Wann numIter = 2 Wiederverwendung der Vektorkapazität anstelle der erneuten Zuweisung eines zweiten Vektors 1,37-mal schneller ist.

Wenn die numIter = 256Wiederverwendung der Vektorkapazität (anstatt einen Vektor 256 Mal immer wieder zuzuweisen / freizugeben ...) 2,45x schneller ist :)

Wir können feststellen , dass time1 ziemlich konstant ist , von numIter = 1zu 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. Das Zuweisen eines großen Vektors mit 8 GB ist jedoch definitiv teurer als das Zuweisen eines Vektors mit 32 MB. Die Wiederverwendung der Kapazität des Vektors führt also zu Leistungssteigerungen.

Von numIter = 512(mem (v) = 16 MB) bis 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. Dies hat wahrscheinlich damit zu tun, dass die L3-Cache-Größe meines Prozessors 8 MB beträgt, sodass der Vektor so gut wie vollständig in den Cache passt. Ich erkläre nicht wirklich, warum der plötzliche Sprung von time1für mem (v) = 16 MB ist. Es scheint logischer, kurz danach zu geschehen, wenn mem (v) = 8 MB. Beachten Sie, dass an diesem Sweet Spot die Nichtwiederverwendung von Kapazität überraschenderweise etwas schneller ist! Ich erkläre das nicht wirklich.

Wenn numIter > 8Mes hässlich wird. Beide Methoden werden langsamer, aber die Rückgabe des Vektors nach Wert wird noch langsamer. Im schlimmsten Fall ist bei einem Vektor, der nur einen einzigen enthält int, die Wiederverwendungskapazität anstelle der Rückgabe nach Wert 3,3-mal schneller. Vermutlich liegt dies an den Fixkosten von malloc (), die zu dominieren beginnen.

Beachten Sie, wie die Kurve für Zeit2 glatter ist als die Kurve für Zeit1: Nicht nur die Wiederverwendung der Vektorkapazität ist im Allgemeinen schneller, sondern möglicherweise noch wichtiger, sie ist vorhersehbarer .

Beachten Sie auch, dass wir im Sweet Spot 2 Milliarden Additionen von 64-Bit-Ganzzahlen in ~ 0,5 Sekunden durchführen konnten, was auf einem 4,2-GHz-64-Bit-Prozessor durchaus optimal ist. Wir könnten es besser machen, indem wir die Berechnung parallelisieren, um alle 8 Kerne zu verwenden (der obige Test verwendet jeweils nur einen Kern, was ich durch erneutes Ausführen des Tests während der Überwachung der CPU-Auslastung überprüft habe). Die beste Leistung wird erzielt, wenn mem (v) = 16 kB ist, was der Größenordnung des L1-Cache entspricht (der L1-Datencache für den i7-7700K beträgt 4 x 32 kB).

Natürlich werden die Unterschiede immer weniger relevant, je mehr Berechnungen Sie tatsächlich für die Daten durchführen müssen. Unten sind die Ergebnisse, wenn wir ersetzen sum = std::accumulate(v.begin(), v.end(), sum);durch for (int k : v) sum += std::sqrt(2.0*k);:

Schlussfolgerungen

1. Die Verwendung von Ausgabeparametern anstelle der Rückgabe nach Wert kann zu Leistungssteigerungen führen, indem die Kapazität wiederverwendet wird.
2. Auf einem modernen Desktop-Computer scheint dies nur für große Vektoren (> 16 MB) und kleine Vektoren (<1 KB) zu gelten.
3. Vermeiden Sie die Zuweisung von Millionen / Milliarden kleiner Vektoren (<1 kB). Wenn möglich, verwenden Sie die Kapazität wieder oder, noch besser, gestalten Sie Ihre Architektur anders.

Die Ergebnisse können auf anderen Plattformen abweichen. Wenn es auf die Leistung ankommt, schreiben Sie wie gewohnt Benchmarks für Ihren speziellen Anwendungsfall.

Ich denke immer noch, dass es eine schlechte Praxis ist, aber es ist erwähnenswert, dass mein Team MSVC 2008 und GCC 4.1 verwendet, sodass wir nicht die neuesten Compiler verwenden.

Zuvor waren viele der in vtune mit MSVC 2008 angezeigten Hotspots auf das Kopieren von Zeichenfolgen zurückzuführen. Wir hatten Code wie diesen:

String Something::id() const
{
    return valid() ? m_id: "";
}

... beachten Sie, dass wir unseren eigenen String-Typ verwendet haben (dies war erforderlich, da wir ein Software-Entwicklungskit bereitstellen, in dem Plugin-Writer unterschiedliche Compiler und damit unterschiedliche, inkompatible Implementierungen von std :: string / std :: wstring verwenden können).

Ich habe eine einfache Änderung in Reaktion auf die Sitzung zur Erstellung von Stichprobenprofilen für Anrufdiagramme vorgenommen, die zeigt, dass String :: String (const String &) viel Zeit in Anspruch nimmt. Methoden wie im obigen Beispiel leisteten die größten Beiträge (tatsächlich zeigte die Profilerstellungssitzung, dass die Speicherzuweisung und -freigabe einer der größten Hotspots ist, wobei der String-Kopierkonstruktor der Hauptbeitrag für die Zuweisungen ist).

Die Änderung, die ich vorgenommen habe, war einfach:

static String null_string;
const String& Something::id() const
{
    return valid() ? m_id: null_string;
}

Dies machte jedoch einen großen Unterschied! Der Hotspot wurde in nachfolgenden Profiler-Sitzungen entfernt. Darüber hinaus führen wir zahlreiche gründliche Unit-Tests durch, um die Leistung unserer Anwendung zu verfolgen. Alle Arten von Leistungstestzeiten sind nach diesen einfachen Änderungen erheblich gesunken.

Fazit: Wir verwenden nicht die absolut neuesten Compiler, aber wir können uns immer noch nicht darauf verlassen, dass der Compiler das Kopieren für eine zuverlässige Rückgabe nach Wert optimiert (zumindest nicht in allen Fällen). Dies ist möglicherweise nicht der Fall für diejenigen, die neuere Compiler wie MSVC 2010 verwenden. Ich freue mich darauf, wenn wir C ++ 0x verwenden und einfach rvalue-Referenzen verwenden können und uns nie Sorgen machen müssen, dass wir unseren Code durch die Rückgabe von Komplex pessimieren Klassen nach Wert.

[Bearbeiten] Wie Nate betonte, gilt RVO für die Rückgabe von Temporären, die innerhalb einer Funktion erstellt wurden. In meinem Fall gab es keine solchen Provisorien (mit Ausnahme des ungültigen Zweigs, in dem wir eine leere Zeichenfolge erstellen), und daher wäre RVO nicht anwendbar gewesen.

Nur um ein wenig zu picken: In vielen Programmiersprachen ist es nicht üblich, Arrays von Funktionen zurückzugeben. In den meisten von ihnen wird ein Verweis auf ein Array zurückgegeben. In C ++ würde die nächste Analogie zurückkehrenboost::shared_array

Wenn die Leistung ein echtes Problem darstellt, sollten Sie sich darüber im Klaren sein, dass die Verschiebungssemantik nicht immer schneller ist als das Kopieren. Wenn Sie beispielsweise eine Zeichenfolge haben, die die Optimierung für kleine Zeichenfolgen verwendet, muss ein Verschiebungskonstruktor für kleine Zeichenfolgen genau so viel Arbeit leisten wie ein regulärer Kopierkonstruktor.