优化“for”循环

Question

std::vector<int> someVector;    
for (unsigned int i = 0; i < someVector.size(); i++)
{
   // do something
}

someVector.size()的值是否每次都会被计算？

- Maria Ines Parnisari

---

为什么不生成汇编代码并自行检查？ - Alok Save

很大程度上取决于您的编译器和优化标志。您还可以查看http://herbsutter.com/2013/05/13/gotw-2-solution-temporary-objects/（并没有真正回答您的问题，但会给您一些提示）。 - Zeta

别听Alok的建议，那是一个糟糕的建议。查看代码只会告诉你编译器实际上做了什么，而你可能更关心标准规定了什么。循环的终止条件会在每次迭代中被评估，因此如果它具有副作用，它们将发生。如果你调用的函数碰巧没有副作用，而且你在循环内部没有做任何产生副作用的事情，并且如果编译器足够聪明地弄清楚了所有这些，它可能优化掉这个调用，但那是一个大大的“如果”。最好自己操作。 - Lee Daniel Crocker

应该每次调用size()，因为在执行循环时，someVector可能会被另一个线程修改。 - Jari Karppanen

@LeeDanielCrocker 我会这样说：1. vector::size 是 const 的，所以如果满足上述条件，这可能是提示编译器仅调用一次的线索；2. 我无法想象出循环遍历向量并修改其大小的情况。我的意思是，确实有 for (i = 0; i < 10; i++) v.push_back(i);，但它不依赖于向量的大小，并且在枚举时修改它真的是一个坏主意（为了画出不太好的类比，在 Objective-C 中，NSMutableArray 明确禁止这样做并抛出异常——因为这真的是无意义的）。 - user529758

Answer 1

我已经使用GCC explorer检查了一下：

输入的代码：

#include<vector>

int sum(const std::vector<int> & someVector) {
  int s = 0;
  for (int i = 0; i < someVector.size(); i++) {
    s += someVector[i];
  }
  return s;
}

int main() {
  std::vector<int> someVector;
  return sum(someVector);
};

sum()函数所生成的汇编代码：

  movq  (%rdi), %rcx
  movq  8(%rdi), %rdx
  xorl  %eax, %eax
  cmpq  %rcx, %rdx
  je    .LBB0_3
  subq  %rcx, %rdx
  sarq  $2, %rdx
  xorl  %eax, %eax
  xorl  %esi, %esi
.LBB0_2:                                # =>This Inner Loop Header: Depth=1
  addl  (%rcx,%rsi,4), %eax
  incq  %rsi
  cmpq  %rdx, %rsi
  jb    .LBB0_2
.LBB0_3:                                # %._crit_edge
  ret

即，大小保存在%rdx中 -- 每次没有调用size()。

正如其他人已经指出的，结果可能取决于

• 您的编译器，
• 优化设置和
• 您在循环中实际执行的操作（点击上面的gcc explorer链接自行尝试）。

而且，在不计算任何内容的情况下，整个循环都被优化掉了。

- Stefan Haustein

---

代码与 OP 的代码也有很大不同，这种情况下可以安全地假设进行了优化：您拥有向量的 const 引用。如果没有额外的 sum 函数，查看 OP 示例的汇编将会很有趣。 - juanchopanza

如果在循环中没有执行任何操作，整个循环将被消除。如果我去掉const &，代码的相关部分保持不变。我猜编译器会发现它仍然可以是一个const引用。 - Stefan Haustein

Answer 2

一些Vector的长度值是否每次都要计算？

可能是的，这取决于循环的内容和其他许多因素。例如，向量的大小在循环内部可能会被修改。那么你的编译器必须能够发现这种情况。因此，必须满足一些条件才能优化掉它。

如果您要求在循环中仅调用一次std::vector::size()，则最好（也是唯一）的策略是通过对代码进行微不足道的修改来回避这个问题：

std::vector<int> someVector;    
for (unsigned int i = 0, length = someVector.size(); i < length; ++i)
{
   // do something
}

- juanchopanza

---

我知道我可以这样做，但我在想那是否真的必要。 - Maria Ines Parnisari

@l19 嗯，你不能完全确定它会被优化掉。它可能会被优化掉，但不一定（例如向量的大小可以在循环内部改变）。 - juanchopanza

你应该将上面的评论作为你回答的一部分添加进去。 - srikanta

@srikanta 很好的观点，谢谢。我稍微扩展了一下答案。 - juanchopanza

“最佳（也是唯一）策略” - 不完全如此。如果没有从头到尾迭代的要求（在大多数情况下并不重要），更清晰的方法是从最后一个元素开始，使用i--进行迭代。 - SomeWittyUsername

Answer 3

这取决于编译器的优化。

它可能是循环优化（如果可能的话，不会提到类似volatile的东西）

编译器将把与循环无关的数据放在循环外面。

因此，它可能会生成类似以下的内容

int length = someVector.length();
for (unsigned int i = 0; i < length; i++)
{
    // do something
}

有许多编译器优化技术可以使用。

在C++中，默认情况下有一些“纯函数”，例如string.length()，它总是被优化的。我不确定vector.size是否属于这种情况。

- Dineshkumar