如何加速自定义类for循环？begin()迭代与索引for循环性能差异

问题背景 #

• 目标：找到提升char*、自定义类迭代速度的可行方案
• 编译运行环境：g++ gnu++2a、macOS，测试用的base::string为自行实现的自定义字符串类
• 问题现象：使用自定义begin()迭代器遍历char数组时运行速度很慢，而for (int i = 0; i < n; ++i)形式的索引for循环迭代速度要快得多，不清楚性能差异产生的原因

测试代码 #

class Iterator {
public:
    const unsigned char *values;
    int n;
    int index = 0;
    Iterator(int n__, const unsigned char *v) {
        n = n__;
        values = v;
    }
    auto& ref() { return *this; }
    auto& ref() const { return *this; }
    auto& begin() { return ref(); }
    auto& cbegin() const { return ref(); }
    auto& end() { return ref(); }
    auto& cend() const { return ref(); }
    bool operator !=(const Iterator& x) { return index < n; }
    bool operator !=(const Iterator & x) const { return index < n; }
    auto& operator ++() { ++index; return ref(); }
};

int main() {
    using namespace cinc;
    using namespace cinc::utils;
    long mark;

    // Itrings.
    print("Speed test:");
    print("   - initialize:");
    mark = timestamp();
    for (int i = 0; i < 10000000; ++i) {
        std::string x;
        x = "";
    }
    print("     - std::string:",timestamp() - mark,"ms");
    mark = timestamp();
    for (int i = 0; i < 10000000; ++i) {
        base::string x;
        x = "";
    }
    print("     - base::string:",timestamp() - mark,"ms");

    // Append.
    print("   - append:");
    mark = timestamp();
    std::string std_string;
    std::string std_string_air;
    for (int i = 0; i < 10000000; ++i) {
        std_string += "0";
    }
    print("     - std::string:",timestamp() - mark,"ms");
    mark = timestamp();
    base::string base_string;
    base_string.allocate();
    base::string base_string_air;
    base_string_air.allocate();
    for (int i = 0; i < 10000000; ++i) {
        base_string.append('0');
    }
    print("     - base::string:",timestamp() - mark,"ms");
    base_string.del();

    // Iterate.
    print("   - iterate:");

    // Iterate std::string with begin.
    mark = timestamp();
    for (auto& i: std_string) {
        std_string_air += i;
    }
    print("     - base::string::begin:",timestamp() - mark,"ms");

    // Iterate base::string with a simlpe for index loop.
    mark = timestamp();
    const unsigned char* us = (unsigned char*)  base_string.values;
    int n = base_string.size__;
    for (int index = 0; index < n; ++index) {
        base_string_air.append(us[index]);
    }
    print("     - base::string::for:",timestamp() - mark,"ms");

    // Iterate base::string with the begin.
    mark = timestamp();
    Iterator iterator = Iterator(base_string.size__, (unsigned char*) base_string.values);
    for (auto& i = iterator.begin(); i != iterator.end(); ++iterator) {
        base_string_air.append(iterator.values[i.index]);
    }
    print("     - base::string::begin:",timestamp() - mark,"ms");
    return 0;

}

测试结果 #

未开启编译优化 #

initialize:
 * std::string: 214 ms
 * base::string: 83 ms
append:
 * std::string: 120 ms
 * base::string: 46 ms
iterate:
 * std::string::begin: 83 ms
 * base::string::for: 22 ms
 * base::string::begin: 94 ms

开启-O2编译优化 #

Speed test:
Speed test:
   - initialize:
     - std::string: 58 ms
     - base::string: 0 ms
   - append:
     - std::string: 96 ms
     - base::string: 10 ms
   - iterate:
     - base::string::begin: 34 ms
     - base::string::for: 0 ms
     - base::string::begin: 0 ms

性能差异核心原因 #

• 迭代器实现不符合C++标准迭代器设计约定，编译器无法做最优优化。当前实现中begin()和end()返回的是同一个对象的引用，而标准要求end()是独立的、指向容器尾后位置的迭代器；operator!=没有比较两个迭代器的相对位置，而是拿迭代器内部的index字段和固定阈值n比较，无优化时每次判断都要走成员函数调用、this指针解引用的额外流程，比直接操作栈上局部索引变量的索引循环多了很多冗余步骤。另外测试里的迭代器循环逻辑本身存在错误：循环中自增的是外层的iterator对象而非循环变量i，取值时还手动拿i.index访问数组，完全绕开了迭代器本该有的解引用逻辑，进一步拉高了开销。
• 无优化模式下成员函数不会被内联。operator!=、operator++、begin()/end()这类短函数在O0模式下都是真实的函数调用，需要走栈帧创建、参数传递的流程，而普通索引循环的变量全部存在栈上，操作都是直接的算术运算、内存访问，没有函数调用开销，速度自然更快。
• 开启-O2后性能差消失是编译器优化的正常结果。开优化后编译器会把这些简单的成员函数全部内联展开，消掉所有函数调用开销，甚至能直接分析出迭代器遍历的本质就是索引访问，把循环优化成和索引for完全等价的逻辑，部分无实际副作用的代码还会被编译器直接删除，因此会出现0ms的测试结果。

迭代速度优化方案 #

• 最高效的实现方式是直接用裸指针作为字符串类的迭代器，不需要单独封装迭代器类：

  using iterator = unsigned char*;
  using const_iterator = const unsigned char*;
  

  对应begin()返回values指针，end()返回values + size__即可。这种形式的迭代器和裸指针完全等价，编译器不需要额外分析就能做到和索引循环完全一致的性能，没有任何额外开销，也是绝大多数标准库实现中std::string采用的迭代器方案。
• 如果确实需要自定义迭代器类，必须符合标准规范：
  • begin()返回指向首元素的迭代器实例，end()返回指向尾后位置的独立迭代器实例，不要返回同一个对象的引用
  • 实现operator*()用于解引用获取当前位置的元素，不要在循环外部手动维护索引访问数组
  • operator!=/operator==直接比较两个迭代器的当前指针位置，不要依赖内部存储的长度字段做判断
  • 把自增、解引用、比较这类短操作声明为内联，保证开优化时能被编译器完全展开
• 所有C性能测试必须在开启O2/O3优化的前提下进行，O0模式下的性能数据没有参考价值。C的零开销抽象特性本身就依赖编译器优化实现，不开优化时任何类封装、函数调用都会带来额外开销，不能代表程序的实际运行性能。

内容的提问来源于stack exchange，提问作者user3134709