предварительное распределение и вектор

Question

В C ++, для вектора, почему предварительное распределение так важно, даже если вектор выделяет пространство динамически

Answer 1

Во-первых, вряд ли это будет "так важно" в 99% случаев.

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

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

Answer 2

Другие ответы уже охватывали теорию, но я хотел бы добавить также некоторые цифры, чтобы понять, что происходит.

Однажды я написал небольшой набор тестов для сравнения std::vector push_back, reserve + push_back, размер в конструкторе (который должен совпадать с resize) + operator[] и необработанные динамические массивы;Вот результаты для 10000000 int с:

matteo@teoubuntu:~/cpp/vectorbenchmark2$ ./vectorbenchmark2 
Insert the number of elements: 10000000
Insert the number of iterations: 100
Minimum allocation for each benchmark 40000000 bytes.
Starting benchmark std::vector<int> (push_back/iterator, without reserve)... benchmark completed.
Results: 173.1 +/- 2.4 ms
Starting benchmark std::vector<int> (push_back/iterator, with reserve)... benchmark completed.
Results: 122.17 +/- 0.57 ms
Starting benchmark std::vector<int> (sized with constructor/operator[])... benchmark completed.
Results: 115.95 +/- 0.66 ms
Starting benchmark new int[]... benchmark completed.
Results: 121.33 +/- 0.84 ms
Starting benchmark malloc+memset... benchmark completed.
Results: 123.9 +/- 4.3 ms
Starting benchmark malloc... benchmark completed.
Results: 117.7 +/- 2.3 ms
Starting benchmark std::list<int>... benchmark completed.
Results: 552 +/- 35 ms

Каждый тест состоит из выделения структуры данных, заполнения ее случайными числами и перечитывания всего в переменной volatile.Тесты выполняются столько раз, сколько указано во втором запрашиваемом параметре (в этом цикле я поставил 100);время измеряется с gettimeofday.Отображаемые результаты представляют собой среднее значение и стандартное отклонение, рассчитанное для всех времен каждой категории.Код для всего этого доступен здесь .

Какие результаты мы можем извлечь из этих данных?

• Первый очевидный результат заключается в том, что push_backБез предварительного выделения самый медленный метод: в этих условиях он примерно на 41% медленнее, чем push_back с предварительным распределением.Таким образом, если время является критическим фактором и вычисление того, насколько большим будет ваш vector, не составит труда, reserve может быть действительно удобным.Очевидно, что если ваше выделение + заполнение в целом занимает ~ 10 мс, даже сокращение его на 40% не будет действительно замечено;как обычно, оптимизируйте там, где это имеет смысл (т. е. на узких местах).
• еще один интересный результат заключается в том, что инициализация размера массива (вместо «прозрачного» предварительного выделения с reserve) выполняется еще быстрее;Я думаю, что это потому, что мы не вызываем push_back (который должен обновлять vector «официальный размер») в узком цикле;вместо этого operator[] почти ничего не делает, кроме суммы указателей, и легко вставляется.Возможно, с помощью итераторов (которые в случае vector являются в основном указателями) можно получить что-то большее.
• Интересно, что единственный реальный претендент с готовностью - resize d vector - это просто malloc, который не предлагает никаких наворотов и не подходит для не POD-типов (и все же в этом самом тесте результаты немного хуже).Замечательно, что vector может быть , что эффективным, сохраняя при этом свои преимущества (я говорю с вами, люди, которые распространяют C-style mallocs вокруг для предполагаемого увеличения производительности!)
• std::list (введено для сравнения) - самый медленный из них - но мы уже знали это :)

Очевидно, YMMV;Прежде всего, это результаты для конкретной архитектуры с конкретным компилятором и его конкретной реализацией STL (а именно, g ++ 4.4.5).Затем я думаю, что использование «сложных» типов (с конструкторами, конструкторами копирования и т. Д.) Может изменить положения методов reserve / resize (resize необходимо для создания всех объектов в vector, в то время какЯ не думаю, что reserve делает).Некоторые изменения могут также возникнуть из-за изменения используемого типа примитива (int против long против short и т. Д.).

Более того, между всеми тестами, кроме первого и последнего, разница довольно мала;оно, безусловно, значительно больше стандартного отклонения, но я думаю, что даже небольшие изменения в стандартной библиотеке могут изменить некоторые их относительные результаты.Кроме того, изменение количества элементов также должно иметь заметные эффекты, так как эти времена являются суммами различных операций big-O, поэтому увеличение или уменьшение количества элементов может изменить преобладающее добавление к сумме.

Условия тестирования (скучный материал)

AMD Phenom X4 955 (3,2 ГГц x4), 4 ГБ ОЗУ DDR3

Компилятор:

matteo@teoubuntu:~/cpp/vectorbenchmark2$ g++ --version
g++ (Ubuntu/Linaro 4.4.4-14ubuntu5) 4.4.5
Copyright (C) 2010 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

ОС/ Ядро:

matteo@teoubuntu:~/cpp/vectorbenchmark2$  uname -a
Linux teoubuntu 2.6.35-24-generic #42-Ubuntu SMP Thu Dec 2 02:41:37 UTC 2010 x86_64 GNU/Linux

Параметры компиляции:

matteo@teoubuntu:~/cpp/vectorbenchmark2$ make
g++ -O3 -Wall -Wextra -ansi -pedantic   -MMD -MF BenchmarkFunctors.o.d -c -o BenchmarkFunctors.o BenchmarkFunctors.cpp
g++ -O3 -Wall -Wextra -ansi -pedantic   -MMD -MF main.o.d -c -o main.o main.cpp
g++ -O3 -Wall -Wextra -ansi -pedantic   -MMD -MF Utils.o.d -c -o Utils.o Utils.cpp
g++ -O3 -Wall -Wextra -ansi -pedantic   BenchmarkFunctors.o main.o Utils.o -o vectorbenchmark2

Код набора тестов

Answer 3

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

Когда вы резервируете место, вы говорите ему, что знаете, сколько места ему понадобится, и не нужно гадать. Это позволяет избежать повторного выделения и копирования.

Обычно это не важно, но это определенно соображение, когда у вас очень большой вектор, и вы заранее знаете, насколько он будет большим: почему бы вам не зарезервировать для него достаточно места?

Answer 4

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

Answer 5

Потому что вы хотите избежать как можно большего количества выделений - в этом случае все происходит быстрее.:)

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

---

Редактировать:

Пример:

Если у вас 1000 элементов и вам нужно добавить еще один элемент, вы не хотите просто увеличивать массив на 1,потому что сразу после добавления еще другого элемента вам придется изменить его размер еще раз, но если вы, скажем, удвоите его размер, вам потребуется n операций, прежде чем вам потребуется выделить ископируйте n элементов, поэтому стоимость каждого элемента равна единице (для получения дополнительной информации см. ссылку).