C++ Vector 增长因子

我们都知道 C++ 的 vector 的容量会随着添加的元素而自动增长，但是每次增长多少呢？原来的两倍？三倍？还是多少？下面，让我们来研究下增长因子是如何确定的。

首先，要阐述一个 vector 实现相关的事实：vector 使用 allocator，不管你增长因子是多少，必然需要重新 copy-cons（或 move-cons）一遍。

假设，我们用了一个 vector，其占用内存为 ，内存布局如下图所示：
Free

我们一直使用这个 vector，当元素太多导致内存不够的时候，要重新给这个 vector 分配内存，新分配的内存大小为 。首先，要先分配 的空间，注意，这个时候 那块内存还没有释放掉：
Free Free

然后把之前的M空间释放掉：
Free Free() Free

我们继续使用这个 vector，内存又不够了，再次分配的内存大小为 。和上面类似，分配内存时：
Free Free() Free

然后释放掉前一块地址：
Free Free() Free() Free

以此类推，第 次重新分配内存时，需要新分配 大小的内存，内存分布如下所示（带括号说明已经释放了）：
Free () () (...) Free

然后再把之前的f ^ (n-1) * M大小的内存回收:
Free () () (...) () Free

我们思考这样一个问题：如果当第 次进行内存扩展时，前面 次操作释放的内存（包括第 次的内存和最开始占用的内存 ）之和大于第 次所需要的内存，那么内存分配器就可以用之前留下来的内存而不用再往后去寻找 Free 的块。按照这个想法得到的内存分布如下：
Free (GAP) () Free

这样做的好处有两个，一是可以提高内存分配器的效率，更重要的是，内存的使用更加紧凑，局部性更好，能够更好的利用缓存机制。

上述想法包含一个约束条件，即下面的不等式（两边已同除了 ）： 当 时， 最小为 ，也就是说，第五次进行内存扩展的时候，可以利用前面释放的内存。

当 时，，不等式永假，也就是说，vector 再也不能利用之前释放的内存。

从不等式可以得到， 越小，能满足不等式的 也会随之减小，但是如果 很小，会频繁的遇到内存不足进行扩展的情况，也就是说，会经常性的 copy-cons 或者 move-cons vector 里面的元素，得不偿失。而且 5 也足够小了，所以 1.5 是一个不错的选择。

读到这里，可能很多人会说，内存分配器是按照 First-Fit 来进行内存分配的吗？你怎么能假设“内存管理器就可以用之前留下来的内存而不用再往后去寻找 Free 的块”呢？而且，这示例图都是连续的内存，实际情况未必如此啊。其实现代内存分配器很复杂，可能会把内存先分成若干块，每一块接受不同大小的内存分配，比如第一块都是内存需求量小于 64B 的，第二块都是内存需求量 64B 至 128B，第三块都是需求量 128B-1KB 的等等；同时每一块又可能有不同的分配回收机制。所以实际情况远比我们想象的复杂，想要真实性能，做性能测试才是靠谱的途径。

排除这些外界因素，仅从本文分析的角度看来，增长因子 1.5 是个不错的选择，比 2 要好，因为使用 2 永远不会利用到之前释放的内存。

Facebook 利用上述分析的原理（增长因子是 1.5），配合 jemalloc，开发了一套 fbVector（已开源），性能比 GCC 的要好。Microsoft的 VC++ STL 中的 vector 实现，增长因子也是 1.5 以获取更好的性能。而 GCC 和 CLang 还停留在古老的增长因子为 2 的阶段。

下面这段小程序，能够帮你测试出当前实现的增长因子： 

#include <vector>
#include <iostream>

int main()
{
    std::vector<int> arr;

    for (int i = 1; i < 10; i++)
    {
        arr.push_back(i \* i);
        std::cout <<
            "Size: " << arr.size() << "; " <<
            "Capacity: " << arr.capacity() << "\n";
    }

    return 0;
}