Wersja skrócona: w wielu językach programowania często zwraca się duże obiekty - takie jak wektory / tablice -. Czy ten styl jest teraz akceptowalny w C ++ 0x, jeśli klasa ma konstruktor ruchu, czy programiści C ++ uważają go za dziwny / brzydki / obrzydliwy?

Wersja długa: czy w C ++ 0x jest to nadal uważane za złą formę?

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

Tradycyjna wersja wyglądałaby tak:

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

W nowszej wersji wartością zwracaną z BuildLargeVectorjest rvalue, więc v zostałoby skonstruowane przy użyciu konstruktora przenoszenia std::vector, przy założeniu, że (N) RVO nie ma miejsca.

Nawet przed C ++ 0x pierwsza postać często byłaby „wydajna” z powodu (N) RVO. Jednak (N) RVO zależy od uznania kompilatora. Teraz, gdy mamy odniesienia do rvalue, gwarantujemy, że nie nastąpi głębokie kopiowanie.

Edycja : Pytanie tak naprawdę nie dotyczy optymalizacji. Obie przedstawione formy mają prawie identyczną wydajność w rzeczywistych programach. Podczas gdy w przeszłości pierwsza forma mogła mieć gorsze wyniki o rząd wielkości. W rezultacie pierwsza forma przez długi czas była głównym powodem zapachu kodu w programowaniu w C ++. Już nie, mam nadzieję?

Dave Abrahams przeprowadził dość wszechstronną analizę szybkości przekazywania / zwracania wartości .

Krótka odpowiedź, jeśli chcesz zwrócić wartość, zwróć wartość. Nie używaj referencji wyjściowych, ponieważ kompilator i tak to robi. Oczywiście są zastrzeżenia, więc powinieneś przeczytać ten artykuł.

Przynajmniej IMO, to zwykle kiepski pomysł, ale nie ze względu na wydajność. To kiepski pomysł, ponieważ omawiana funkcja powinna być zwykle zapisana jako ogólny algorytm, który generuje dane wyjściowe za pośrednictwem iteratora. Prawie każdy kod, który akceptuje lub zwraca kontener zamiast działać na iteratorach, powinien zostać uznany za podejrzany.

Nie zrozum mnie źle: czasami ma sens przekazywanie obiektów typu kolekcji (np. Ciągów znaków), ale w przytoczonym przykładzie uważam, że przekazanie lub zwrócenie wektora jest kiepskim pomysłem.

Istota jest taka:

Kopiuj Elision i RVO mogą uniknąć "przerażających kopii" (kompilator nie jest wymagany do implementacji tych optymalizacji, aw niektórych sytuacjach nie można go zastosować)

Odwołania C ++ 0x RValue pozwalają na implementacje ciągów / wektorów, które to gwarantują .

Jeśli możesz porzucić starsze kompilatory / implementacje STL, zwróć wektory swobodnie (i upewnij się, że twoje własne obiekty również je obsługują). Jeśli twój kod musi obsługiwać "mniejsze" kompilatory, trzymaj się starego stylu.

Niestety ma to duży wpływ na twoje interfejsy. Jeśli C ++ 0x nie jest opcją i potrzebujesz gwarancji, w niektórych scenariuszach możesz zamiast tego użyć obiektów liczonych jako odwołania lub kopiowanych przy zapisie. Mają jednak wady związane z wielowątkowością.

(Chciałbym, żeby tylko jedna odpowiedź w C ++ była prosta, nieskomplikowana i bezwarunkowa).

Rzeczywiście, od C ++ 11, koszt kopiowaniastd::vector zniknął w większości przypadków.

Należy jednak pamiętać, że koszt skonstruowania nowego wektora (a następnie zniszczenia go) nadal istnieje, a użycie parametrów wyjściowych zamiast zwracania wartości według wartości jest nadal przydatne, gdy chcesz ponownie wykorzystać pojemność wektora. Jest to udokumentowane jako wyjątek w F.20 podstawowych wytycznych C ++.

Porównajmy:

std::vector<int> BuildLargeVector1(size_t vecSize) {
    return std::vector<int>(vecSize, 1);
}

z:

void BuildLargeVector2(/*out*/ std::vector<int>& v, size_t vecSize) {
    v.assign(vecSize, 1);
}

Załóżmy teraz, że musimy wywołać te metody numIterrazy w ścisłej pętli i wykonać jakąś akcję. Na przykład obliczmy sumę wszystkich elementów.

Używając BuildLargeVector1, zrobiłbyś:

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

Używając BuildLargeVector2, zrobiłbyś:

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

W pierwszym przykładzie występuje wiele niepotrzebnych dynamicznych alokacji / zwalniania alokacji, którym zapobiega się w drugim przykładzie poprzez użycie parametru wyjściowego w stary sposób, ponownie wykorzystując już przydzieloną pamięć. To, czy ta optymalizacja jest warta wykonania, zależy od względnego kosztu alokacji / cofnięcia alokacji w porównaniu z kosztem obliczania / mutowania wartości.

Reper

Pobawmy się wartościami vecSizei numIter. Zachowamy stałą vecSize * numIter, aby "w teorii" zajęło to tyle samo czasu (= jest taka sama liczba przypisań i dodatków, z dokładnie tymi samymi wartościami), a różnica czasu może pochodzić tylko z kosztu alokacje, cofanie przydziałów i lepsze wykorzystanie pamięci podręcznej.

Mówiąc dokładniej, użyjmy vecSize * numIter = 2 ^ 31 = 2147483648, ponieważ mam 16 GB pamięci RAM i ta liczba zapewnia, że ​​przydzielono nie więcej niż 8 GB (sizeof (int) = 4), zapewniając, że nie przełączam się na dysk ( wszystkie inne programy były zamknięte, podczas testu miałem ~ 15 GB wolnego miejsca).

Oto kod:

#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;
}

A oto wynik:

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

Notacja: mem (v) = v.size () * sizeof (int) = v.size () * 4 na mojej platformie.

Nic dziwnego, że gdy numIter = 1(tj. Mem (v) = 8 GB), czasy są idealnie identyczne. Rzeczywiście, w obu przypadkach przydzielamy tylko raz ogromny wektor o wielkości 8 GB w pamięci. Dowodzi to również, że żadna kopia się nie wydarzyła podczas korzystania z BuildLargeVector1 (): nie miałbym wystarczająco dużo pamięci RAM, aby wykonać kopię!

Kiedy numIter = 2ponowne wykorzystanie pojemności wektora zamiast ponownego przydzielania drugiego wektora jest 1,37x szybsze.

Kiedy numIter = 256ponowne użycie pojemności wektora (zamiast przydzielania / cofania alokacji wektora w kółko 256 razy ...) jest 2,45x szybsze :)

Możemy zauważyć, że czas1 jest prawie stały od numIter = 1do numIter = 256, co oznacza, że ​​przydzielenie jednego ogromnego wektora o wielkości 8 GB jest prawie tak samo kosztowne, jak przydzielenie 256 wektorów o pojemności 32 MB. Jednak przydzielenie jednego ogromnego wektora o wielkości 8 GB jest zdecydowanie droższe niż przydzielenie jednego wektora o wielkości 32 MB, więc ponowne wykorzystanie pojemności wektora zapewnia wzrost wydajności.

Od numIter = 512(mem (v) = 16MB) do numIter = 8M(mem (v) = 1kB) to najlepszy punkt: obie metody są dokładnie tak samo szybkie i szybsze niż wszystkie inne kombinacje numIter i vecSize. Prawdopodobnie ma to związek z faktem, że rozmiar pamięci podręcznej L3 mojego procesora wynosi 8 MB, więc wektor prawie całkowicie mieści się w pamięci podręcznej. Naprawdę nie wyjaśniam, dlaczego nagły skok time1dotyczy mem (v) = 16 MB, wydaje się, że bardziej logiczne byłoby zdarzenie zaraz po, gdy mem (v) = 8 MB. Zwróć uwagę, że, co zaskakujące, w tym słodkim miejscu, brak możliwości ponownego wykorzystania jest w rzeczywistości nieco szybszy! Naprawdę tego nie wyjaśniam.

Kiedy numIter > 8Mrobi się brzydko. Obie metody działają wolniej, ale zwracanie wektora według wartości jest jeszcze wolniejsze. W najgorszym przypadku, gdy wektor zawiera tylko jeden pojedynczy int, ponowne użycie pojemności zamiast zwracania wartości jest 3,3 razy szybsze. Przypuszczalnie wynika to ze stałych kosztów malloc (), które zaczynają dominować.

Zwróć uwagę, że krzywa dla czasu2 jest gładsza niż krzywa dla czasu1: nie tylko ponowne wykorzystanie pojemności wektorów jest generalnie szybsze, ale co ważniejsze, jest bardziej przewidywalne .

Zwróć również uwagę, że w najlepszym miejscu byliśmy w stanie wykonać 2 miliardy dodań 64-bitowych liczb całkowitych w ~ 0,5 s, co jest całkiem optymalne na 64-bitowym procesorze 4,2 GHz. Moglibyśmy zrobić lepiej, zrównoleglenie obliczeń w celu wykorzystania wszystkich 8 rdzeni (powyższy test wykorzystuje tylko jeden rdzeń na raz, co zweryfikowałem, ponownie uruchamiając test podczas monitorowania użycia procesora). Najlepszą wydajność osiąga się, gdy mem (v) = 16kB, co jest rzędem wielkości pamięci podręcznej L1 (pamięć podręczna danych L1 dla i7-7700K to 4x32kB).

Oczywiście różnice stają się coraz mniej istotne, im więcej obliczeń trzeba wykonać na danych. Poniżej znajdują się wyniki jeśli zastąpimy sum = std::accumulate(v.begin(), v.end(), sum);przez for (int k : v) sum += std::sqrt(2.0*k);:

Wnioski

1. Użycie parametrów wyjściowych zamiast zwracania wartości według wartości może zapewnić wzrost wydajności poprzez ponowne wykorzystanie pojemności.
2. Na nowoczesnym komputerze stacjonarnym wydaje się to mieć zastosowanie tylko do dużych wektorów (> 16 MB) i małych wektorów (<1 kB).
3. Unikaj przydzielania milionów / miliardów małych wektorów (<1kB). Jeśli to możliwe, ponownie wykorzystaj pojemność lub jeszcze lepiej zaprojektuj architekturę w inny sposób.

Wyniki mogą się różnić na innych platformach. Jak zwykle, jeśli liczy się wydajność, napisz testy porównawcze dla konkretnego przypadku użycia.

Nadal uważam, że to zła praktyka, ale warto zauważyć, że mój zespół korzysta z MSVC 2008 i GCC 4.1, więc nie używamy najnowszych kompilatorów.

Wcześniej wiele hotspotów wyświetlanych w vtune z MSVC 2008 sprowadzało się do kopiowania ciągów. Mieliśmy taki kod:

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

... zauważ, że użyliśmy naszego własnego typu String (było to wymagane, ponieważ dostarczamy zestaw programistyczny, w którym twórcy wtyczek mogą używać różnych kompilatorów, a tym samym różnych, niekompatybilnych implementacji std :: string / std :: wstring).

Wprowadziłem prostą zmianę w odpowiedzi na sesję profilowania próbkowania wykresu wywołań pokazującą, że String :: String (const String &) zajmuje znaczną ilość czasu. Metody takie jak w powyższym przykładzie były największymi współtwórcami (w rzeczywistości sesja profilowania wykazała, że ​​alokacja i cofanie alokacji pamięci jest jednym z największych hotspotów, a konstruktor kopiujący String był głównym współtwórcą alokacji).

Zmiana, którą wprowadziłem, była prosta:

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

Jednak to zrobiło wielką różnicę! Hotspot zniknął w kolejnych sesjach profilera, a oprócz tego wykonujemy wiele dokładnych testów jednostkowych, aby śledzić wydajność naszej aplikacji. Po tych prostych zmianach czasy testów wydajności wszelkiego rodzaju znacznie się skróciły.

Wniosek: nie używamy absolutnie najnowszych kompilatorów, ale nadal nie możemy polegać na kompilatorze optymalizującym kopiowanie w celu niezawodnego zwracania przez wartość (przynajmniej nie we wszystkich przypadkach). Może tak nie być w przypadku tych, którzy używają nowszych kompilatorów, takich jak MSVC 2010. Nie mogę się doczekać, kiedy będziemy mogli użyć C ++ 0x i po prostu użyć referencji rvalue i nigdy nie będziemy musieli się martwić, że pesymizujemy nasz kod, zwracając złożone klasy według wartości.

[Edytuj] Jak zauważył Nate, RVO dotyczy zwracania tymczasowych utworzonych wewnątrz funkcji. W moim przypadku nie było takich tymczasowych (poza nieprawidłową gałęzią, w której konstruujemy pusty ciąg), a zatem RVO nie miałby zastosowania.

Żeby trochę poszukać: w wielu językach programowania nie jest powszechne zwracanie tablic z funkcji. W większości z nich zwracane jest odwołanie do tablicy. W C ++ powracałaby najbliższa analogiaboost::shared_array

Jeśli wydajność jest prawdziwym problemem, powinieneś zdać sobie sprawę, że semantyka przenoszenia nie zawsze jest szybsza niż kopiowanie. Na przykład, jeśli masz ciąg, który używa optymalizacji małych ciągów, wówczas dla małych ciągów konstruktor przenoszenia musi wykonać dokładnie taką samą pracę, jak zwykły konstruktor kopiujący.