c++ - std::vector 的性能差是因为没有调用 realloc 的对数次数吗？

Question

编辑:我又添加了两个基准测试，以比较 realloc 与 C 数组的使用以及 reserve() 与 std::vector 的使用。从最后的分析来看，realloc 的影响似乎很大，即使只调用了 30 次。检查文档我猜这是因为 realloc 可以返回一个全新的指针，复制旧指针。为了完成这个场景，我还添加了用于在初始化期间完全分配数组的代码和图表。与 reserve() 的区别是显而易见的。

编译标志:仅图中描述的优化，使用 g++ 编译，仅此而已。

原始问题:

我对 std::vector 与新建/删除数组进行了基准测试，当我添加 10 亿个整数时，第二个代码比使用 vector 的代码快得多，尤其是在优化的情况下开启。

我怀疑这是vector内部调用realloc次数太多造成的。如果 vector 每次填充时都不会增长一倍，就会出现这种情况(这里数字 2 没有什么特别的，重要的是它的大小呈几何增长)。在这种情况下，对 realloc 的调用将仅为 O(log n) 而不是 O(n)。

如果这就是导致第一个代码运行缓慢的原因，我该如何告诉 std::vector 以几何方式增长？

请注意，调用 reserve once 在这种情况下会起作用，但在更一般的情况下不起作用，在这种情况下 push_back 的数量是事先不知道的。

黑线

#include<vector>

int main(int argc, char * argv[]) {
    const unsigned long long size = 1000000000;

    std::vector <int> b(size);
    for(int i = 0; i < size; i++) {
        b[i]=i;
    }    
    return 0;
}

蓝线

#include<vector>

int main(int argc, char * argv[]) {
    const int size = 1000000000;    
    std::vector <int> b;
    for(int i = 0; i < size; i++) {
        b.push_back(i);
    }    

    return 0;
}

绿线

#include<vector>

int main(int argc, char * argv[]) {
    const int size = 1000000000;
    std::vector <int> b;
    b.reserve(size);
    for(int i = 0; i < size; i++) {
        b.push_back(i);
    }    

    return 0;
}

红线

int main(int argc, char * argv[]) {
    const int size = 1000000000;
    int * a = new int [size];
    for(int i = 0; i < size; i++) {
        a[i] = i;
    }
    delete [] a;   
    return 0;
}

橙线

#include<vector>

int main(int argc, char * argv[]) {
    const unsigned long long size = 1000000000;
    int * a = (int *)malloc(size*sizeof(int));
    int next_power = 1;
    for(int i = 0; i < size; i++) {
        a[i] = i;
        if(i == next_power - 1) {
            next_power *= 2;
            a=(int*)realloc(a,next_power*sizeof(int));
        }
    }
    free(a);
    return 0;
}

编辑:按照建议检查.capacity()，我们看到增长确实呈指数级增长。那么为什么 vector 这么慢？

Answer 1

优化后的 C 样式数组优化为空。

On godbolt :

xorl %eax, %eax
retq

这就是程序。

每当你有一个优化到接近 0 的程序时，你应该考虑这种可能性。

优化器发现您没有对分配的内存执行任何操作，注意到未使用的分配内存可能具有零副作用，并消除了分配。

并且写入内存然后从不读取它也具有零副作用。

相比之下，编译器很难证明 vector 的分配是无用的。编译器开发人员可能会教它识别未使用的 std vector ，就像他们识别未使用的原始 C 数组一样，但这种优化确实是一个极端情况，根据我的经验，它会导致很多问题分析。

请注意，在任何优化级别的 vector-with-reserve 与未优化的 C 样式版本的速度基本相同。

在 C 风格的代码中，唯一需要优化的是“什么都不做”。在 vector 代码中，未优化的版本充满了额外的堆栈帧和调试检查，以确保您不会越界(如果越界，则彻底崩溃)。

请注意，在 Linux 系统上，分配大块内存除了摆弄虚拟内存表外没有任何作用。只有当内存被触摸时，它才会真正为您找到一些零的物理内存。

毫无保留地，std vector 必须猜测一个初始的小尺寸，调整它的大小并复制它，然后重复。这会导致 50% 的性能损失，这对我来说似乎是合理的。

有了保留，它实际上就完成了工作。这项工作只需不到 5 秒。

通过推回添加到 vector 确实会导致它呈几何增长。几何增长导致每份数据的 2-3 个拷贝的渐近平均。

---

至于重新分配，std::vector 不重新分配。它分配一个新缓冲区，并复制旧数据，然后丢弃旧数据。

Realoc 尝试增大缓冲区，如果不能，则按位复制缓冲区。

这比 std vector 管理按位可复制类型的效率更高。我敢打赌 realloc 版本实际上从不复制；总是有内存空间可以将 vector 增长到(在实际程序中可能不是这种情况)。

std 库分配器中缺少 realloc 是一个小缺陷。您必须为它发明一个新的 API，因为您希望它适用于非按位复制(类似于“尝试增加分配的内存”，如果失败则由您决定增加分配)。