Как известно, если мы помещаем элементы push_back в std::vector<>
и если вся память, выделенная в векторе, занята, то std::vector<>
резервирует 2X текущего размера памяти (выделяет новую память с 2X размером), изменяет размер вектора и копирует старые данные в новую память.
Мы можем оптимизировать его, и Facebook сделал это с помощью библиотеки Folly (FBVector — встроенная реализация Facebook std :: vector. У него есть специальные оптимизации для использования с перемещаемыми типами и jemalloc. https://github.com/facebook/folly/blob/master/folly/FBVector.h#L21 ).
То есть когда vector<>
не хватает памяти для push_back нового элемента, тогда мы выделяем больше памяти, но не в 2 раза больше (в разное количество раз: 1,3 — 1,5 раза)
Описание: https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md
Графический решатель ниже показывает, что выбор k = 1,5 (синяя линия)
позволяет повторно использовать память после 4 перераспределений, выбирая k = 1.45 (красный
линия) позволяет повторно использовать память после 3 перераспределений и выбрать k = 1,3
(черная линия) позволяет повторно использовать только после 2 перераспределений.
Но почему мы должны использовать folly::fbvector<>
вместо std::vector<>
с нашим пользовательским распределителем, который использует VirtualAllocEx()
(как показано здесь: Для чего мне нужно использовать VirtualAlloc / VirtualAllocEx? ) или то же самое в linux https://stackoverflow.com/a/2782910/1558037 , где:
std::vector<>::reserve()
— изначально резервировать большую незафиксированную область виртуального адреса (выделять WMA, но не выделяет PTE в PT), например выделять изначально 16 ГБ виртуальной области и каждый раз при нехватке памяти выделять память (выделять PTE — выделять физическая площадь) равен 1 x РАЗМЕР вектораstd::vector<>::resize()
— а затем только зафиксировать новый пакет страниц, выделить только новый PTE в PT, без перераспределения памяти, которая уже используется, и без копирования данных из старой памяти в новуюВ общем и целом:
Преимущества этого подхода с большой незафиксированной областью по сравнению с folly::vector<>
: всегда мы выделяем только новую часть памяти и никогда не копируем старые данные.
Преимущества folly::vector<>
подходить над std::vector<>
: иногда нам не нужно выделять новую память, но копировать старые данные в новую память следует всегда.
Это зависит от реализации. Библиотека GCC выделяет в два раза больше, а Visual C ++ — нет. Я верю, что он также использует 1.5, но не уверен.
Я верю, folly
должен быть независимым от операционной системы, ваш подход зависит от Windows / Linux.
Перемещение объекта из старого вектора в новый должно быть не таким страшным, если вы тщательно выбираете типы — то есть используйте std::unique_ptr
как тип данных.
Других решений пока нет …