新古典C++：分段迭代器再探

# 新古典 C++：重访分段迭代器（一） 来源：https://boostedcpp.net/2026/05/18/neoclassical-c-segmented-iterators-revisited-1/ ## 分段迭代器简介 *传奇的 STL 库*（https://stl.boost.org/）一直是 C++ 语言及库发展中的灵感源泉。Stepanov、Lee、Musser、Austern 等人所开发的概念与代码，是任何 C++ 程序员取之不尽的宝藏。Stepanov 的核心主张是，抽象应当几乎零开销。他认为，正确实现的泛型编程不应比手写的特化代码带来显著运行时开销（*抽象惩罚*）。这不仅是愿望，更是 STL 的设计原则。 遵循这一理念，Matt Austern 于 2000 年发表了论文 *分段迭代器与分层算法*（https://lafstern.org/matt/segmented.pdf）。论文的核心论点是，许多数据结构天然是分段的（例如 *deque*），而忽略此特征的泛型算法——将每个数据结构都视为统一的元素区间——是不必要地低效的。一种新的迭代器抽象，将分段性显式化，可以编写出利用分段特性的分层算法，从而减少与标准迭代器相关的*抽象惩罚*。 经典的激励示例是 *std::deque*，它在内部是由一系列固定大小的数组组成。对 deque 迭代器的每个 `++it` 操作都可能跨越块边界，因此隐式地 `std::find` 或 `std::fill` 每一步都必须评估当前指针是否已到达当前块的末尾，这种间接操作使得 deque 迭代明显变慢，同时也打破了大多数编译器的自动向量化能力。一个*分段迭代器*可以是一个两级结构，允许算法高效地操作每个连续分段（例如，在每个块上调用 *memset* 或紧凑内部循环），只在外部层面处理分段之间的转换。 这篇论文影响深远，但其思想从未被采纳进 C++ 标准。另一方面，一些库已在内部发展了这些核心思想。举例如下： - 大约从 2023 年起，*libc++* 的 *std::for_each* 针对分段迭代器进行了优化，*带来了显著的性能提升*（https://releases.llvm.org/19.1.0/projects/libcxx/docs/ReleaseNotes/18.html），并且正在持续努力添加更多算法（https://github.com/llvm/llvm-project/issues/102817）。 - 一些 Boost 库，如 Boost.PolyCollection（https://www.boost.org/doc/libs/latest/doc/html/poly_collection.html），内部专门为其分段特性调整了算法实现（https://github.com/boostorg/poly_collection/blob/develop/include/boost/poly_collection/algorithm.hpp）。 ## Austern 论文详解 传统的迭代器提供扁平视图：递增、递减、解引用。一个*分段*迭代器额外允许分解为两个坐标： 1. **分段迭代器（segment iterator）**，遍历*外层*的分段序列（deque 的块、chunk-list 的块、链式哈希表的桶等）。此迭代器*不可解引用*。 2. **局部迭代器（local iterator）**，遍历单个分段内的*内部*区间。此迭代器*可解引用*。 一个*分层算法*因此是一个泛型算法，当给定分段迭代器时，它分派到一个两级循环：外层循环遍历分段，在每个分段内部，是一个简化算法，作用于性能更高、分段性更少的 *local_iterator*，而后者本身可以进一步分解为新的、更低层的**分段迭代器**/**局部迭代器**对。最终，这种递归分段到达一个不可再分、可能非常高效的 *local_iterator*。 对于 `deque` 来说，这是经典的一级分段情况：*segment_iterator* 本质上遍历块索引，而相应的 *local_iterator* 在一个块内部遍历。 对于像 `vector<vector<int>>` 这样更深层次的容器，同样的分解*递归*进行：外层产生的 *local_iterator* 本身可以分解为新的 *segment_iterator*（其分段是中间层的 vector）和 *local_iterator*，而最内层 `vector` 的 *local_iterator* 才是真正的扁平。 为了在 *iterator*、*local_iterator* 和 *segment_iterator* 之间进行转换，Austern 提出了一个 `segmented_iterator_traits` 类模板，定义了分段感知算法所需的基本操作。其概要（摘自论文）如下： ```cpp // 通用定义，包含一个标志，标识迭代器为非分段 template <typename Iterator> struct segmented_iterator_traits { typedef /* Type::value == false */ is_segmented_iterator; }; // 为每个分段迭代器类型特化 traits 类 template <typename Iterator> struct segmented_iterator_traits<Iterator> { // is_segmented_iterator::value == true 如果 Iterator 是分段的 typedef /* unspecified */ is_segmented_iterator; // 一个不可解引用的迭代器，遍历分段序列 typedef /* unspecified */ segment_iterator; // 一个高效的、可解引用的迭代器，在单个分段内遍历 // 此迭代器可进一步分解为更低层的分段和局部迭代器 typedef /* unspecified */ local_iterator; // 返回包含 it 当前位置的分段 static segment_iterator segment(Iterator it); // 返回 it 在当前分段内的位置 static local_iterator local(Iterator it); // 从 segment + local 构造高层迭代器 static Iterator compose(segment_iterator s, local_iterator l); // 返回指向分段首元素的局部迭代器 static local_iterator begin(segment_iterator s); // 返回指向分段尾元素下一个位置的局部迭代器 static local_iterator end(segment_iterator s); }; ``` 有了这个 traits，论文的经典示例——在分段区间上的 `fill`——编写为三个部分的遍历：第一个分段的尾部、所有中间分段的整体、最后一个分段的头部： ```cpp template <typename SegIt, typename T> void hierarchical_fill(SegIt first, SegIt last, const T& x) { typedef segmented_iterator_traits<SegIt> traits; typename traits::segment_iterator sf = traits::segment(first); typename traits::segment_iterator sl = traits::segment(last); if (sf == sl) { // 单个分段，快速路径 std::fill(traits::local(first), traits::local(last), x); } else { // 多分段情况 std::fill(traits::local(first), traits::end(sf), x); // 部分初始 for (++sf; sf != sl; ++sf) // 中间"完整"分段 std::fill(traits::begin(sf), traits::end(sf), x); std::fill(traits::begin(sl), traits::local(last), x); // 部分最终 } } ``` 对 `std::fill` 的三次调用都是基于 *local_iterator* 的扁平循环，其效率可以与 `T*` 媲美。Austern 的论文声称，与传统的 STL 式 `std::fill` 实现相比，可以获得*约 20% 的性能提升*。然而，我们将看到，在现代编译器下，一个高效的 *local_iterator* 可以实现更高的性能水平。 ## Boost.Container 如何实验分段 Boost.Container（https://www.boost.org/library/latest/container/）已开始实验性工作，紧密遵循原始提案开发分段算法。时间会证明这项实验性工作是会产生另一个 Boost 库提案，还是仅仅作为加速像 `deque`、`hub`（https://github.com/joaquintides/hub）等分段数据结构的实现细节。你可以在 Boost.Container 仓库（https://github.com/boostorg/container/tree/develop/include/boost/container/experimental）中找到正在进行的工作，包括实现、初步测试和非常早期的基准测试。 初步实验遵循原始论文，实现了以下算法： - 标签分派基于 `segmented_iterator_traits::is_segmented_iterator`。 - 当迭代器确实被检测为分段时，对于简单算法（更复杂的算法需要更新的方法），算法将输入区间分解为第一个分段、中间分段和最后一个分段，在每个分段上递归调用自身，最终在 *local_iterator* 类型的扁平循环上终止。 - 当传入的迭代器未被检测为分段时，算法退化为经典循环，行为与标准库版本相同。 > **注：** Austern 论文中的多分段（首分段+中间分段+末分段）方法可以简化为单个 `while` 循环，但这可能会降低固定大小分段数据结构（如 `deque`）的性能，因为编译器在地址范围长度在编译时已知时更容易进行自动向量化。我发现，没有固定边界（分段起始和结束）的单一 while 循环在许多情况下明显较慢，因为编译器无法保证向量化能在每次迭代中工作。 ```cpp template <typename SegIt, typename T> void hierarchical_fill(SegIt first, SegIt last, const T& x) { typedef segmented_iterator_traits<SegIt> traits; typename traits::segment_iterator sf = traits::segment(first); typename traits::segment_iterator sl = traits::segment(last); typename traits::local_iterator lf = traits::local(first); while (true) { typename traits::local_iterator le = (sf == sl) ? traits::local(last) : traits::end(sf); std::fill(lf, le, x); if (sf == sl) break; lf = traits::begin(++sf); } } ``` 本文的目标是展示这些实验性分段算法的性能，从经典的 `boost::container::deque` 容器开始。正如上一篇文章（https://boostedcpp.net/2026/03/30/deque/）所解释的，在这个 `deque` 实现中，块"索引"实现为一个 `T*` 数组，指向固定大小的 `T` 类型块（数组）。因此，对于 Boost 的 `deque::iterator`： - *segment_iterator* 定义为 `T**`，在块之间移动。 - *local_iterator* 定义为纯 `T*`，可以在一个连续内存块内高效移动。 ## 低垂的果实：使用 `deque` 对单区间、单遍算法进行基准测试 幸运的是，Austern 的 `fill` 示例可以完全复用于许多其他类似算法。*无界*算法（接受长度参数而非区间，如 `fill_n`、`generate_n`）需要稍微复杂的分段处理，但本质上遵循 Austern 的提案。 **注：** 当算法接受多个输入迭代器区间和/或输出迭代器区间时（例如 `std::merge` 接受两个输入区间和一个输出迭代器，可能涉及三种不同的分段迭代器类型），分段处理会变得更加复杂。像 `reverse` 这样必须同时向前和向后遍历区间的算法也是挑战。最后，在某些情况下，利用递归分段迭代器（一般情况）的实现比处理单级分段更为复杂。 基准测试亮点（你可以在这里找到通用基准测试代码：https://github.com/boostorg/container/blob/develop/experimental/bench_segmented_algos.cpp）： - 每次测试都针对同一个 **`boost::container::deque`**，块大小固定为 **每块 128 个元素**，**`size() == 100'000`**。 - 每次调用成本在数千次调用中取平均值。 - 容器**填充连续的正值** `0, 1, 2, ..., N-1`（因此所有元素非负、互异且严格升序）。 - 在适当情况下，基准测试同时探测 **`(hit)`** 和 **`(miss)`** 变体，分别指算法返回的*答案*。 - 选定的 **27 个子基准**（16 个算法，其中部分包含 "hit" + "miss" 变体）总结在下表中。 | 算法 | Hit 情况 | Miss 情况 | |------|----------|-----------| | `all_of` | 谓词 `x ≥ 0` — 所有位置为 true；必须扫描每个元素 | 谓词 `x ≠ N/2` — 算法在中间短路 | | `any_of` | 谓词 `x == N/2` — 在中间短路 | 谓词 `x < 0` — 全遍历后回答"否" | | `count` | 值 = `0` — 计数单个命中，但仍扫描整个 deque | 值 = `-1` — 从不出现，扫描整个 deque | | `count_if` | 谓词 `is_odd(x)` — 一半元素为 true；全遍历 | 谓词 `x < 0` — 从不 true；全遍历 | | `fill` | 用 `T(42)` 覆盖所有 `N` 个元素 | — | | `fill_n` | 用 `T(42)` 覆盖前 `N` 个元素 | — | | `find` | 值 = `N/2` — 存在于索引 `N/2`；在中间短路 | 值 = `-1` — 从不出现；全遍历 | | `find_if` | 谓词 `x == N/2` — 在索引 `N/2` 为 true；在中间短路 | 谓词 `x < 0` — 从不 true；全遍历 | | `find_if_not` | 谓词 `x ≠ N/2` — 在索引 `N/2` 为 false；在中间短路 | 谓词 `x ≥ 0` — 所有位置为 true；全遍历后报告"没有元素不满足谓词" | | `for_each` | 对整个 deque 应用一个 `summer` 仿函数，累加 `int` 和 | — | | `generate` | 用生成器 `counter` 产生 `0, 1, 2, ...` 覆盖每个元素 | — | | `generate_n` | 与 `generate` 相同，通过 `_n` 重载调用 | — | | `is_partitioned` | 谓词 `x < 0` 在未修改的、全非负 deque 上，算法遍历整个 deque 以确认 | 谓词 `x < 0` 在索引 `N/2` 处注入了 `-1` 的副本上，在中间短路 | | `none_of` | 谓词 `x < 0` — 从不 true；全遍历后回答"是的，没有一个满足" | 谓词 `x == N/2` — 在索引 `N/2` 为 true；在中间短路 | | `replace` | deque 预先处理为每个奇数索引包含 `-1`；`replace(-1 → -2)` 然后*重写*一半的元素（多次存储） | `replace(-1 → -2)` 在未修改的 deque 上 — `-1` 从不出现，因此遍历执行零次存储 | | `replace_if` | 谓词 `is_odd(x)` — 一半元素为 true；全遍历，每两个元素执行一次存储 | 谓词 `x < 0` — 从不 true；全遍历，零次存储 | 使用了两种元素类型： - **`MyInt`** — 包装单个 `int`（4 字节，可平凡比较）。 - **`MyFatInt`** — 包装八个 `int`（32 字节），仅比较其第一个字段。 算法以三种模式执行： - **seg**（**SEG**mented）：调用 Boost 实现，走分段路径（`segmented_iterator_traits::is_segmented_iterator::value == true`） - **nsg**（**N**on**S**e**G**mented）：调用 Boost 实现，但不走分段路径（`segmented_iterator_traits::is_segmented_iterator::value == false`），使用简单的经典 STL 式循环。 - **std**（**ST**an**D**ard）：调用 `std::` 算法 对于每个算法和每个值类型，基准测试打印三列： | 列 | 隔离内容 | 比率 > 1.0 的含义 | |----|----------|------------------| | **`nsg/seg`** | 相同算法、相同编译器、相同迭代器对象，是否声明分段 | Boost**分段路径**比 Boost**非分段路径**快 X 倍 | | **`std/seg`** | 分段版本与平台原生实现的比较 | Boost**分段路径**比**std**算法快 X 倍 | | **`std/nsg`** | 平台原生实现与不带分段标签的相同扁平循环的比较 | Boost**非分段路径**比**std**算法快 X 倍 | 测试的编译器/标准库： - **MSVC 2022** — Toolset v14.44（VS 2022），Microsoft STL — Windows，`/O2 /std:c++20`。 - **MSVC 2026** — Toolset v14.51（VS 2026），Microsoft STL — Win