std :: vector的性能不好是因为没有调用realloc的对数次？

Question

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

编译标志:只有图中描述的优化,用g ++编译,仅此而已.

原始问题:

std::vector当我添加10亿个整数并且第二个代码比使用向量的代码快得多时,我做了vs新/删除数组的基准测试,尤其是在启用优化的情况下.

我怀疑这是由内部调用realloc的向量太多次引起的.如果vector每次填充时它的大小不会增加一倍就会出现这种情况(这里数字2没有什么特别之处,重要的是它的大小几何增长).在这种情况下,对realloc的调用只会O(log n)代替O(n).

如果这是导致第一个代码缓慢的原因,我怎么能告诉std :: vector几何增长？

请注意,调用reserve一次会在这种情况下工作,但不是在更普遍的情况下,事先不知道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()按照建议检查,我们看到增长确实呈指数增长.那么为什么矢量这么慢？

Answer 1

优化的C样式数组优化为零.

在godbolt上:

xorl %eax, %eax
retq

这是该计划.

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

优化器看到你对分配的内存没有任何作用,注意到未使用的分配内存可能没有副作用,并且消除了分配.

写入内存然后从不读它也没有副作用.

相比之下,编译器很难证明向量的分配是无用的.可能编译器开发人员可以教它识别未使用的标准向量,就像它们识别未使用的原始C数组一样,但这种优化确实是一个极端情况,并且在我的经验中导致很多问题分析.

请注意,任何优化级别的vector-with-reserve与未优化的C风格版本的速度基本相同.

在C风格代码中,唯一要优化的是"不要做任何事情".在矢量代码中,未经优化的版本充满了额外的堆栈帧和调试检查,以确保您不会超出范围(如果您这样做,则会彻底崩溃).

请注意,在Linux系统上,除了虚拟内存表之外,分配大量内存并不会做任何事情.只有当触摸内存时,它实际上才会为您找到一些零物理内存.

没有保留,标准向量必须猜测一个初始的小尺寸,重新调整它的副本,并重复.这导致50%的性能损失,这对我来说似乎是合理的.

有了储备,它实际上可以完成工作.这项工作不到5秒.

通过推回添加到矢量会导致它几何增长.几何增长导致每个数据的2-3个副本的渐近平均值.

至于realloc的,的std :: vector所没有的realloc.它分配一个新缓冲区,并复制旧数据,然后丢弃旧数据.

Realloc尝试增长缓冲区,如果不能,则按位复制缓冲区.

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

std库分配器中缺少realloc是一个小缺陷.你必须为它发明一个新的API,因为你希望它能用于非按位复制(类似于"尝试增长分配的内存",如果失败则由你来增加分配).

Answer 2

当我添加10亿个整数时,第二个代码比使用向量的代码快得多

那......完全不足为奇.您的一个案例涉及一个动态大小的容器,必须重新调整其负载,另一个涉及固定大小的容器,而不是.后者只需要做更少的工作,没有分支,没有额外的分配.公平的比较是:

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

现在这与你的数组示例完全相同(好吧,几乎 - new int[size]默认初始化所有ints,而std::vector<int>(size)零初始化它们,所以它仍然更多工作).

将这两者相互比较并没有多大意义.如果固定大小的int数组适合您的用例,请使用它.如果没有,那就不要了.您是否需要动态大小的容器.如果你这样做,执行速度比固定大小的解决方案慢,那你就是在暗示放弃了.

如果这是导致第一个代码缓慢的原因,我怎么能告诉std::vector它几何增长？

std::vector已经被要求几何增长,这是维持O(1)摊销push_back复杂性的唯一方法.

Answer 3

std::vector 的性能不佳是否是由于未调用 realloc 对数次数所致？

你的测试既不支持这个结论，也没有证明相反的结论。然而，我认为重新分配被称为线性次数，除非有相反的证据。

更新：您的新测试显然是反对您的非对数重新分配假设的证据。

我怀疑这是由于向量内部调用realloc太多次造成的。

更新：您的新测试表明，部分差异是由于重新分配造成的......但不是全部。我怀疑其余部分是由于优化器能够证明（但仅在非增长的情况下）数组值未使用，并选择根本不循环和写入它们。如果您要确保实际使用写入的值，那么我预计非增长数组将具有与保留向量类似的优化性能。

优化构建中的差异（保留代码和非保留向量之间）很可能是由于进行了更多的重新分配（与保留数组没有重新分配相比）所致。重新分配的次数是否过多是视情况和主观而定的。减少重新分配的缺点是由于过度分配而浪费更多空间。

请注意，重新分配大型数组的成本主要来自元素的复制，而不是内存分配本身。

在未优化的构建中，由于未内联扩展的函数调用，可能会产生额外的线性开销。

我怎样才能告诉 std::vector 几何增长？

标准要求几何增长。没有办法也没有必要告诉我们std::vector使用几何增长。

请注意，在这种情况下调用reserve一次可以工作，但在提前不知道push_back的数量的更一般情况下则不行。

push_back然而，提前未知数量的一般情况是非增长数组甚至不是一种选择的情况，因此其性能与一般情况无关。