Почему изменение размера вектора быстрее, чем зарезервировать и push_back?

Question

Я проводил несколько быстрых тестов с участием std:vector. Я начинаю с относительно небольшого вектора в 100 дюймов и вызываю различные методы для его заполнения миллионами. Большинство моих функций включают очистку элементов и добавление элементов снова или создание нового вектора и перемещение или замена его на исходный вектор. У меня также есть функция, которая просто изменяет размер вектора и перезаписывает элементы.

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

Я знаю, что std::vector::resize() изменит размер вектора, чтобы он содержал новый счет. Согласно cppreference :

Если текущий размер меньше чем count, дополнительные элементы добавляются и инициализируются с копиями значения.

resize() должно составлять на 100 единиц меньше, чем другие функции. Поэтому я удивлен разницей в скорости. Я думал, что resize() выделит и инициализирует новые элементы, в то время как резерв просто выделит память.

#include <algorithm>
#include <chrono>
#include <iostream>

constexpr int InitialSize = 100;
constexpr int NewSize = 1000000;

void overwrite(std::vector<int>& v)
{
  v.resize(NewSize);
  for (int i = 0; i < NewSize; ++i)
  {
      v[i] = i;
  }
}

void clear(std::vector<int>& v)
{
    v.clear();
    v.reserve(NewSize);
    for (int i = 0; i < NewSize; ++i)
    {
        v.push_back(i);
    }
}

void swap(std::vector<int> &v)
{
    std::vector<int> vnew;
    vnew.reserve(NewSize);
    for (int i = 0; i < NewSize; ++i)
    {
        vnew.push_back(i);
    }
    v.swap(vnew);
}

void move(std::vector<int> &v)
{
    std::vector<int> vnew;
    vnew.reserve(NewSize);
    for (int i = 0; i < NewSize; ++i)
    {
        vnew.push_back(i);
    }
    v = std::move(vnew);
}


int main()
{
    {
        std::vector<int> v(InitialSize);
        std::iota(v.begin(), v.end(), 1);
        auto start = std::chrono::high_resolution_clock::now();
        move(v);
        auto finish = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double, std::milli> elapsed = finish - start;
        std::cout << "Move - elapsed time: " << elapsed.count() << " ms" << std::endl;
    }

    {
        std::vector<int> v(InitialSize);
        std::iota(v.begin(), v.end(), 1);
        auto start = std::chrono::high_resolution_clock::now();
        clear(v);
        auto finish = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double, std::milli> elapsed = finish - start;
        std::cout << "Clear - elapsed time: " << elapsed.count() << " ms" << std::endl;
    }

    {
        std::vector<int> v(InitialSize);
        std::iota(v.begin(), v.end(), 1);
        auto start = std::chrono::high_resolution_clock::now();
        swap(v);
        auto finish = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double, std::milli> elapsed = finish - start;
        std::cout << "Swap - elapsed time: " << elapsed.count() << " ms" << std::endl;
    }

    {
        std::vector<int> v(InitialSize);
        std::iota(v.begin(), v.end(), 1);
        auto start = std::chrono::high_resolution_clock::now();
        overwrite(v);
        auto finish = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double, std::milli> elapsed = finish - start;
        std::cout << "Overwrite - elapsed time: " << elapsed.count() << " ms" << std::endl;
    }
    return 0;
}

Вывод:

Move - elapsed time: 14.6284 ms
Clear - elapsed time: 17.5072 ms
Swap - elapsed time: 12.9111 ms
Overwrite - elapsed time: 5.19079 ms

LIVE

Quick Bench результаты .

Может кто-нибудь объяснить, что здесь происходит?

Answer 1

push_back является более дорогой операцией, чем доступ на основе индекса, даже если резервирование было заранее выполнено резервом.

1. push_back должно позаботиться о указателе конца, чтобы векторный размер можно было правильно вычислить
2. push_back проверит наличие необходимости в реальной операции. По сути, прогноз ветвления.
3. push_back приведет к тому, что копирование (или перемещение) значения будет отодвинуто назад. В случае int, это не должно вызывать разницы в производительности.

Если вы видите преобразование сборки (взятое из рассматриваемой ссылки на Godbolt), операция индекса - это не ветвящаяся последовательность нескольких ходов и операция сдвига, в то время как push_back гораздо более сложный. В долгосрочной перспективе l oop (1000000 в данном примере) эта разница будет иметь значение. Уровень оптимизации компилятора может определенно влиять на разницу.

Для оператора индекса []

    push    rbp
    mov     rbp, rsp
    mov     QWORD PTR [rbp-8], rdi
    mov     QWORD PTR [rbp-16], rsi
    mov     rax, QWORD PTR [rbp-8]
    mov     rax, QWORD PTR [rax]
    mov     rdx, QWORD PTR [rbp-16]
    sal     rdx, 2
    add     rax, rdx
    pop     rbp
    ret

Для push_back

    push    rbp
    mov     rbp, rsp
    sub     rsp, 16
    mov     QWORD PTR [rbp-8], rdi
    mov     QWORD PTR [rbp-16], rsi
    mov     rax, QWORD PTR [rbp-8]
    mov     rdx, QWORD PTR [rax+8]
    mov     rax, QWORD PTR [rbp-8]
    mov     rax, QWORD PTR [rax+16]
    cmp     rdx, rax
    je      .L73
    mov     rax, QWORD PTR [rbp-8] // When allocation is not needed
    mov     rcx, QWORD PTR [rax+8]
    mov     rax, QWORD PTR [rbp-8]
    mov     rdx, QWORD PTR [rbp-16]
    mov     rsi, rcx
    mov     rdi, rax
    call    void std::allocator_traits<std::allocator<int> >::construct<int, int const&>(std::allocator<int>&, int*, int const&)
    mov     rax, QWORD PTR [rbp-8]
    mov     rax, QWORD PTR [rax+8]
    lea     rdx, [rax+4]
    mov     rax, QWORD PTR [rbp-8]
    mov     QWORD PTR [rax+8], rdx
    jmp     .L75
.L73:   // When allocation is needed
    mov     rax, QWORD PTR [rbp-8]
    mov     rdi, rax
    call    std::vector<int, std::allocator<int> >::end()
    mov     rcx, rax
    mov     rdx, QWORD PTR [rbp-16]
    mov     rax, QWORD PTR [rbp-8]
    mov     rsi, rcx
    mov     rdi, rax
.L75:
    nop
    leave
    ret

Answer 2

Может кто-нибудь объяснить, что здесь происходит?

overwrite принципиально отличается от других, потому что вы никогда не звоните push_back, который должен проверить на изменение размера, что делает l oop намного сложнее.

Остальные три в основном эквивалентны (за вычетом постоянной разницы во времени) и будут работать по-разному в зависимости от оптимизации, от того, насколько хорошо компилятор выполняет свою работу, и от реализации стандартной библиотеки.

Если вам очень повезет, оптимизатор может увидеть, что изменение размера никогда не произойдет, и вести себя как overwrite.