Pytanie Zwracanie wektora STL z funkcji - koszt kopiowania


Po zwróceniu wektora STL z funkcji:

vector<int> getLargeArray() {  ...  }

Czy powrót będzie kosztowną operacją kopiowania? Pamiętam, że gdzieś czytałem, że przypisanie wektora jest szybkie - czy powinienem wymagać od osoby dzwoniącej podania referencji?

void getLargeArray( vector<int>& vec ) {  ...  }

16
2017-09-26 14:48


pochodzenie


@Gareth Z wyjątkiem gdy jesteś w C ++ 11, gdzie zwracanie wektora z funkcji jest gwarantowane być szybkim według standardu (oprócz optymalizacji wartości zwracanej, nawet w wielu przypadkach, szybko w pre-C ++ 11, ale OK, to zależy od implementacji i sytuacji). - Christian Rau
Ten post może być interesujący: cpp-next.com/archive/2009/08/want-speed-pass-by-value - Gareth


Odpowiedzi:


Zakładając, że twoja funkcja konstruuje i zwraca nowe dane, powinieneś zwrócić wartość i spróbować upewnić się, że sama funkcja ma jeden punkt powrotu, który zwraca zmienną typu vector<int>lub w najgorszym przypadku kilka punktów zwrotu, które wszystkie zwracają tę samą zmienną.

Zapewnia to otrzymanie nazwanej optymalizacji wartości zwracanej na dowolnym wiarygodnym kompilatorze, który eliminuje jeden potencjalnych kopii (tej z wartości w funkcji, do wartości zwracanej). Istnieją inne sposoby na uzyskanie optymalizacji wartości zwracanej, ale nie jest ona w pełni przewidywalna, więc prosta reguła jest bezpieczna.

Następnie chcesz wyeliminować potencjalną kopię z wartości zwracanej do tego, co wywołuje użytkownik. Jest to problem, z którym należy się połączyć, a nie adresata, i są na to trzy sposoby:

  • Użyj wywołania funkcji jako inicjalizatora dla a vector<int>, w takim przypadku ponownie każdy wiarygodny kompilator C ++ będzie przesuwał kopię.
  • Użyj C ++ 11, gdzie vector ma semantykę ruchu.
  • W C ++ 03 użyj "swaptimization".

Tak jest w C ++ 03 nie rób tego pisać

vector<int> v;
// use v for some stuff
// ...
// now I want fresh data in v:
v = getLargeArray();

Zamiast:

getLargeArray().swap(v);

W ten sposób unika się przypisania kopii, które jest wymagane (nie można z niego zrezygnować [*]) v = getLargeArray(). Nie jest to konieczne w C ++ 11, gdzie zamiast kosztownego zadania kopiowania istnieje tanie polecenie przeniesienia, ale oczywiście nadal działa.

Kolejną kwestią do rozważenia jest to, czy faktycznie chcesz vector jako część twojego interfejsu. Zamiast tego możesz napisać szablon funkcji, który pobiera iterator wyjścia, i zapisuje dane do tego wyjściowego iteratora. Dzwoniący, którzy chcą danych w wektorze, mogą następnie przekazać wynik std::back_inserter, podobnie jak osoby dzwoniące, które chcą danych w formacie deque lub list. Dzwoniący, którzy wcześniej znają wielkość danych, mogli nawet przejść tylko iteratory wektorowe (odpowiednio resize()d pierwszy) lub surowy wskaźnik do wystarczająco dużej tablicy, aby uniknąć narzutu back_insert_iterator. Istnieją nie-szablonowe sposoby robienia tego samego, ale najprawdopodobniej poniosą koszty w taki czy inny sposób. Jeśli martwisz się kosztem kopiowania int za element, a następnie martwisz się o koszt wywołania funkcji na element.

Jeśli twoja funkcja nie tworzy i zwraca nowe dane, to raczej zwraca bieżącą zawartość niektórych istniejących vector<int> i nie wolno zmieniać oryginału, nie można uniknąć co najmniej jednej kopii po zwróceniu przez wartość. Więc jeśli wydajność tego jest sprawdzonym problemem, musisz spojrzeć na API inne niż wartość zwracana przez wartość. Na przykład możesz podać parę iteratorów, które mogą być używane do przechodzenia przez wewnętrzne dane, funkcję wyszukiwania wartości w wektorze według indeksu lub nawet (jeśli problem z wydajnością jest tak poważny, że uzasadnia ujawnienie twoich wnętrz), odniesienie do wektora. Oczywiście we wszystkich tych przypadkach zmienia się znaczenie funkcji - teraz zamiast podawać dzwoniącemu "własne dane", zapewnia on widok danych innych osób, które mogą ulec zmianie.

[*] oczywiście nadal obowiązuje zasada "jak gdyby" i można sobie wyobrazić implementację C ++, która jest wystarczająco inteligentna, aby zdać sobie z tego sprawę, ponieważ jest to wektor trywialnie kopiowalnego typu (int), a ponieważ nie wziąłeś żadnych wskaźników do żadnych elementów (zakładam), to może zamiast tego zamienić, a wynik jest "jak gdyby" skopiowany. Ale nie będę na to liczył.


22
2017-09-26 15:00





Jesteś bardzo prawdopodobny optymalizacja wartości zwracanej, w zależności od struktury ciała funkcji. W C ++ 11 możesz również skorzystać z semantyki ruchu. Wracając do wartości z pewnością ma czystszą semantykę i uważam to za preferowaną opcję, chyba że profilowanie dowodzi, że jest to kosztowne. Istnieje dobry artykuł pokrewny tutaj.

Oto mały przykład z obszerną klasą manekina, skompilowaną bez obsługi optymalizacji lub C ++ 11, przy użyciu starej wersji GCC (4.3.4):

#include <vector>
#include <iostream>
struct Foo
{
  Foo() { std::cout << "Foo()\n"; }
  Foo(const Foo&) { std::cout << "Foo copy\n"; }
  Foo& operator=(const Foo&) { 
    std::cout << "Foo assignment\n"; 
    return *this;
  }
};

std::vector<Foo> makeFoos()
{
  std::vector<Foo> tmp;
  tmp.push_back(Foo());
  std::cout << "returning\n";
  return tmp;
}

int main()
{
  std::vector<Foo> foos = makeFoos();
}

Rezultatem na mojej platformie jest to, że całe kopiowanie odbywa się przed powrotem funkcji. Jeśli skompiluję z obsługą C ++ 11, to push_back daje kopię ruchu zamiast konstrukcji kopii C ++ 03.


10
2017-09-26 14:51



W rzeczywistości bardzo prawdopodobne jest, że otrzymasz RVO, jeśli zawsze zwrócisz ten sam wektor ... - ltjax
@ltjax tak, to wchodzi w "strukturę ciała funkcji". Ponieważ nie jest napisany w standardzie, nie chciałem zbytnio się rozwodzić. - juanchopanza