众所周知,如果我们将元素 push_back 到std::vector<>
,并且如果向量中分配的整个内存都被占用,则std::vector<>
保留当前内存大小的 2X(分配 2X 大小的新内存),调整向量大小并将旧数据复制到新内存。
我们可以对其进行优化,Facebook 在 folly-library 中完成了此操作(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,但不在 PT 中分配任何 PTE),例如最初分配 16 GB 的虚拟区域并且每次内存不足时提交内存(分配 PTE - 分配物理区域)等于向量的 1 x SIZEstd::vector<>::resize()
- 然后只提交一批新的页面,在 PT 中只分配新的 PTE,不重新分配已经使用的内存,也不将数据从旧内存复制到新内存
总体:
这种方法的优点是具有较大的未提交区域folly::vector<>
:我们总是只分配新的内存部分,从不复制旧数据。
folly::vector<>
方法优于:std::vector<>
有时我们不需要分配新内存,但总是应该将旧数据复制到新内存中。