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
- 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.
- Na nowoczesnym komputerze stacjonarnym wydaje się to mieć zastosowanie tylko do dużych wektorów (> 16 MB) i małych wektorów (<1 kB).
- 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.