42

在以下代码中：

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

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

4

10 回答 10

49

理论上，每次都会调用它，因为一个 for 循环：

for(initialization; condition; increment)
    body;

扩展到类似的东西

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

（注意花括号，因为初始化已经在内部范围内）

在实践中，如果编译器知道你的条件的一部分在循环的所有持续时间内是不变的并且它没有副作用，它可以足够聪明地将它移出。这通常strlen在没有写入其参数的循环中使用诸如此类的事情（编译器很清楚）来完成。

但是必须注意，最后一个条件并不总是可以证明的。一般来说，如果容器是函数的本地容器并且从不传递给外部函数，这很容易；如果容器不是本地的（例如它是通过引用传递的——即使它是const）并且循环体包含对其他函数的调用，编译器通常必须假设这些函数可能会改变它，从而阻止长度计算的提升。

如果您知道您的条件的一部分是“昂贵的”评估（并且这种条件通常不是，因为它通常归结为指针减法，这几乎肯定是内联的），那么手动进行优化是值得的。

编辑：正如其他人所说，通常对于容器，最好使用迭代器，但对于vectors 来说它并不那么重要，因为随机访问元素 viaoperator[]保证为 O(1); 实际上对于向量，它通常是指针总和（向量基数+索引）和解引用与指针增量（前一个元素+1）和迭代器的解引用。由于目标地址仍然相同，我认为您不能从迭代器中获得缓存位置方面的东西（即使是这样，如果您不是在紧密循环中遍历大数组，您甚至不应该注意到这样种改进）。

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

于 2010-10-10T18:43:36.197 回答
6

它每次都被“调用”，但我把调用放在引号中，因为它实际上可能只是一个内联方法调用，所以你不必担心它的性能。

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

于 2010-10-10T18:40:14.930 回答
5

size()成员函数每次都会被调用，但如果不将其内联，这将是一个非常糟糕的实现，而且它不是对固定数据的简单访问或两个指针的减法，这是一个奇怪的实现。
无论如何，在您分析您的应用程序并发现这是一个瓶颈之前，您不应该担心这些琐碎的事情。

但是，您应该注意的是：

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

因此，循环应该是：

for(vector<int>::size_type i=0; i<var.size(); ++i)
  ...
于 2010-10-10T18:41:22.157 回答
2

每次都必须调用它，因为 size() 每次都可能返回不同的值。

因此，没有什么大的选择，它只是必须的。

于 2010-10-10T18:42:04.350 回答
2

你的问题的问题是它没有任何意义。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 能够在这里“看到”循环体不会以任何方式改变大小。

于 2019-10-25T06:44:07.490 回答
1

正如其他人所说

  • 语义必须就像每次都被调用一样
  • 它可能是内联的，并且可能是一个简单的函数

在这之上

  • 一个足够聪明的优化器可能能够推断出它是一个没有副作用的循环不变量并完全忽略它（如果代码是内联的，这会更容易，但如果编译器进行全局优化，即使不是这样也可能）
于 2010-10-10T18:44:49.193 回答
1

但它可以通过这种方式完成（假设这个循环只打算读/写而不实际改变向量的大小）： 

for(vector<int>::size_type i=0, size = var.size(); i < size; ++i) 
{
//do something
}

在上面的循环中，您只需调用一次 size 就可以独立于 size 是否内联。

于 2010-10-10T18:53:42.517 回答
1

我认为如果编译器可以最终推断出变量var在“循环体”内没有被修改

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

那么上面的内容可以转换为等价的东西

const size_t var_size = var.size();
for( int i = 0; i < var_size; i++ ) { 
    // loop body
}

但是，我不是很确定，所以欢迎评论:)

还，

  • 在大多数情况下，size()成员函数是内联的，所以这个问题不需要担心

  • 这个问题可能同样适用于end()始终用于基于迭代器的循环，即it != container.end()

  • 请考虑使用size_t或vector<int>::size_type类型i[参见下面史蒂夫·杰索普的评论。]

于 2010-10-10T19:12:34.433 回答
0

正如其他人所说，编译器应决定如何处理实际编写的代码。关键是它每次都被调用。但是，如果您想获得性能提升，最好在编写代码时考虑一些因素。您的案例就是其中之一，还有其他案例，例如这两段代码之间的区别：

for (int i = 0 ; i < n ; ++i)
{
   for ( int j = 0 ; j < n ; ++j)
       printf("%d ", arr[i][j]);
   printf("\n");
}
for (int j = 0 ; j < n ; ++j)
{
   for ( int i = 0 ; i < n ; ++i)
       printf("%d ", arr[i][j]);
   printf("\n");
}

不同之处在于，第一个不会对每个引用过多地更改 ram 页面，但另一个会耗尽你的缓存和 TLB 和其他东西。

内联也无济于事！因为调用函数的顺序将保持为 n（向量的大小）次。虽然它在某些地方有所帮助，但最好的办法是重写你的代码。

但！如果你想让编译器做它对你的代码的优化永远不要放 volatile，像这样：

for(volatile int i = 0 ; i < 100; ++i)

它会阻止编译器进行优化。如果您需要另一个性能提示，请使用 register 而不是 volatile。

for(register int i = 0 ; i < 100; ++i)

编译器将尽量不将 i 从 CPU 寄存器移动到 RAM。不能保证它可以做到，但它会做到最好；）

于 2010-10-10T19:42:23.167 回答
0

对其进行了 900k 次迭代测试它的预先计算大小需要 43 秒，使用 size() 调用需要 42 秒。

如果您保证向量大小在循环中不会改变，最好使用预先计算的大小，否则别无选择，必须使用 size()。

#include <iostream>
#include <vector>

using namespace std;

int main() {
vector<int> v;

for (int i = 0; i < 30000; i++)
        v.push_back(i);

const size_t v_size = v.size();
for(int i = 0; i < v_size; i++)
        for(int j = 0; j < v_size; j++)
                cout << "";

//for(int i = 0; i < v.size(); i++)
//      for(int j = 0; j < v.size(); j++)
//              cout << "";
}
于 2018-06-28T05:28:02.723 回答