Wydajny sposób na zwrócenie std :: vector w języku C ++

108

Ile danych jest kopiowanych, podczas zwracania std :: vector w funkcji i jak duża będzie optymalizacja, aby umieścić std :: vector w wolnym magazynie (na stercie) i zamiast tego zwrócić wskaźnik, tj. Jest:

std::vector *f()
{
  std::vector *result = new std::vector();
  /*
    Insert elements into result
  */
  return result;
} 

bardziej wydajny niż:

std::vector f()
{
  std::vector result;
  /*
    Insert elements into result
  */
  return result;
} 

?

Morten
źródło
4
Co powiesz na przekazanie wektora przez odniesienie, a następnie wypełnienie go w środku f?
Kiril Kirov,
4
RVO to dość podstawowa optymalizacja, którą większość kompilatorów będzie w stanie wykonać w dowolnym momencie.
Remus Rusanu
W miarę napływu odpowiedzi może pomóc ci wyjaśnić, czy używasz C ++ 03 czy C ++ 11. Najlepsze praktyki między dwiema wersjami są bardzo różne.
Drew Dormann
@Kiril Kirov, Czy mogę to zrobić bez umieszczania tego na liście argumentów funkcji, tj. void f (std :: vector & result)?
Morten

Odpowiedzi:

141

W C ++ 11 jest to preferowany sposób:

std::vector<X> f();

Oznacza to, że zwraca wartość.

W C ++ 11 std::vectorma semantykę ruchu, co oznacza, że lokalny wektor zadeklarowany w funkcji zostanie przeniesiony po powrocie, aw niektórych przypadkach kompilator może wyeliminować nawet ruch.

Nawaz
źródło
13
@LeonidVolnitsky: Tak, jeśli jest lokalny . W rzeczywistości return std::move(v);wyłączy ruch-elizję, nawet jeśli było to możliwe z just return v;. Więc to drugie jest preferowane.
Nawaz
1
@juanchopanza: Nie sądzę. Przed C ++ 11 można było argumentować przeciwko temu, ponieważ wektor nie zostanie przeniesiony; a RVO jest zależne od kompilatora! Porozmawiaj o rzeczach z lat 80-tych i 90-tych.
Nawaz
2
Moje rozumienie wartości zwracanej (według wartości) jest następujące: zamiast `` przeniesiono '' wartość zwracana w wywoływanym jest tworzona na stosie wywołującego, więc wszystkie operacje w wywoływanym są na miejscu, nie ma nic do przeniesienia w RVO . Czy to jest poprawne?
r0ng
2
@ r0ng: Tak, to prawda. W ten sposób kompilatory zwykle implementują RVO.
Nawaz,
1
@Nawaz To nie jest. Nie ma już nawet ruchu.
Wyścigi lekkości na orbicie,
71

Powinieneś zwrócić według wartości.

Standard ma specyficzną funkcję poprawiającą efektywność zwrotu wartości. Nazywa się to „elizją kopiowania”, a dokładniej w tym przypadku „nazwaną optymalizacją wartości zwracanej (NRVO)”.

Kompilatory nie muszą tego implementować, ale z drugiej strony kompilatory nie muszą implementować funkcji inlining (ani w ogóle wykonywać jakiejkolwiek optymalizacji). Ale wydajność standardowych bibliotek może być dość słaba, jeśli kompilatory nie optymalizują, a wszystkie poważne kompilatory implementują inlining i NRVO (i inne optymalizacje).

Po zastosowaniu NRVO nie będzie kopiowania w następującym kodzie:

std::vector<int> f() {
    std::vector<int> result;
    ... populate the vector ...
    return result;
}

std::vector<int> myvec = f();

Ale użytkownik może chcieć to zrobić:

std::vector<int> myvec;
... some time later ...
myvec = f();

Opcja Copy Elision nie zapobiega tutaj kopiowaniu, ponieważ jest to raczej przypisanie niż inicjalizacja. Jednak nadal powinieneś zwracać według wartości. W C ++ 11 przypisanie jest optymalizowane przez coś innego, zwanego „semantyką ruchu”. W C ++ 03 powyższy kod powoduje kopiowanie i chociaż teoretycznie optymalizator mógłby tego uniknąć, w praktyce jest to zbyt trudne. Więc zamiast tego myvec = f()w C ++ 03 powinieneś napisać to:

std::vector<int> myvec;
... some time later ...
f().swap(myvec);

Jest jeszcze jedna opcja, która ma zaoferować użytkownikowi bardziej elastyczny interfejs:

template <typename OutputIterator> void f(OutputIterator it) {
    ... write elements to the iterator like this ...
    *it++ = 0;
    *it++ = 1;
}

Następnie możesz również obsługiwać istniejący interfejs oparty na wektorach:

std::vector<int> f() {
    std::vector<int> result;
    f(std::back_inserter(result));
    return result;
}

Może to być mniej wydajne niż istniejący kod, jeśli istniejący kod używa reserve()w sposób bardziej złożony niż tylko ustalona z góry kwota. Ale jeśli twój istniejący kod w zasadzie push_backwielokrotnie odwołuje się do wektora, to ten oparty na szablonie kod powinien być równie dobry.

Steve Jessop
źródło
Głosowano za naprawdę najlepszą i szczegółową odpowiedzią. Jednak w wariancie swap () ( dla C ++ 03 bez NRVO ) nadal będziesz mieć jedną kopię konstruktora kopiującego utworzoną wewnątrz f (): z wyniku zmiennej do ukrytego obiektu tymczasowego, który w końcu zostanie zamieniony na myvec .
JenyaKh
@JenyaKh: jasne, to jest problem z jakością wdrożenia. Standard nie wymagał implementacji NRVO w implementacjach C ++ 03, tak jak nie wymagał wbudowywania funkcji. Różnica w stosunku do funkcji inlining polega na tym, że inlining nie zmienia semantyki ani programu, podczas gdy NRVO tak. Kod przenośny musi działać z NRVO lub bez niego. Zoptymalizowany kod dla konkretnej implementacji (i poszczególnych flag kompilatora) może szukać gwarancji dotyczących NRVO we własnej dokumentacji implementacji.
Steve Jessop
3

Czas zamieścić odpowiedź na temat RVO , ja też ...

Jeśli zwracasz obiekt według wartości, kompilator często optymalizuje to, aby nie był konstruowany dwukrotnie, ponieważ zbędne jest konstruowanie go w funkcji jako tymczasowego, a następnie kopiowanie. Nazywa się to optymalizacją wartości zwracanych: utworzony obiekt zostanie przeniesiony zamiast kopiowania.


źródło
1

Popularnym idiomem sprzed C ++ 11 jest przekazanie referencji do wypełnianego obiektu.

Wtedy nie ma kopiowania wektora.

void f( std::vector & result )
{
  /*
    Insert elements into result
  */
} 
Drew Dormann
źródło
3
To już nie jest idiom w C ++ 11.
Nawaz
1
@Nawaz Zgadzam się. Nie jestem pewien, jakie są teraz najlepsze praktyki w SO w odniesieniu do pytań dotyczących C ++, ale nie konkretnie C ++ 11. Podejrzewam, że powinienem być skłonny do udzielania odpowiedzi w C ++ 11 studentowi, C ++ 03 odpowiada komuś zagłębionego w kod produkcyjny. Masz opinię?
Drew Dormann
7
Właściwie po wydaniu C ++ 11 (który ma 19 miesięcy) uważam, że każde pytanie jest pytaniem C ++ 11, chyba że wyraźnie określono, że jest to pytanie C ++ 03.
Nawaz
1

Jeśli kompilator obsługuje Named Return Value Optimization ( http://msdn.microsoft.com/en-us/library/ms364057(v=vs.80).aspx ), możesz bezpośrednio zwrócić wektor pod warunkiem, że nie ma:

  1. Różne ścieżki zwracające różne nazwane obiekty
  2. Wiele ścieżek zwrotnych (nawet jeśli ten sam nazwany obiekt jest zwracany na wszystkich ścieżkach) z wprowadzonymi stanami EH.
  3. Zwrócony nazwany obiekt odwołuje się do wbudowanego bloku asm.

NRVO optymalizuje nadmiarowy konstruktor kopiujący i wywołania destruktora, a tym samym poprawia ogólną wydajność.

W twoim przykładzie nie powinno być żadnych różnic.

taocp
źródło
0
vector<string> getseq(char * db_file)

A jeśli chcesz wydrukować to na main (), powinieneś to zrobić w pętli.

int main() {
     vector<string> str_vec = getseq(argv[1]);
     for(vector<string>::iterator it = str_vec.begin(); it != str_vec.end(); it++) {
         cout << *it << endl;
     }
}
Akash Kandpal
źródło
-2

Mimo że „zwracanie przez wartość” może być przyjemne, jest to rodzaj kodu, który może prowadzić do błędu. Rozważ następujący program:

    #include <string>
    #include <vector>
    #include <iostream>
    using namespace std;
    static std::vector<std::string> strings;
    std::vector<std::string> vecFunc(void) { return strings; };
    int main(int argc, char * argv[]){
      // set up the vector of strings to hold however
      // many strings the user provides on the command line
      for(int idx=1; (idx<argc); ++idx){
         strings.push_back(argv[idx]);
      }

      // now, iterate the strings and print them using the vector function
      // as accessor
      for(std::vector<std::string>::interator idx=vecFunc().begin(); (idx!=vecFunc().end()); ++idx){
         cout << "Addr: " << idx->c_str() << std::endl;
         cout << "Val:  " << *idx << std::endl;
      }
    return 0;
    };
  • P: Co się stanie, gdy powyższe zostanie wykonane? O: Coredump.
  • P: Dlaczego kompilator nie złapał błędu? O: Ponieważ program jest poprawny składniowo, choć nie semantycznie.
  • P: Co się stanie, jeśli zmodyfikujesz vecFunc (), aby zwrócić odwołanie? Odp .: Program działa do końca i daje oczekiwany wynik.
  • P: Jaka jest różnica? O: Kompilator nie musi tworzyć i zarządzać anonimowymi obiektami. Programista poinstruował kompilator, aby używał dokładnie jednego obiektu dla iteratora i do określenia punktu końcowego, a nie dwóch różnych obiektów, jak robi to uszkodzony przykład.

Powyższy błędny program nie wskaże żadnych błędów, nawet jeśli użyje się opcji raportowania GNU g ++ -Wall -Wextra -Weffc ++

Jeśli musisz podać wartość, to zamiast dwukrotnego wywołania vecFunc () zadziałałyby następujące czynności:

   std::vector<std::string> lclvec(vecFunc());
   for(std::vector<std::string>::iterator idx=lclvec.begin(); (idx!=lclvec.end()); ++idx)...

Powyższe również nie generuje żadnych anonimowych obiektów podczas iteracji pętli, ale wymaga możliwej operacji kopiowania (która, jak niektórzy zauważają, może zostać zoptymalizowana w pewnych okolicznościach. Ale metoda referencyjna gwarantuje, że żadna kopia nie zostanie utworzona. perform RVO nie zastąpi próby zbudowania najbardziej wydajnego kodu, jaki tylko możesz.Jeśli możesz podważyć potrzebę kompilatora do wykonania RVO, jesteś o krok do przodu.

Wuj wujka smoka
źródło
3
To jest raczej przykład tego, co może pójść źle, jeśli użytkownik nie jest ogólnie zaznajomiony z C ++. Ktoś, kto jest zaznajomiony z językami opartymi na obiektach, takimi jak .net lub javascript, prawdopodobnie założyłby, że wektor łańcuchowy jest zawsze przekazywany jako wskaźnik i dlatego w twoim przykładzie zawsze wskazywałby ten sam obiekt. vecfunc (). begin () i vecfunc (). end () niekoniecznie będą pasować w twoim przykładzie, ponieważ powinny być kopiami wektora łańcuchowego.
Medran
-2
   vector<string> func1() const
   {
      vector<string> parts;
      return vector<string>(parts.begin(),parts.end()) ;
   } 
Amruth A
źródło