与递增一个单独的变量并将其索引到数组中相比，如何更快地递增和取消引用迭代器？

Question

为什么会这样：

for (auto & x : vec) { /* do stuff with x */ }

比

快

for (int i = 0; i < v.size(); ++i) { /* do stuff with v[i] */ }

正如我的标题所说，有人告诉我递增和取消引用迭代器比递增一个单独的变量并将其索引到数组中更快，但不明白为什么？

究竟是什么让它变得更快？

我试着逐步查看发生了什么，这就是我想到的

// pseudo instructions
// iterator

increment iterator
    e.g., if the object is 3 integers you would increment the iterator
    by 12
dereference this iterator

// pseudo instructions
// array

increment array index
    add 1 to index counter
multiply by size of object 
    e.g., if the object is 3 integers, you multiply by 12
dereference the array

遍历一个数组似乎很简单。您只是在执行以下操作：

[offset + index * size] ; An array takes this form in assembly

如果你有一个整数数组，它看起来像这样

[rbp - 16 + rdi * 4] ; rbp - 16 is the offset
                     ; rdi is the index
                     ; 4 is the size of the integer

数组迭代看起来相当微不足道，所以我不明白取消引用迭代器的速度有多快。

Answer 1

它可能更快的唯一方法，至少在未优化的代码中是因为您在每次迭代开始时调用 size() 成员函数，这实际上取决于容器和它使用的迭代器类型。否则，对 array-like 容器使用迭代器与使用指针算法相同，哪个顺序更快取决于优化。如果 i 的类型大小合适，不会因值的不同宽度而混淆编译器，这也会有所帮助。

Range-based for 循环比 index-based 有更多的失效问题，但如果您正在修改同一个容器。因为它是这样编码的：

range-based for语句

for ( for-range-declaration : for-range-initializer ) statement

相当于

{
    auto &&__range = for-range-initializer ;
    auto __begin = begin-expr ;   
    auto __end = end-expr ;
    for ( ; __begin != __end; ++__begin ) {
        for-range-declaration = *__begin;
        statement
    }
}

如您所见，范围开始和结束的迭代器在循环之前求值，对范围采取的任何使它们无效的操作都会调用 UB。

如果我们谈论容器的通用概念而不仅仅是 std::vector，对于某些容器来说 operator[] 可能比迭代器增量更昂贵。只有少数标准容器具有 operator[] 的固定成本，而在 views\ranges 的情况下，其成本通常更大，non-constant 或 non-linear。递增迭代器的成本往往是恒定的或线性的。成本通常会在性能测试期间公布或查明。

所以主要问题不是性能而是代码的正确性，并且使用 range-based for 循环表明范围是改变了它。故意引起这样的更改变得更加困难，因为您可以访问的只是元素的引用或副本。这样做的尝试是显而易见的，这将是对原始范围的一些使用。它还保存了 begin-expr/end-expr.

的样板代码

通常 for-loop 在 i < v.size() 中调用大小可能表明 size() 可能会在执行期间发生变化。如果它是 true 并且发生在循环体的中间，您可能会发现索引从该点开始越界。

在不知道代码作者的情况下审查代码时，如果我寻找此类更改的来源，从我看到它的第一行紧随其后的那一刻起，每个此类循环都是检测到的错误或 out-of-bound 访问时崩溃的可疑对象通过一些 non-transparent 代码。

Answer 2

for (auto & x : vec) { /* do stuff with x */ } 比 for (int i = 0; i < v.size(); ++i) { /* do stuff with v[i] */ } 快吗？

当你绝对地谈论更快时，你基本上总是错的。每个案例都是不同的。堆栈对齐方式的一个简单更改可以使代码速度产生多达 40% 的差异，这比通常 -O0 和 -O2 之间的差异还要大。因此，只需在调用图中较早的某个函数中添加一个局部变量就可以完全逆转更快的过程。

始终使用真实输入来衡量代码的性能！

也就是说，for 循环在每次迭代中都会调用 v.size()。自动循环不会那样做。编译器可能会也可能不会意识到 v 的变化在循环期间永远不会改变。否则会导致速度变慢。

但是如果它用两种方式编写循环应该变成这样（在 x86_64 上）：

size_t count = vec.end() - vec.begin();
T *it = vec.begin();
while (count-- > 0) {
    /* do stuff with *it */
    ++it;
}

优化良好的循环通常采用这种形式。或者 a do{}while(--count != 0) 代码在循环外，如果它应该运行零迭代则不进入它。或者 do{}while(++ptr < endptr) 使用 it 本身作为循环计数器，避免实际计算 pointer-subtraction.

的计数

您认为数组访问应采用 [rbp - 16 + rdi * 4] 形式的想法是错误的。虽然手工编写是完全合理的，但生成的机器代码比每个循环使用一次 [rdi] 和 add rdi, 4 更大。这将节省指令缓存，尤其是在指针被多次访问时，并最终变得更快。 > 0 测试在处理索引时也比 < end 简单，所以如果编译器使用单独的 count 寄存器，它可以做 dec rcx / jnz .loop_top（英特尔 1 微指令）而不是 inc/cmp/jne（需要第二个寄存器来限制，英特尔和 AMD 是 2 微指令，macro-fusing cmp+jcc).

总的来说，如果两种形式中的一种比另一种更快，那么要么是优化失败（同样的方式），要么是 v.size() 调用无法消除。

与递增一个单独的变量并将其索引到数组中相比，如何更快地递增和取消引用迭代器？

How is incrementing and dereferencing the iterator faster than incrementing a separate variable and indexing it into the array?

c++

foreach

iterator

x86-64