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

Question

Как известно, если мы помещаем элементы 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 /questions/43853867/lyuboj-sposob-zarezervirovat-no-ne-fiksirovat-pamyat-v-linux/43853876#43853876, где:

• std::vector<>::reserve() - изначально резервировать большую незафиксированную область виртуального адреса (выделять WMA, но не выделяет PTE в PT), например выделять изначально 16 ГБ виртуальной области и каждый раз при нехватке памяти выделять память (выделять PTE - выделять физическая площадь) равен 1 x РАЗМЕР вектора
• std::vector<>::resize() - а затем только зафиксировать новый пакет страниц, выделить только новый PTE в PT, без перераспределения памяти, которая уже используется, и без копирования данных из старой памяти в новую

В целом:

Преимущества этого подхода с большой незафиксированной областью по сравнению с folly::vector<>: мы всегда выделяем только новую часть памяти и никогда не копируем старые данные.

Преимущества folly::vector<> подходить над std::vector<> Иногда нам не нужно выделять новую память, но копирование старых данных в новую память всегда должно происходить.

Answer 1

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

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

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