5

众所周知,如果我们将元素 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 SIZE
  • std::vector<>::resize()- 然后只提交一批新的页面,在 PT 中只分配新的 PTE,不重新分配已经使用的内存,也不将数据从旧内存复制到新内存

总体

这种方法的优点是具有较大的未提交区域folly::vector<>我们总是只分配新的内存部分,从不复制旧数据。

folly::vector<>方法优于:std::vector<>有时我们不需要分配新内存,但总是应该将旧数据复制到新内存中。

4

1 回答 1

1

这是特定于实现的。GCC 库确实分配了两倍,但 Visual C++ 没有。我相信,它也使用 1.5,但不确定。

我相信,folly应该与操作系统无关,您的方法是特定于 Windows/Linux 的。

如果您仔细选择类型 - 即std::unique_ptr用作数据类型,则从旧向量移动到新向量的对象应该不会那么糟糕。

于 2016-02-23T16:48:45.830 回答