std :: vector :: резерв производительности - PullRequest
Новая
       10

std :: vector :: резерв производительности

6 голосов
/ 16 ноября 2009 
inline void add(const DataStruct& rhs) {
   using namespace boost::assign;
   vec.reserve(vec.size() + 3);
   vec += rhs.a, rhs.b, rhs.c;
}

Вышеприведенная функция выполнялась около 17000 раз и выполняла (насколько я вижу. Произошло некоторое преобразование) примерно на 2 величины хуже с вызовом vector :: reserve.

У меня всегда было впечатление, что резерв может ускорить push_back даже для небольших значений, но это не так, и я не могу найти никаких очевидных причин, почему так не должно быть. Запрещает ли резервирование встраивание функции? Является ли вызов size () слишком дорогим? Это зависит от платформы? Я попытаюсь написать небольшой тест, чтобы подтвердить это в чистой среде.

Компилятор: gcc (GCC) 4.4.2 с -g -O2

Ответы [ 6 ]

24 голосов
/ 16 ноября 2009
Реализация

GCC reserve() будет распределять точное количество элементов, в то время как push_back() будет наращивать внутренний буфер экспоненциально, удваивая его, поэтому вы подавляете экспоненциальный рост и вынуждаете перераспределение / копирование на каждой итерации. Запустите тест под номером ltrace или valgrind и посмотрите количество вызовов malloc().

7 голосов
/ 16 ноября 2009

Вы используете reserve(), только если заранее знаете количество элементов. В этом случае reserve() место для всех элементов одновременно.

В противном случае просто используйте push_back() и полагайтесь на стратегию по умолчанию - она ​​будет перераспределяться экспоненциально и значительно сократит количество перераспределений за счет слегка неоптимального потребления памяти.

6 голосов
/ 16 ноября 2009

Используйте только резерв, если вы заранее знаете, сколько места он будет использовать.

Резерв должен будет скопировать весь ваш вектор ...

Если вы выполняете push_back, а вектор слишком мал, он создаст резерв (vec.size () * 2).

Если вы заранее не знаете, насколько большим будет ваш вектор, и если вам нужен произвольный доступ, подумайте об использовании std :: deque.

4 голосов
/ 16 ноября 2009

Когда std :: vector необходимо перераспределить, он увеличивает свой размер выделения на N * 2, где n - его текущий размер. Это приводит к логарифмическому числу reallocs по мере роста вектора.

Если бы вместо этого std :: vector увеличивал свое выделенное пространство на постоянную величину, число reallocs будет расти линейно с ростом вектора.

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

Как правило, единственный рост лучше, чем логарифмический, является постоянным. Именно поэтому комитет по стандартам создал резервный метод. Если вы можете избежать всех reallocs (константа), вы будете работать лучше, чем логарифмическое поведение по умолчанию.

Тем не менее, вы можете рассмотреть комментарии Херба Саттера о предпочтении std :: deque над вектором www.gotw.ca / gotw / 054.htm

3 голосов
/ 16 ноября 2009

Если вы профилируете код, который, я готов поспорить, вы увидите, что + = IS очень быстро, проблема в том, что резерв убивает вас. На самом деле вы должны использовать резерв только тогда, когда знаете, насколько велик вектор. Если вы можете угадать заранее, сделайте ОДИН резерв, в противном случае просто используйте push_back по умолчанию.

3 голосов
/ 16 ноября 2009

Переместить резерв за пределы доп.

Каждый раз, когда вы вызываете «добавить», вы резервируете как минимум 3 дополнительных элемента. В зависимости от реализации вектора, это может увеличивать размер резервного массива почти каждый раз, когда вы вызываете "add" Это определенно приведет к разнице в производительности, которую вы описываете.

Правильный способ использования резерва - что-то вроде: 

vec.reserve(max*3);
for(int i=0; i<max; i++)
   add(i);
...