LINUX.ORG.RU

Для std::vector, полезен ли .reserve() перед std::move в конец оного?

 


0

1

Вопрос о std::move для range: https://en.cppreference.com/w/cpp/algorithm/move

Полезно ли делать .reserve перед тем, как добавлять элементы в конец контейнера с помощью вышеупомянутой функции и std::back_inserter? Или STL сам это уже делает?

std::vector<T> result;
while (someCondition) {
  // ...
  std::vector<T> part = process();
  result.reserve(result.size() + part.size()); // <-- сабж, полезно ли?
  std::move(part.begin(), part.end(), std::back_inserter(result));
}

Доводилось слышать вот какое предупреждение для подобных сценариев.

Когда в вектор добавляются элементы порциями и вы не знаете, сколько суммарно их будет добавлено, то использование reserve между вставками отдельных порций может ухудшить производительность.

Происходит это вот почему. Когда выполняется обычный push_back/emplace_back, и size()==capacity(), то вектор автоматически увеличивает свой размер. Но не на 1, а умножая свой текущий capacity() на некий коэффициент. Например, на 1.5 или на 2.

Допустим, например, что коэффициент равен 1.5 и начальный capacity() равен 10. Ваш вектор сперва вырастет до 15, затем до 23, затем до 34, затем до 51, затем до 76 и т.д. Т.е. после каждог такого увеличения у вас будет оказываться все больше и больше «резервного» места в векторе для того, чтобы переаллокаций больше не было.

Поэтому, если вы добавляете 1000 порций и каждая порция небольшая (например, не больше 10), то у вас сперва будут частые переаллокации на некоторых push_back-ах. А потом они будут становиться все более и более редкими.

Но вот если вы постоянно дергаете reserve(), то вы постоянно инициируете переаллокации, т.к. reserve() выделяет вам место только под заказанный вами capacity. Без использования увеличивающего коэффициента, как в случае с push_back-ом.

Поэтому если вы добавляете 1000 порций и делаете reserve перед добавлением каждой порции, то у вас будет 1000 переаллокаций.

Ну а как вы будете добавлять элементы — через push_back с rvalue reference или через emplace_back — это уже переаллокациям содержимого вектора отношения не имеет.

Так что отталкивайтесь от того профиля нагрузки, который у вас есть. И проводите, по возможности, замеры на своих данных.

eao197 ★★★★★ ()
Ответ на: комментарий от eao197

т.к. reserve() выделяет вам место только под заказанный вами capacity.

Все таки reserve может выделить и больше.

https://en.cppreference.com/w/cpp/container/vector/reserve

Increase the capacity of the vector to a value that's greater or equal to new_cap.

Так что отталкивайтесь от того профиля нагрузки, который у вас есть. И проводите, по возможности, замеры на своих данных.

В данном случае я знаю наперед сколько будет циклов, только вот размер каждого part сильно зависит от входных данных. Может быть от 1 до 30 (но огнаничение сверху не жесткое).

На самом начале делаю еще в стиле:

constexpr auto PART_SIZE_ESTIMATE = 4ul;
result.reserve(numberOfParts * PART_SIZE_ESTIMATE); 

KennyMinigun ★★★★★ ()
Ответ на: комментарий от KennyMinigun

Increase the capacity of the vector to a value that's greater or equal to new_cap.

Это следует трактовать так: после вызова reserve емкость вектора будет больше или равной new_cap. Больше она может быть, например, если capacity() уже больше, чем new_cap. В этом случае reserve ничего не делает.

Рассчитывать на то, что вам reserve зарезервирует, скажем, new_cap*1.5, не стоит.

На самом начале делаю еще в стиле:

Тогда смысла в дополнительных reserve внутри цикла не видно.

eao197 ★★★★★ ()

Выглядит как тонкий троллинг лоровских программистов.

Нужно, конечно, смотреть с вашими данными, но вот такой простой тест https://pastebin.com/k7Gudqb5 (я комментировал строку с reserve) дает совершенно однозначный результат: с резервированием на порядки медленнее (где-то 6 сек против 0.02 сек)

vmx ★★ ()
Ответ на: комментарий от vmx

где-то 6 сек против 0.02 сек

Выглядит как толстый троллинг всех и вся. Слишком большая разница не смутила? Ну и неплохо было бы показать, что оптимизатор не дропнул цикл

Deleted ()
Ответ на: комментарий от vmx

я специально там написал rand()

Это не помешает компилятору оставить только вызов printf в конце, что он скорее всего и сделал в одном из случаев

давайте свой

А что он должен показать? Разве что на синтетике один вариант в довольно избитой теме предпочтительней другого

Deleted ()
Ответ на: комментарий от Deleted

Вы так безапелляционно пишете, что я не выдержал и посмотрел в ассемблерный код. Нет, ничего он там не выбросил, цикл проходит в обоих случаях.

Раз не хотите показывать свои тесты, смысла продолжать дискуссию нет. Я уже свое любопытство удовлетворил, вы с остальными экспертами свое экспертное мнение высказали, ТС похоже тоже уже для себя все решил.

vmx ★★ ()
Ответ на: комментарий от vmx

Эх, тролота... Давай покормлю:

#include <vector>

void autoalloc()
{
	std::vector<int> v;
	for (auto i(180000000U);i--;v.resize(v.size()+1U),const_cast<volatile int&>(v.back())=0);
}

void prealloc()
{
	std::vector<int> v;
	v.reserve(60000000U);
	for (auto i(60000000U);i--;v.resize(v.size()+1U),const_cast<volatile int&>(v.back())=0);
	v.reserve(60000000U);
	for (auto i(60000000U);i--;v.resize(v.size()+1U),const_cast<volatile int&>(v.back())=0);
	v.reserve(60000000U);
	for (auto i(60000000U);i--;v.resize(v.size()+1U),const_cast<volatile int&>(v.back())=0);
}

int main() try
{
#ifdef USING_PREALLOC
	prealloc();
#else
	autoalloc();
#endif
}
catch (...) { throw; }
$ g++ -xc++ -std=c++14 -pedantic-errors -O3 -g0 -opreallocation-test preallocation-test.cxx 
$ time -p ./preallocation-test
real 4,04
user 1,82
sys 2,21
$ g++ -xc++ -std=c++14 -pedantic-errors -O3 -g0 -DUSING_PREALLOC -opreallocation-test preallocation-test.cxx 
$ time -p ./preallocation-test
real 3,61
user 1,75
sys 1,86

Deleted ()
Ответ на: комментарий от Deleted

Не хотелось бы вас расстраивать, но это не так работает.

Вот есть код в ОП. Вы утверждаете что (при каких-то условиях) с преаллокацией он будет работать быстрее, чем без преаллокации. И в доказательство приводите совершенно другой код.

То, что код с преаллокацией может работать быстрее было бы вполне логично. Но вы, вместо того чтоб показать условия, при которых это начнет действовать (размеры элемента вектора, количество преаллоцируемых элементов и т.п.) начинаете зажигать в духе Царя.

Дело ваше, конечно, но зачем так делать - не понимаю

vmx ★★ ()
Ответ на: комментарий от vmx

вопрос про преаллокацию

вот правильные тесты этого «наинтереснейшего» момента

приводите совершенно другой код
зажигать в духе Царя

А ты прожорлив. Но мне сейчас особо нечего делать, поэтому давай ещё накормлю:

размеры элемента вектора, количество преаллоцируемых элементов

Вперёд, рассказывай, где ТС говорил что-то о размерах элементов и их кол-ве

Deleted ()