为什么调整向量大小比保留和push_back更快？

Question

我进行了一些涉及 std::vector 的快速基准测试。我从一个相对较小的100个整数的向量开始，并调用多种方法来填充它，使它包含1,000,000个整数。我的大部分函数都涉及清除元素并再次添加元素或创建新向量并将其移动或交换原向量。我还有一个函数只是调整向量的大小并覆盖元素。

你可以在下面的代码中看到这些函数。有趣的是，调整向量的大小并覆盖元素是最快的。我认为在推入元素之前保留内存会提高性能。

我知道 std::vector::resize() 会重新调整向量大小以包含新的计数。根据cppreference：

如果当前大小小于计数，则附加并初始化值的副本。

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

点击此处查看实时结果

快速测试结果。

有人能解释一下这里到底发生了什么吗？

- jignatius

---

resize 可以使用一些 avx 优化的 memset 更高效地批量初始化成员，而 push_back 则会逐个初始化它们。 - Tarek Dakhran

我没有看到任何编译标志。在godbolt上默认进行了优化吗？ - Jack

你有开启优化编译吗？比如 -O3。 - selbie

除了编译标志之外，如果将覆盖测试移动到第一个位置，则结果会发生变化，以至于覆盖速度更慢。我猜这个基准测试并不真正可用。 - Jack

你只测试了 int。我怀疑使用非平凡类型会触发不同的优化路径并产生截然不同的结果。此外，一定要多次重复计时实验以获得结果的可信度。作为经验法则，你不应该少于20次重复实验。而且你应该像其他评论中建议的那样预热测试。 - bitmask

Answer 1

即使已经通过reserve处理了分配，push_back操作仍比基于索引的访问昂贵。

1. push_back需要管理末尾指针，以便正确计算向量大小。
2. push_back将检查是否需要重新分配。实际上是一个分支预测。
3. 在推入值时，push_back会导致值的复制（或移动）。对于int类型，这不应该导致性能差异。

如果查看汇编转换（从问题中给出的godbolt链接获取），索引操作是非分支的一系列移动和移位操作，而push_back则涉及更多内容。在长时间运行的循环（例如给定示例中的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

- nkvns

Answer 2

有人能解释一下这里发生了什么吗？

与其他操作不同，overwrite 操作基本上是不同的，因为您从未调用需要检查大小调整的 push_back，这使得循环更加复杂。

其他三个操作基本上是等效的（除了常数时间差异），并且将根据优化、编译器的工作质量和标准库实现而有所不同。

如果你非常幸运，优化器可能能够看到调整大小永远不会发生，并像 overwrite 一样表现。

- Acorn

---

是的，push_back()必须检查大小是否小于容量，否则需要重新分配内存。这是overwrite()和其他方法之间的主要区别。我试图通过预先设置容量来避免重新分配内存。然而，我本以为大小检查只是一个小差异。 - jignatius

@jignatius 的意思是，即使重新分配在运行时不会发生，优化器仍然能看到处理它的所有代码，并且可能无法将循环简化为“overwrite”的平凡循环的等效形式。如果优化器未到达简化的循环，则也无法应用其余的优化。 - Acorn

即使分支预测是完美的或被优化掉，对于int类型而言，push_back()本质上涉及两个赋值操作，因此成本大约应该是两倍：它需要更新末尾指针（或大小成员）！（当然，编译器也可以将其优化掉；实际上，除了打印时间之外，它可能什么都不做，因为所有传输的数据都没有可观察的效果。这就是基准测试的问题所在。） - Peter - Reinstate Monica