Действительно, начиная с C ++ 11, стоимость копирования std::vector в большинстве случаев исчезла.
Однако следует иметь в виду, что стоимость создание нового вектора (тогда разрушение его) все еще существует, и использование выходных параметров вместо возврата по значению все еще полезно, когда вы хотите повторно использовать емкость вектора.Это задокументировано как исключение в F.20 Основных руководящих принципов C ++.
Давайте сравним:
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);
}
Теперь предположим, что нам нужно вызвать эти методы numIter раз в узком цикле и выполнить какое-то действие.Например, давайте вычислим сумму всех элементов.
Используя BuildLargeVector1, вы сделаете:
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);
}
Используя BuildLargeVector2, вы сделаете:
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);
}
В первом примере происходит много ненужных динамических распределений / освобождений, которые предотвращаются во втором примере путем использования выходного параметра по-старому, повторного использования уже выделенной памяти.Стоит ли проводить эту оптимизацию, зависит от относительной стоимости выделения / освобождения по сравнению со стоимостью вычисления / изменения значений.
Тест
Давайте поиграем со значениями vecSize и numIter.Мы будем сохранять постоянную vecSize * numIter, чтобы «теоретически» это заняло одинаковое время (= одинаковое количество назначений и дополнений с одинаковыми значениями), а разница во времени может быть получена только из стоимостираспределение, освобождение и лучшее использование кэша.
В частности, давайте использовать vecSize * numIter = 2 ^ 31 = 2147483648, потому что у меня 16 ГБ ОЗУ, и это число гарантирует, что выделено не более 8 ГБ (sizeof(int) = 4), гарантируя, что я не подменяюсь на диск (все другие программы были закрыты, у меня было ~ 15 Гбайт при выполнении теста).
Вот код:
#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;
}
И вот результат:
$ 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 ГГц; 16 ГБ DDR4 2400 МГц; Kubuntu 18.04)
Обозначение: mem (v) = v.size () * sizeof (int) = v.size () * 4 на моей платформе.
Не удивительно, когда numIter = 1 (т.е.mem (v) = 8GB), время абсолютно идентично.Действительно, в обоих случаях мы выделяем только один огромный вектор в 8 ГБ памяти.Это также доказывает, что при использовании BuildLargeVector1 () копирование не происходило: у меня не хватило бы оперативной памяти для копирования!
Когда numIter = 2, повторное использование емкости вектора вместо перераспределения второго вектора составляет 1,37.х быстрее.
Когда numIter = 256, повторное использование емкости вектора (вместо выделения / освобождения вектора снова и снова 256 раз ...) в 2,45 раза быстрее :)
Мы можемобратите внимание, что время1 в значительной степени постоянно от numIter = 1 до numIter = 256, что означает, что выделение одного огромного вектора размером 8 ГБ обходится так же дорого, как выделение 256 векторов по 32 МБ.Однако выделение одного огромного вектора из 8 ГБ определенно дороже, чем выделение одного вектора из 32 МБ, поэтому повторное использование емкости вектора обеспечивает повышение производительности.
С numIter = 512 (mem (v) = 16 МБ) до numIter = 8M(mem (v) = 1kB) - самое приятное: оба метода работают так же быстро и быстрее, чем все другие комбинации numIter и vecSize.Это, вероятно, связано с тем, что размер кэша L3 моего процессора составляет 8 МБ, поэтому вектор почти полностью помещается в кэш.Я действительно не объясняю, почему внезапный скачок time1 для mem (v) = 16 МБ, было бы более логичным произойти сразу после, когда mem (v) = 8 МБ.Обратите внимание, что на удивление, в этом приятном месте, не повторное использование емкости на самом деле немного быстрее!Я не очень-то это объясняю.
Когда numIter > 8M вещи начинают становиться ужасными.Оба метода становятся медленнее, но возвращение вектора по значению становится еще медленнее.В худшем случае, когда вектор содержит только один int, повторное использование емкости вместо возврата по значению происходит в 3,3 раза быстрее.Предположительно, это связано с постоянными издержками malloc (), которые начинают доминировать.
Обратите внимание, что кривая для времени2 более плавная, чем кривая для времени1: не только повторное использование векторной емкости обычно быстрее, но, что еще важнее, она более предсказуемая .
Также обратите внимание, что в приятной ситуации мы смогли выполнить 2 миллиарда сложений 64-битных целых чисел за ~ 0,5 с, что вполне оптимально для 64-битного процессора с частотой 4,2 ГГц. Мы могли бы добиться большего успеха, распараллеливая вычисления, чтобы использовать все 8 ядер (в приведенном выше тесте используется только одно ядро за раз, что я подтвердил, повторно выполнив тест при мониторинге загрузки ЦП). Наилучшая производительность достигается, когда mem (v) = 16 КБ, что является порядком величины кэша L1 (кэш данных L1 для i7-7700K равен 4x32 КБ).
Конечно, различия становятся все менее и менее значимыми, чем больше вычислений вы должны сделать для данных. Ниже приведены результаты, если мы заменим sum = std::accumulate(v.begin(), v.end(), sum); на for (int k : v) sum += std::sqrt(2.0*k);:
Выводы
- Использование выходных параметров вместо возврата по значению может обеспечить повышение производительности за счет повторного использования емкости.
- На современном настольном компьютере это применимо только к большим векторам (> 16 МБ) и маленьким векторам (<1 кБ). </li>
- Избегайте выделения миллионов / миллиардов маленьких векторов (<1 КБ). Если возможно, повторно используйте емкость или, что еще лучше, спроектируйте свою архитектуру иначе. </li>
Результаты могут отличаться на других платформах. Как обычно, если производительность имеет значение, напишите тесты для вашего конкретного случая использования.