станд :: вектор :: резерв снижения производительности

Question

inline void add(const DataStruct& rhs) { 
    using namespace boost::assign; 
    vec.reserve(vec.size() + 3); 
    vec += rhs.a, rhs.b, rhs.c; 
} 

выше функция была выполнена в течение приблизительно 17 000 раз, и это выполняется (насколько я могу видеть. Был некоторое преобразование участие) около 2 магнитуды хуже с ВЫЗОВ МАСТЕРА к вектору ::.

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

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

Answer 1

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

Answer 2

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

Reserve потребуется скопировать весь свой вектор ...

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

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

Answer 3

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

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

Answer 4

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

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

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

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

Answer 5

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

Answer 6

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

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

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

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

Это сказал, что вы можете рассмотреть комментарии Герба Саттера о предпочтя станд :: Deque над векторными www.gotw.ca/gotw/054.htm