Почему векторы C++ STL в 1000 раз медленнее при выполнении большого количества резервов?

Question

Я столкнулся со странной ситуацией.

В моей программе у меня есть цикл, который объединяет кучу данных в гигантский вектор. Я пытался понять, почему он работает так медленно, хотя мне казалось, что я делаю все правильно, чтобы эффективно распределять память на ходу.

В моей программе трудно определить, насколько большим должен быть конечный вектор объединенных данных, но размер каждого фрагмента данных известен по мере их обработки. Поэтому вместо того, чтобы резервировать и изменять размер объединенного вектора данных за один раз, я резервировал достаточно места для каждого блока данных, поскольку он добавляется к большему вектору. Вот когда я столкнулся с этой проблемой, которую можно повторить, используя простой фрагмент ниже:

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

Почему существует огромное расхождение во времени выполнения?

Почему звонит reserve кучу раз, а затем push_back принимать в 1000 раз дольше, чем звонить resize кучу раз с последующим прямым доступом к индексу?

Как это имеет смысл, что это может занять в 500 раз больше, чем наивный подход, который вообще не включает в себя предварительное распределение?

Answer 1

Как это имеет смысл, что это может занять в 500 раз больше, чем наивный подход, который вообще не включает в себя предварительное распределение?

Вот где ты ошибаешься. "Наивный" подход, о котором вы говорите, делает предварительное распределение. Они просто сделаны за кулисами, и нечасто, в призыве к push_back, Это не просто выделить место для еще одного элемента каждый раз, когда вы звоните push_back, Он выделяет некоторое количество, которое является фактором (обычно между 1,5x и 2x) текущей емкости. И тогда ему не нужно выделять снова, пока эта емкость не исчерпается. Это намного эффективнее, чем ваш цикл, который выполняет распределение каждый раз, когда добавляется 50 элементов, без учета текущей емкости.

Answer 2

Ответ @ Бенджамина Линдли объясняет способность std::vector, Тем не менее, именно по этой причине 4-й тестовый пример такой медленный, фактически это деталь реализации стандартной библиотеки.

[vector.capacity]

резерв пустот (size_type n);

...

Эффекты: директива, которая информирует вектор о запланированном изменении размера, чтобы соответствующим образом управлять распределением памяти. После Reserve(), Capacity() больше или равна аргументу резерва, если происходит перераспределение; и равен предыдущему значению емкости () в противном случае. Перераспределение происходит в этой точке тогда и только тогда, когда текущая емкость меньше, чем аргумент резерва ().

Таким образом, стандарт C++ не гарантирует, что после reserve() для большей емкости фактическая емкость должна быть запрошенной. Лично я думаю, что для реализации не является необоснованным следовать какой-то конкретной политике, когда получен такой запрос большей емкости. Тем не менее, я также проверил на своей машине, кажется, что STL делает самое простое.