std :: vector <std :: vector <unsigned char>> или std :: deque <std :: vector <unsigned char>>?

Question

У меня есть существующий алгоритм, и мне нужно его оптимизировать, если это возможно.В данный момент многое изменить в этом алгоритме невозможно.Алгоритм работает с экземпляром std::vector< std::vector<unsigned char> >.Это выглядит так:

typedef std::vector<unsigned char> internal_vector_t;
std::vector< internal_vector_t > internal_vectors; 

while (fetching lots of records) {
   internal_vector_t tmp;
   // reads 1Mb of chars in tmp...
   internal_vectors.push_back(tmp);
   // some more work
}

// use this internal_vectors

Алгоритм много раз вставляет в internal_vectors экземпляры internal_vector_t, используя push_back (). Большинство экземпляров internal_vector_t имеют размер 1 Мб .Поскольку размер internal_vectors неизвестен, резерв () не делается заранее.

Первое, что я не понимаю, это то, что происходит, когда internal_vectors достигает своей текущей емкости, нужно выделитьновый блок и скопируйте его текущий контент в больший блок памяти.Поскольку большая часть блоков имеет размер 1 МБ, копирование является длительной операцией. Стоит ли ожидать, что компилятору (gcc 4.3, MS VC ++ 2008) удастся оптимизировать его, чтобы избежать копирования ?

Если копирование невозможно, изменится ли на std::deque help ?Я рассматриваю std :: deque, потому что мне все еще нужен доступ по индексу, как internal_vectors [10].Вот так:

typedef std::vector<unsigned char> internal_vector_t;
std::deque< internal_vector_t > internal_vectors; 
// the same while

Насколько я понимаю, std::deque не требует перемещения, которое было когда-то выделено.Прав ли я, что std::deque в этой ситуации потребует меньше выделения и копирования на push_backs?

Обновление: 1) Согласно DeadMG MSVC9 выполняет этот тип оптимизации (The Swaptimization - TR1 Исправления в VC9 SP1 ).gcc 4.3, вероятно, не выполняет этот тип оптимизации.

2) Я профилировал версию алгоритма, которая использует std::deque< std::vector<unsigned char> >, и я вижу, что его производительность лучше.

3) Я также использовал swap, который былпредложено Марк Рэнсом .Использование этого улучшило производительность:

   internal_vector_t tmp;
   internal_vectors.push_back(empty);
   tmp.swap(internal_vectors.back());

Answer 1

MSVC9 реализует нечто, известное как «своптимизация» для своих стандартных контейнеров. Это более слабая версия семантики перемещения. Когда внешний вектор изменяется, он не копирует внутренние векторы.

Однако вам лучше всего просто обновить ваш компилятор до MSVC10 или GCC (я думаю, что это 4.5), что даст вам семантику перемещения, что сделает такие операции значительно более эффективными. Конечно, std::deque, вероятно, все еще является более умным контейнером, но семантика перемещения очень важна для производительности во многих местах.

Answer 2

Каждый раз, когда вы вставляете internal_vector_t в internal_vectors, он собирается сделать копию internal_vector_t.Это будет верно, используете ли вы vector или deque.Стандартные контейнеры всегда делают копию вставляемого объекта.

Вы можете исключить копирование, вставив пустой internal_vector_t, а затем swap содержимое вставленного объекта с тем, который вам действительно нужендля вставки.

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

Редактировать: Совет, который я дал выше, можно обобщить с помощью этих изменений кода.Этот код должен избегать копирования всех больших векторов.

typedef std::vector<unsigned char> internal_vector_t;
std::deque< internal_vector_t > internal_vectors; 
internal_vector_t empty;

while (fetching lots of records) {
   internal_vector_t tmp;
   // reads 1Mb of chars in tmp...
   internal_vectors.push_back(empty);
   tmp.swap(internal_vectors.back());
   // some more work
}

Answer 3

std::deque не хранит свои элементы непрерывно - он разбивает свое хранилище на серию «блоков» постоянного размера.Это означает, что когда у std::deque заканчивается емкость, ему нужно только выделить новый блок постоянного размера - ему не нужно перераспределять весь свой внутренний буфер и перемещать все его существующие элементы.

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

std::vector «умный»его схема перераспределения, распределение по частям в соответствии с геометрическим рядом (часто удвоение или увеличение емкости на 1,5 и т. д.).Это означает, что перераспределение происходит не часто.

std::deque может быть более эффективным в этом случае, поскольку, когда перераспределение происходит, оно выполняет меньше работы.Как всегда, для получения любых действительных чисел вам понадобится сравнительный тест.

Возможно, ваш код может быть улучшен в других областях.Кажется, что на каждой итерации цикла while вы создаете новый internal_vector_t tmp.Может быть более эффективно объявить это вне цикла, и просто ::clear() это хранилище на каждой итерации.Вы также копируете весь вектор tmp каждый раз, когда вызываете internal_vectors.push_back(tmp) - возможно, вы могли бы улучшить это, просто переместив вектор tmp через internal_vectors.push_back(std::move(tmp)) - это просто скопирует несколько указателей.

Надеюсь, это поможет.

Answer 4

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

Answer 5

Индексируете ли вы внешний вектор? Если нет, то как насчет std::list<std::vector<unsigned char> >?