В C++ все еще плохая практика возвращать вектор из функции?
Короткая версия: во многих языках программирования принято возвращать большие объекты, такие как векторы / массивы. Является ли этот стиль приемлемым в C++0x, если у класса есть конструктор перемещения, или программисты C++ считают его странным / уродливым / мерзким?
Длинная версия: В C++0x это все еще считается плохой формой?
std::vector<std::string> BuildLargeVector();
...
std::vector<std::string> v = BuildLargeVector();
Традиционная версия будет выглядеть так:
void BuildLargeVector(std::vector<std::string>& result);
...
std::vector<std::string> v;
BuildLargeVector(v);
В более новой версии значение возвращается из BuildLargeVector является значением r, поэтому v будет создан с использованием конструктора перемещения std::vectorпри условии (N)RVO не имеет места.
Даже до C++0x первая форма часто была бы "эффективной" из-за (N)RVO. Однако (N)RVO остается на усмотрение компилятора. Теперь, когда у нас есть ссылки на rvalue, мы гарантируем, что глубокого копирования не будет.
Изменить: Вопрос на самом деле не об оптимизации. Обе показанные формы имеют практически одинаковую производительность в реальных программах. В то время как в прошлом первая форма могла иметь на порядок худшую производительность. В результате первая форма долгое время была основным запахом кода в программировании на C++. Надеюсь, больше нет?
7 ответов
У Дейва Абрахамса есть довольно всесторонний анализ скорости передачи / возврата значений.
Короткий ответ: если вам нужно вернуть значение, верните значение. Не используйте выходные ссылки, потому что компилятор делает это в любом случае. Конечно, есть предостережения, поэтому вы должны прочитать эту статью.
По крайней мере, IMO, это обычно плохая идея, но не по соображениям эффективности. Это плохая идея, потому что рассматриваемая функция обычно должна быть написана как универсальный алгоритм, который выдает результат через итератор. Почти любой код, который принимает или возвращает контейнер вместо работы с итераторами, следует рассматривать как подозрительный.
Не поймите меня неправильно: бывают моменты, когда имеет смысл обойти объекты, подобные коллекциям (например, строки), но для приведенного примера я бы посоветовал передать или вернуть вектор плохая идея.
Суть это:
Copy Elision и RVO могут избежать "страшных копий" (компилятор не требуется для реализации этих оптимизаций, и в некоторых ситуациях он не может быть применен)
Ссылки C++ 0x RValue допускают реализации строк / векторов, которые гарантируют это.
Если вы можете отказаться от более старых реализаций компиляторов / STL, возвращайте векторы свободно (и убедитесь, что ваши собственные объекты тоже поддерживают это). Если ваша кодовая база должна поддерживать "меньшие" компиляторы, придерживайтесь старого стиля.
К сожалению, это имеет большое влияние на ваши интерфейсы. Если C++ 0x не является опцией, и вам нужны гарантии, вы можете использовать вместо этого объекты со счетчиком ссылок или копирование при записи в некоторых сценариях. У них есть и недостатки с многопоточностью.
(Я бы хотел, чтобы только один ответ на C++ был простым и понятным и без условий).
Действительно, начиная с 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) = 8 ГБ), время абсолютно идентично. Действительно, в обоих случаях мы выделяем только один огромный вектор в 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(), которые начинают доминировать.
Обратите внимание, что кривая для time2 более гладкая, чем кривая для time1: не только повторное использование векторной емкости обычно быстрее, но, что еще важнее, она более предсказуема.
Также обратите внимание, что в приятной ситуации мы смогли выполнить 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 КБ).
- Избегайте выделения миллионов / миллиардов маленьких векторов (<1 кБ). Если возможно, повторно используйте емкость или, что еще лучше, спроектируйте свою архитектуру по-другому.
Результаты могут отличаться на других платформах. Как обычно, если производительность имеет значение, напишите тесты для вашего конкретного случая использования.
Я все еще думаю, что это плохая практика, но стоит отметить, что моя команда использует MSVC 2008 и GCC 4.1, поэтому мы не используем последние компиляторы.
Ранее многие горячие точки, показанные в vtune с MSVC 2008, сводились к копированию строк. У нас был такой код:
String Something::id() const
{
return valid() ? m_id: "";
}
... обратите внимание, что мы использовали наш собственный тип String (это было необходимо, потому что мы предоставляем комплект разработки программного обеспечения, в котором разработчики плагинов могут использовать разные компиляторы и, следовательно, разные несовместимые реализации std::string/std::wstring).
Я сделал простое изменение в ответ на сеанс профилирования выборки графа вызовов, показав, что String::String(const String&) занимает значительное время. Методы, подобные приведенному выше, были самыми большими участниками (на самом деле сеанс профилирования показал, что выделение и освобождение памяти является одной из самых больших горячих точек, при этом конструктор копирования String является основным источником размещения).
Внесенное мной изменение было простым:
static String null_string;
const String& Something::id() const
{
return valid() ? m_id: null_string;
}
Все же это сделало мир разницы! Горячая точка исчезла в последующих сеансах профилирования, и в дополнение к этому мы проводим тщательное модульное тестирование, чтобы отслеживать производительность наших приложений. После этих простых изменений время всех видов испытаний производительности значительно сократилось.
Вывод: мы не используем абсолютные последние компиляторы, но мы все еще не можем полагаться на то, что компилятор оптимизирует копирование для надежного возврата по значению (по крайней мере, не во всех случаях). Это может быть не так для тех, кто использует более новые компиляторы, такие как MSVC 2010. Я с нетерпением жду, когда мы сможем использовать C++0x и просто использовать ссылки на rvalue, и нам никогда не придется беспокоиться о том, что мы пессимизируем наш код, возвращая сложный классы по значению.
[Править] Как указал Нейт, RVO применяется к возвращаемым временным файлам, созданным внутри функции. В моем случае не было таких временных (кроме недопустимой ветви, где мы создаем пустую строку), и поэтому RVO не был бы применим.
Просто немного придираться: во многих языках программирования не принято возвращать массивы из функций. В большинстве из них возвращается ссылка на массив. В C++ самая близкая аналогия будет возвращаться boost::shared_array
Если производительность является реальной проблемой, вы должны понимать, что семантика перемещения не всегда быстрее, чем копирование. Например, если у вас есть строка, которая использует оптимизацию небольших строк, то для небольших строк конструктор перемещения должен выполнять ту же работу, что и обычный конструктор копирования.