Почему мы должны использовать folly :: fbvector вместо std :: vector с allocator, который изначально резервирует большую незафиксированную область?

Как известно, если мы помещаем элементы 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<>: иногда нам не нужно выделять новую память, но копировать старые данные в новую память следует всегда.

4

Решение

Это зависит от реализации. Библиотека GCC выделяет в два раза больше, а Visual C ++ — нет. Я верю, что он также использует 1.5, но не уверен.

Я верю, folly должен быть независимым от операционной системы, ваш подход зависит от Windows / Linux.

Перемещение объекта из старого вектора в новый должно быть не таким страшным, если вы тщательно выбираете типы — то есть используйте std::unique_ptr как тип данных.

1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]