在C++循环中vector :: size()的性能问题

Question

在以下代码中:

std::vector<int> var;
for (int i = 0; i < var.size(); i++);

size()成员函数是为每个循环迭代调用的,还是仅调用一次？

Answer 1

从理论上讲,每次都会调用它,因为for循环:

for(initialization; condition; increment)
    body;

扩展到类似的东西

{
    initialization;
    while(condition)
    {
        body;
        increment;
    }
}

(注意花括号,因为初始化已经在内部范围内)

在实践中,如果编译器理解你的条件的一部分在循环的整个持续时间内是不变的并且它没有副作用,那么它可以足够聪明地将其移出.这通常strlen是在没有编写其参数的循环中完成的(类似编译器所知).

但必须指出的是,最后一个条件并不总是微不足道的证明; 通常,如果容器是函数的本地容器并且永远不会传递给外部函数,则很容易; 如果容器不是本地的(例如它通过引用传递 - 即使它是const)并且循环体包含对其他函数的调用,则编译器通常必须假设这些函数可能改变它,从而阻止长度计算的提升.

手动进行优化是值得的,如果你知道你的条件的一部分是"昂贵"来评估(并且这种条件通常不是,因为它通常归结为指针减法,几乎肯定是内联的).

编辑:正如其他人所说,通常使用容器最好使用迭代器,但是对于vectors来说它并不那么重要,因为对元素的随机访问operator[]保证是O(1); 实际上,对于向量,它通常是指针求和(向量基数+索引)和解引用对指针增量(在元素之前+ 1)和迭代器的解除引用.由于目标地址仍然相同,我不认为你可以从缓存局部性方面获得迭代器的东西(即使如此,如果你没有在紧密循环中走大数组,你甚至不应该注意到一种改进).

对于列表和其他容器,使用迭代器而不是随机访问可能非常重要,因为使用随机访问可能意味着每次遍历列表时,而递增迭代器只是指针取消引用.

Answer 2

它每次都被"调用",但我把调用放入引号,因为它实际上可能只是一个内联方法调用,所以你不必担心它的性能.

为什么vector<int>::iterator不用呢？

Answer 3

该size()成员函数被调用每一次,但是这将是一个非常糟糕的执行,不会内嵌它,一个奇怪的之一,它不会是一个固定数据的简单访问或两个指针的减法.
无论如何,在你描述你的应用程序并发现这是一个瓶颈之前,你不应该担心这些琐事.

但是,你应该注意的是:

1. 向量索引的正确类型是std::vector<T>::size_type.
2. 有些类型(例如一些迭代器)i++ 可能比它慢++i.

因此,循环应该是:

for(vector<int>::size_type i=0; i<var.size(); ++i)
  ...

Answer 4

你的问题的问题在于它没有任何意义。C++ 编译器将一些源代码翻译成二进制程序。要求是生成的程序必须根据 C++ 标准的规则保留代码的可观察效果。这段代码：

for (int i = 0; i < var.size(); i++); 

根本没有任何可观察到的效果。此外，它不会以任何方式与周围的代码交互，并且编译器可能会完全优化它；即没有生成对应的程序集。

为了使您的问题有意义，您需要指定循环内发生的情况。问题在于

for (int i = 0; i < var.size(); i++) { ... }

答案很大程度上取决于...实际情况。我相信@MatteoItalia 提供了一个非常好的答案，只需添加我所做的一些实验的描述。考虑以下代码：

int g(std::vector<int>&, size_t);

int f(std::vector<int>& v) {
   int res = 0;
   for (size_t i = 0; i < v.size(); i++)
      res += g(v, i);
   return res;
}

首先，即使调用var.size()几乎 100% 肯定会内联启用的优化，并且这种内联通常转化为两个指针的减法，但这仍然会给循环带来一些开销。如果编译器无法证明向量大小被保留（这通常是非常困难的，甚至是不可行的，例如在我们的例子中），那么您最终将得到不必要的load和sub（以及可能的shift）指示。-O3使用 GCC 9.2、和 x64生成的循环汇编为：

.L3:
    mov     rsi, rbx
    mov     rdi, rbp
    add     rbx, 1
    call    g(std::vector<int, std::allocator<int> >&, unsigned long)
    add     r12d, eax
    mov     rax, QWORD PTR [rbp+8] // loads a pointer
    sub     rax, QWORD PTR [rbp+0] // subtracts another poniter
    sar     rax, 2                 // result * sizeof(int) => size()
    cmp     rbx, rax
    jb      .L3

如果我们将代码重写如下：

int g(std::vector<int>&, size_t);

int f(std::vector<int>& v) {
   int res = 0;
   for (size_t i = 0, e = v.size(); i < e; i++)
      res += g(v, i);
   return res;
}

那么，生成的程序集更简单（因此更快）：

.L3:
    mov     rsi, rbx
    mov     rdi, r13
    add     rbx, 1
    call    g(std::vector<int, std::allocator<int> >&, unsigned long)
    add     r12d, eax
    cmp     rbx, rbp
    jne     .L3

向量大小的值简单地保存在寄存器中（rbp）中。

我什至尝试了不同的版本，其中向量被标记为const：

int g(const std::vector<int>&, size_t);

int f(const std::vector<int>& v) {
   int res = 0;
   for (size_t i = 0; i < v.size(); i++)
      res += g(v, i);
   return res;
}

令人惊讶的是，即使v.size()此处无法更改，生成的程序集也与第一种情况相同（带有附加的mov、sub和sar指令）。

现场演示就在这里。

另外，当我将循环更改为：

for (size_t i = 0; i < v.size(); i++)
   res += v[i];

v.size()然后，在汇编级别的循环内没有评估（指针的减法）。GCC 能够在这里“看到”，循环体不会以任何方式改变大小。