在循环中反复调用容器的size()方法是否不好？

Question

出于效率原因，我总是避免编写像这样的循环：

for(std::size_t i = 0; i < vec.size(); ++i) { ... }

其中vec是一个STL容器。我不会像这样去做：

const std::size_t vec_size = vec.size();
for(std::size_t i = 0; i < vec_size; ++i) { ... }

或者使用容器迭代器。

但是第一个解决方案有多糟糕呢？我记得在 Meyers 的书中读到过，它将是二次的而不是线性的，因为向量不知道其大小并且必须重复计数。但是现代编译器不会检测到这一点并对其进行优化吗？

- Frank

---

你要找的那个 Meyers 参考资料是 Effective STL 的第4项：调用 empty 而不是检查 size 是否为零。 - Billy ONeal

你为什么要首先编写这个循环？为什么不使用STL算法呢？ - jalf

@jalf 有时候函数等效太繁琐，你得写一个特殊的函数对象等等。 - Frank

for(std::size_t i = 0, i_size = vec.size(); i < i_size; ++i) <- 问题解决了 =) - Viktor Sehr

@Viktor：当然可以，但其实并不必要。从生成的汇编代码来看，编译器已经为你解决了这一切。 - Evan Teran

Answer 1

vector::size() 是常数时间复杂度的，通常实现为一个被优化掉的平凡内联函数。不要费心手动优化它。

- Marcelo Cantos

---

我不会点踩，但我不同意，大多数情况下它被实现为减法，在性能关键的部分中进行优化可能是值得的。 - Viktor Sehr

作为一个减法和除法（数据类型的大小），这使情况变得更糟。 - Jim Buck

（假设除法不简单到可以使用移位等方式实现。） - Jim Buck

我已经进行了基准测试，结果表明编译器将为这种类型的代码发出相同的代码(因为在这篇帖子中有一个论点: https://dev59.com/SUbRa4cB1Zd3GeqP1IV9#535233)。标准指定size()是一个`const`函数。因此，只要在循环中只使用`const`操作，它可以知道它只需要调用一次。通过查看汇编代码，它确实做到了。 - Evan Teran

@Evan：非常感谢你替我辩论了这个观点:-)。 我想补充一点的是，这取决于您在循环内部执行的操作。 如果进行了非内联函数调用，则优化程序放弃竞争的可能性很大。 但即使如此，绝大多数类型大小都是2的幂，这使得大小计算非常便宜，即使不是这种情况，好的编译器也足够聪明，会执行乘法而不是除法（至少g++这样）。 - Marcelo Cantos

Answer 2

我记得在 Meyers 的书中读到，由于向量不知道其大小并且需要重复计数，因此它将是二次的而不是线性的。

你把 vector 和 list 搞混了。 vector 的大小值保存在向量中；list 的大小需要遍历实际列表。

- Billy ONeal

---

只是出于好奇，为什么不能将相同的原则应用于std::list呢？也就是说，存储列表的大小，并相应地增加/减少。 - Steve Guidi

因为 std::list::splice 要求具有常数时间复杂度，并且必须能够使用任意迭代器进行操作。如果要获取距离，就必须遍历整个列表，这会使时间复杂度变为线性而不是常数。 - Billy ONeal

以上文字的修改：在上文中，“splice”不一定需要在常数时间内完成，但它有可能会。如果“splice”被实现为常数时间，则“size”则不能保证在常数时间内。如果“size”被实现为常数时间，那么“splice”则不能保证在常数时间内。选择哪个取决于STL的具体实现方式。 - Billy ONeal

@jalf：这意味着我们不会有一个常数时间的splice吗？考虑到“splice”是使用列表的罕见原因之一，这似乎有点浪费... - Matthieu M.

@James：http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3090.pdf 第778页：复杂度：如果&x == this，则为常数时间；否则为线性时间。 - Billy ONeal

Answer 3

考虑下面这个愚蠢的函数：

void sum (vector<int>& vec, int* sumOut)
{
    *sumOut = 0;
    for(std::size_t i = 0; i < vec.size(); ++i)
    {
        *sumOut += vec[i];      
    }
}

生成的实际汇编代码将取决于编译器和vector的实现，但我认为在大多数情况下，编译器必须每次通过循环重新读取vector的大小。这是因为sumOut指针可能与向量的大小的内部存储（假设vector将其大小存储在int中）重叠，因此循环可以更改大小。如果您频繁调用此类函数，则可能会增加许多周期，因为您正在触摸比所需更多的内存。

三种可能的解决方案是:

1. 将大小存储在本地变量中。 理想情况下，这个大小将会被 存储在寄存器中，避免接触 内存。即使它必须 放在堆栈上，编译器 应该能够更有效地排序 加载/存储。

2. 在输出指针上使用__restrict。这告诉编译器 指针不可能与其他任何东西重叠，因此对它的写入不需要重新加载其他任何东西。

3. 反转循环。终止 条件现在检查是否为0， 所以不再调用vec.size()。

其中，我认为#1是最干净的，但有些人可能更喜欢#3。#2可能是最不易读的，但比其他方法更快（因为它意味着可以更有效地读取向量的数据）。

有关别名的更多信息，请参见Christer Ericson的GDC内存优化演示；里面有一个几乎与此相同的例子。

- celion

---

我想补充一点，与普遍的看法相反，在你的例子中，如果向量引用本应是const vector<int>&，那也没关系，因为const引用意味着你不能使用该引用来更改数据，而不是数据是常量。对于优化器来说，const引用只是一个引用。引用的const性质是为了帮助程序员，而不是编译器...即使在我看来，这个概念是否真正有所帮助还是值得怀疑的，而不仅仅是额外的负担... - 6502

Answer 4

判断编译器是否优化掉某些内容的最简单方法是比较汇编语言编译器输出。

尽管如此，这两个代码块实际上并不等价。如果在迭代过程中向量的大小发生了变化怎么办？编译器必须非常聪明才能证明向量的大小不可能改变。

现实世界中，这种微小的优化真的值得额外的努力吗？vec.size()只返回一个存储的值。它不会重新计算长度。

- Borealid

---

我一直看到这个建议，但它有一个致命的缺陷：我们中许多人不知道汇编语言，因此无法理解编译后的输出。如果您知道汇编语言，那太好了。另一方面，如果我们知道汇编语言，我们可能根本不会首先问这个问题。 - Billy ONeal

@Billy，我无法想象在一个我至少不了解汇编语言基础的平台上进行C++编程 - 如果你不知道它，请花几天时间学习基础知识，这是非常值得努力的。 - anon

@Borealid：编译器实际上可以确定大小不会改变，而且很容易。它只需要保证循环内对vec的任何操作都是const（并且不引用循环外创建的非const变量，因为它们可能与vec别名）。因此，像求和、打印等简单的只读操作很容易确定整个循环的const性。 - Evan Teran

@Evan Teran：如果有多个线程访问该结构，或者它驻留在共享内存区域中怎么办？这并不简单。 - Borealid

@Borealid：c++03 完全不知道线程和共享内存。大多数编译器都会忽略它们的存在，只有少数例外。就优化而言，编译器完全可以像这些问题不存在一样进行优化，除了一些特殊情况，它们就是这么做的。 - Evan Teran

@Boreliad：如果大小在循环期间可以更改，那么不重新读取大小是你最不用担心的问题。正如Evan所说，编译器应该忽略这种可能性，除非另有指示。 - peterchen