为什么在做许多保留工作时C ++ STL向量要慢1000倍? [英] Why are C++ STL vectors 1000x slower when doing many reserves?

问题描述

我遇到了一个奇怪的情况.

I've run into a strange situation.

在我的程序中，我有一个循环，将一个大数据中的一堆数据组合在一起.我试图弄清楚为什么它运行这么慢，即使看起来我在做所有事情都可以在旅途中高效地分配内存.

In my program I have a loop that combines a bunch of data together in a giant vector. I was trying to figure out why it was running so slowly, even though it seemed like I was doing everything right to allocate memory in an efficient manner on the go.

在我的程序中，很难确定组合数据的最终向量应该有多大，但是每条数据的大小在处理时就已知.因此，我没有一次保留和调整大小的方法，而是在将每个数据块添加到较大的向量中时为其保留了足够的空间.那时我遇到了这个问题，可以使用下面的简单代码片段重复进行此操作:

In my program it is difficult to determine how big the final vector of combined data should be, but the size of each piece of data is known as it is processed. So instead of reserving and resizing the combined data vector in one go, I was reserving enough space for each data chunk as it is added to the larger vector. That's when I ran into this issue that is repeatable using the simple snippet below:

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中编译后，该测试的结果如下:

The results of this test, after compilation in Visual Studio 2017, are as follows:

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

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

Why is there the huge discrepancy in running times?

为什么多次调用 reserve ，然后调用 push_back ，要比调用 resize 的时间长1000倍，直接索引访问?

Why does calling reserve a bunch of times, followed by push_back take 1000x times longer than calling resize a bunch of times, followed by direct index access?

与天真的方法(根本不包括预分配)相比，它花费的时间可能长500倍，这有什么意义呢?

How does it make any sense that it could take 500x longer than the naive approach which includes no pre-allocations at all?

推荐答案

从什么意义上讲，它可能需要比原先更长的时间500倍天真的方法，根本不包含预分配?

How does it make any sense that it could take 500x longer than the naive approach which includes no pre-allocations at all?

那是你弄错的地方.您所说的幼稚"方法确实会进行预分配.它们只是在幕后完成，而且很少在对 push_back 的调用中完成.每次调用 push_back 时，它不仅会为另一个元素分配空间.它会分配一些当前容量的因素(通常在1.5倍至2倍之间).然后，在容量用完之前，无需再次分配.这比循环(每次添加50个元素而不考虑当前容量)进行分配的效率要高得多.

That's where you're mistaken. The 'naive' approach you speak of does do pre-allocations. They're just done behind the scenes, and infrequently, in the call to push_back. It doesn't just allocate room for one more element every time you call push_back. It allocates some amount that is a factor (usually between 1.5x and 2x) of the current capacity. And then it doesn't need to allocate again until that capacity runs out. This is much more efficient than your loop which does an allocation every time 50 elements are added, with no regard for the current capacity.

这篇关于为什么在做许多保留工作时C ++ STL向量要慢1000倍?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！