为何std::reverse迭代后遍历比反向迭代器性能更优？

测试代码 #

#include <iostream>
#include <vector>
#include <windows.h>
using namespace std;
int v_size = 100000;
void foo1() {
    vector<int>test(v_size, 1);
    auto start = GetTickCount();
    reverse(test.begin(), test.end());
    int h = 0;
    for (auto& i : test) {
        i += h;
        ++h;
    }
    reverse(test.begin(), test.end());
    auto end = GetTickCount();
    cout <<"foo1 time consumption: "<< (end - start) << endl;
}
void foo2() {
    vector<int>test(v_size, 1);
    auto start = GetTickCount();
    int h = 0;
    for (auto it = test.rbegin(); it != test.rend(); ++it) {
        *it += h;
        ++h;
    }
    auto end = GetTickCount();
    cout << "foo2 time consumption : " << (end - start) << endl;
}
int main() {
    foo1();
    foo2();
    foo2();
    foo1();
    foo2();
}

运行结果 #

foo1 time consumption: 0
foo2 time consumption : 156
foo2 time consumption : 156
foo1 time consumption: 0
foo2 time consumption : 171

问题描述 #

我观察到两个现象：一是将范围for循环替换为普通for循环后程序变慢，但耗时约40ms；二是反向迭代器的性能显著偏低。请问该性能差异的成因是什么？

性能差异成因分析 #

1. foo1耗时为0的“假象”与编译器优化 #

首先要明确，GetTickCount()的精度是毫秒级，foo1的实际耗时大概率小于1ms，所以显示为0，并非完全没有开销。但即便如此，foo1依然比foo2快很多，核心原因是编译器对foo1的优化空间大得多：

• foo1里的两次reverse+正向遍历，编译器能识别出这一串操作的本质就是从后往前修改数组元素（先反转再正向修改，再反转回去，等价于反向遍历修改）。现代编译器的优化器（如O2/O3级别）可以直接把这三次操作合并成一次反向内存访问，甚至能触发SIMD指令批量处理，大幅压缩执行时间。
• 而foo2的反向迭代器遍历，编译器优化难度更高。反向迭代器本质是对正向迭代器的封装，每次++it实际是调用底层正向迭代器的--，每次解引用*it也要多一层封装转换。虽然单步开销极小，但10万次循环累计起来就很可观；更关键的是，这种封装会干扰编译器的向量化优化——反向迭代器的内存访问模式对编译器来说不如正向连续访问直观，很难触发自动向量化。

2. 反向迭代器的底层额外开销 #

vector的反向迭代器rbegin()返回的是std::reverse_iterator<vector<int>::iterator>，它的核心操作有额外成本：

• operator++()：调用底层正向迭代器的operator--()，哪怕被内联，指令逻辑也比正向迭代器的operator++()多一层。
• operator*()：返回*(base() - 1)，每次解引用都要先偏移一个元素再取值，比正向迭代器直接解引用多一次地址计算。

这些微小开销在单次迭代中可以忽略，但循环次数达到10万次时，累计起来就会形成明显的耗时差。

3. 普通for循环比范围for慢的原因 #

你提到的范围for换普通for后耗时增加，通常是因为普通for的写法没让编译器充分优化：

• 范围for在编译时会被转换成基于迭代器的循环，编译器更容易识别连续内存访问模式，进而触发向量化优化。
• 如果普通for是for (int i = 0; i < test.size(); ++i)的形式，若test.size()每次循环都被调用且未被优化，或者用int而非vector::size_type导致类型转换，都会引入额外开销；要是你用的是反向普通for（for (int i = test.size()-1; i >=0; --i)），这种递减循环的内存访问模式对CPU预取器不友好，也会降低编译器向量化的概率。

内容的提问来源于stack exchange，提问作者J.R.