在我的程序中,我有一个循环,它将一堆数据组合在一个巨大的向量中.我试图找出它运行得如此缓慢的原因,尽管看起来我正在尽一切努力在旅途中以有效的方式分配内存.

在我的程序中,很难确定组合数据的最终向量应该有多大,但是每个数据的大小在处理时都是已知的.因此,我不是一次性保留和调整组合数据向量,而是为每个数据块保留足够的空间,因为它被添加到较大的向量中.那时我遇到了这个问题,可以使用下面的简单片段重复：

std::vector<float> arr1;
std::vector<float> arr2;
std::vector<float> arr3;
std::vector<float> arr4;
int numLoops = 10000;
int numSubloops = 50;

{
    // Test 1
    // Naive test where no pre-allocation occurs

    for (int q = 0; q < numLoops; q++)
    {
        for (int g = 0; g < numSubloops; g++)
        {
            arr1.push_back(q * g);
        }
    }
}

{
    // Test 2
    // Ideal situation where total amount of data is reserved beforehand

    arr2.reserve(numLoops * numSubloops);
    for (int q = 0; q < numLoops; q++)
    {
        for (int g = 0; g < numSubloops; g++)
        {
            arr2.push_back(q * g);
        }
    }
}

{
    // Test 3
    // Total data is not known beforehand,so allocations made for each
    // data chunk as they are processed using 'resize' method

    int arrInx = 0;
    for (int q = 0; q < numLoops; q++)
    {
        arr3.resize(arr3.size() + numSubloops);
        for (int g = 0; g < numSubloops; g++)
        {
            arr3[arrInx++] = q * g;
        }
    }
}

{
    // Test 4
    // Total data is not known beforehand,so allocations are made for each
    // data chunk as they are processed using the 'reserve' method

    for (int q = 0; q < numLoops; q++)
    {
        arr4.reserve(arr4.size() + numSubloops);
        for (int g = 0; g < numSubloops; g++)
        {
            arr4.push_back(q * g);
        }
    }
}

在Visual Studio 2017中编译后,此测试的结果如下：

Test 1: 7 ms
Test 2: 3 ms
Test 3: 4 ms
Test 4: 4000 ms

为什么运行时间存在巨大差异？

为什么调用保留很多次,然后push_back比调用resize多一倍,然后是直接索引访问？

它是如何理解它可能比原始方法(包括根本没有预分配)花费500倍更长的时间？