В C ++ по-прежнему ли плохая практика возвращать вектор из функции?
https://stackoverflow.com/questions/3134831
-
01-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Сокращенная версия: Во многих языках программирования обычно возвращаются большие объекты, такие как векторы / массивы.Является ли этот стиль теперь приемлемым в 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 ++.Надеюсь, больше нет?
Решение
Дейв Абрахамс имеет довольно всесторонний анализ Скорость прохождения / возвращения значений.
Краткий ответ, если вам нужно вернуть значение, то верните значение. Не используйте выходные ссылки, потому что компилятор делает это в любом случае. Конечно, есть предостережения, поэтому вы должны прочитать эту статью.
Другие советы
По крайней мере, ИМО, это обычно плохое представление, но нет по причинам эффективности. Это плохая идея, потому что рассматриваемая функция обычно должна быть написана как общий алгоритм, который производит свой вывод через итератор. Почти любой код, который принимает или возвращает контейнер, а не эксплуатацию на итераторы, следует считать подозреваемым.
Не поймите меня неправильно: есть времена, это имеет смысл проходить вокруг коллекционных объектов (например, строки), но для приведенного примера я бы рассмотрел прохождение или возвращение вектора плохой идеи.
Гист:
Копировать Elision и RVO могу Избегайте «страшных копий» (компилятор не требуется для реализации этих оптимизаций, а в некоторых ситуациях его нельзя применять)
C ++ 0x RValue ссылки разрешать Реализации строки / векторные гарантии это.
Если вы можете отказаться от более старых реализаций Compilers / STL, свободно возвращайте векторы (и убедитесь, что ваши собственные объекты также поддерживают его). Если ваша база кода должна поддерживать «меньшие» компиляторы, придерживайтесь старого стиля.
К сожалению, это имеет большое влияние на ваши интерфейсы. Если C ++ 0X - это не вариант, и вам нужны гарантии, вы можете использовать вместо этого объекты, подсчитанные или копировальные на записи в некоторых сценариях. Однако у них есть нисходящие с многопотативной.
(Желаю только один ответ на C ++ было бы простым и простым и без условий).
Действительно, начиная с C ++ 11, стоимость копирование тот самый std::vector в большинстве случаев исчезает.
Однако следует иметь в виду, что стоимость конструирование новый вектор (тогда разрушающий it) все еще существует, и использование выходных параметров вместо возврата по значению все еще полезно, когда вы хотите повторно использовать емкость вектора.Это задокументировано как исключение в F.20 из Основных Руководящих принципов C++ Core.
Давайте сравним:
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 (т.е. объем памяти (v) = 8 ГБ), время абсолютно идентично.Действительно, в обоих случаях мы выделяем только один раз огромный вектор объемом 8 ГБ в памяти.Это также доказывает, что при использовании BuildLargeVector1() копирование не произошло:У меня не хватило бы оперативной памяти для копирования!
Когда numIter = 2, повторное использование емкости вектора вместо перераспределения второго вектора происходит в 1,37 раза быстрее.
Когда numIter = 256, повторное использование векторной емкости (вместо выделения / освобождения вектора снова и снова 256 раз ...) в 2,45 раза быстрее :)
Мы можем заметить, что time1 в значительной степени постоянен с момента numIter = 1 Для numIter = 256, что означает, что выделение одного огромного вектора размером 8 ГБ практически так же затратно, как выделение 256 векторов размером 32 МБ.Однако выделение одного огромного вектора объемом 8 ГБ определенно дороже, чем выделение одного вектора объемом 32 МБ, поэтому повторное использование емкости вектора обеспечивает прирост производительности.
От numIter = 512 (объем памяти (v) = 16 МБ) для numIter = 8M (mem (v) = 1 КБ) - это самое приятное место.:оба метода работают точно так же быстро, как и все другие комбинации numIter и vecSize.Вероятно, это связано с тем фактом, что размер кэша L3 моего процессора составляет 8 МБ, так что вектор практически полностью помещается в кэш.Я на самом деле не объясняю, почему внезапный скачок time1 если для mem (v) = 16 МБ, казалось бы, логичнее было бы произойти сразу после, когда mem (v) = 8 МБ.Обратите внимание, что, как ни странно, в этом приятном месте отказ от повторного использования емкости на самом деле происходит немного быстрее!На самом деле я этого не объясняю.
Когда numIter > 8M все начинает становиться ужасным.Оба метода становятся медленнее, но возврат вектора по значению становится еще медленнее.В худшем случае, с вектором, содержащим только один единственный int, повторное использование емкости вместо возврата по значению происходит в 3,3 раза быстрее.Предположительно, это связано с постоянными затратами на malloc(), которые начинают доминировать.
Обратите внимание, что кривая для time2 более плавная, чем кривая для time1:повторное использование векторных мощностей, как правило, происходит не только быстрее, но, что, возможно, более важно, это более предсказуемый.
Также обратите внимание, что в the sweet spot мы смогли выполнить 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: "";
}
... Обратите внимание, что мы использовали наш собственный тип строки (это требовалось, поскольку мы предоставляем комплект разработки программного обеспечения, где писатели плагинов могут быть использованы различные компиляторы и, следовательно, различные, несовместимые реализации STD :: String / std :: WSTRING).
Я сделал простое изменение в ответ на сеанс профилирования выборки графика вызовов, показывающий строку :: string (Const String &), чтобы получить значительное количество времени. Способы, такие как в приведенном выше примере, были величайшими участниками (фактически сеанс профилирования, показал распределение памяти, а делилокацию, чтобы быть одной из самых больших горящих точек, причем конструктор String Copy является основным вкладчиком для ассигнований).
Изменение, которое я сделал, было просто:
static String null_string;
const String& Something::id() const
{
return valid() ? m_id: null_string;
}
Тем не менее, это сделало мир различий! Горячая точка ушла в последующие сеансы профилировщиков, а в дополнение к этому мы делаем много тщательного тестирования подразделения для отслеживания нашей производительности приложений. Все виды испытаний производительности значительно упали после этих простых изменений.
Вывод: мы не используем абсолютные новейшие компиляторы, но мы все еще не можем зависеть от компилятора, оптимизирующего копирование для возврата по значению надежно (по крайней мере, во всех случаях). Это может быть не так для тех, кто использует новые компиляторы, такие как MSVC 2010. Я с нетерпением жду, когда мы сможем использовать C ++ 0x и просто использовать ссылки на RValue и не должны беспокоиться о том, что мы пессимизируем наш код, возвращая комплекс классы по значению.
Править] Как указал Nate, RVO применяется к возвращению временных данных, созданных внутри функции. В моем случае таких временных не было (за исключением недействительной ветки, где мы строим пустую строку), и, таким образом, RVO не применим.
Просто в NitPick немного: во многих языках программирования не распространено, чтобы вернуть массивы из функций. В большинстве из них возвращается ссылка на массив. В C ++, ближайшая аналогия будет возвращаться boost::shared_array
Если производительность является реальной проблемой, вы должны реализовать, что SEMANTICS НЕ всегда быстрее, чем копирование. Например, если у вас есть строка, которая использует небольшая оптимизация струны Тогда для небольших строк в шаге конструктор должен выполнять то же количество работы в качестве регулярного конструктора копирования.
