Segmented iterators 重訪——讓編譯器看見 deque 的分段結構，把通用演算法的 SIMD 加速找回來

把一個 std::deque<int> 灌滿同一個值，你會怎麼寫。 多數人不假思索地寫 std::fill(d.begin(), d.end(), 0)， 然後相信標準庫實作會幫你做對的事。 對 std::vector 而言這個信任是被回報的：vector 的迭代器就是裸指標， std::fill 退化成一個對連續記憶體的 tight loop， GCC 與 Clang 在 -O3 下會把它向量化成 memset 等級的 SIMD store。 但對 deque，這個信任落空了——而且落空的方式不是「慢一點」， 是整整一個數量級的差距。

問題的根源是 deque 的記憶體布局。 deque 不是一塊連續記憶體，而是一個 block 的陣列： 一個外層的 T** 索引（map），指向若干個固定大小的 block， 每個 block 是一段連續的 T*。 這篇 2026 年五月在 boostedcpp.net 上的長文， 把 Matt Austern 在 2000 年提出的 segmented iterator 概念重新搬上檯面， 用 MSVC 2026、Clang、GCC 16 三個編譯器跑了一遍 benchmark， 結論是：把這個分段結構暴露給演算法，幾何平均加速 5.9×， corner case 上 fill 衝到 17×。 這篇要回答的問題很具體——分段感知（segmentation-awareness）在什麼情況下值得做， 讀者實際上又該做什麼。

這是一個比較，有兩條軸。 第一條軸是演算法：把容器當扁平 range 走的 naive flat iteration， 對上看得見分段結構的 hierarchical algorithm。 第二條軸是編譯器：同一個 hierarchical 改寫，在 MSVC、Clang、GCC 上的回報差異極大， 甚至方向相反——有的編譯器吃 unroll hint 吃得很開心，有的反而因此退步。 這兩條軸交叉起來，才是讀者真正需要的決策圖： 你用哪個編譯器、你的元素多大、你呼叫的是哪個演算法， 決定了這個改寫是值 17× 還是只值 1.96×。

先把四個編譯器配置在兩種元素大小上的幾何平均加速擺出來看。 這張圖的每一組長條對應一個編譯器（含 GCC 開不開 unroll hint 兩種）， 左半邊是 4-byte 的 MyInt，右半邊是 32-byte 的 MyFatInt。 你會立刻看到兩件事：MSVC 在小型別上一枝獨秀， 以及元素變大之後所有編譯器的加速都收斂——這不是巧合，後面會解釋。

切到「僅 std::fill」會看到 MSVC 那根長條暴衝到 17.16×。 這不是平均值，是 fill 這個單項演算法在 4-byte 元素上的 corner case—— 純 SIMD store 識別。fill 是所有演算法裡最容易向量化的： 它的內迴圈就是「對連續記憶體寫同一個值」， 一旦編譯器看得見一段連續的 T* range， MSVC 2026 的後端會直接認出這是 vectorizable store pattern， 展開成寬向量寫入。而扁平的 deque 迭代器把這個 pattern 藏起來了， 所以加速幅度等於「向量化 vs 完全沒向量化」的全部落差。

分段結構：T** 走 block、T* 走元素，兩層迭代器各管一層

要理解 segmented iterator，得先看清楚一個 segmented iterator 拆成兩個東西。 Austern 在 2000 年的定義是：一個 segmented iterator 分解成兩層的階層結構。 外層是 segment iterator，走過外層的 segment 序列—— 在 deque 裡就是 block，在 chunk-list 裡是 chunk，在 hash table 裡是 bucket。 它本身是 不可解參考的（non-dereferenceable）： 對 deque 而言它的型別是 T**，你 *seg 得到的是一個 block 的位址， 不是元素本身。

內層是 local iterator，走過單一 segment 內部的元素。 對 deque 而言它的型別是 T*，是 可解參考的（dereferenceable）： *local 直接給你元素。 一個扁平的 deque iterator，骨子裡就是「一個 segment iterator 加一個 local iterator」的組合， 只是它把這個組合包成單一物件，每次 ++ 都要在內部判斷 「local 走到 block 尾巴了沒，要不要 ++segment 換下一個 block」。

下面這張圖把這個兩層結構畫出來。 上排是 segment iterator 走的 T** map， 每個格子指向下方一個 block； 下排是 local iterator 在某一個 block 內走的 T*。 注意 segment iterator 停在格子之間（block 邊界）時是 non-dereferenceable 的—— 這就是為什麼扁平迭代器每次 ++ 都得問一句「我現在在邊界上嗎」。

這個遞迴性質值得停一下。 像 vector<vector<vector<T>>> 這種巢狀容器可以遞迴地分解： 某一層的 local iterator 同時就是下一層的 segment iterator。 這讓 segmented iterator 不只是 deque 的專屬把戲， 而是任何「分段儲存」結構的通用抽象—— chunk-allocated container、column store、rope、B-tree 的葉節點掃描， 本質上都是同一個形狀。 Boost.PolyCollection 就為這類結構實作了自己的 segmented algorithm， libc++ 在 2023 年也為 segmented iterator 特化了 std::for_each。

為什麼是 T** 而不是更精巧的東西。 答案是 deque 的設計約束：它要支援兩端 O(1) 的 push， 所以中間的 block 序列不能隨成長重新配置已有的 block—— 那會讓既有元素的位址失效，違反 deque 的迭代器穩定性保證。 解法是再加一層間接：一個可重新配置的 T** map 指向固定不動的 block， 成長時只重配 map 本身。 這層間接是 deque 的特性，不是缺陷； segmented iterator 要做的，是讓演算法直接走這層 map（segment iterator）， 而不是把它藏在每步 ++ 背後當作隱性成本。

邊界檢查：每次 ++ 的隱性分支擋掉了向量化

現在看為什麼扁平迭代器慢。 Austern 2000 年的分析點出核心： deque iterator 的每一次 ++it 都可能跨越一個 block 邊界， 所以 std::find 或 std::fill 在隱性的層面上， 每一步都得評估「目前的指標是否已經到達當前 block 的尾端」。 這個間接層擋住了編譯器的 auto-vectorization。 論文當年量到的是相較傳統 STL 實作約 20% 的效能改善空間。

20% 這個數字今天讀起來甚至偏保守，因為 2000 年的編譯器還沒有現在這麼激進的 SIMD 後端。auto-vectorizer 要把一個迴圈向量化， 前提是它能證明「迴圈體內每一步的記憶體存取是連續的、步長固定的、沒有資料相依的分支」。 扁平 deque iterator 的 ++ 內含一個條件分支 （「到 block 尾了嗎？是的話換 block」）， 這個分支讓 vectorizer 無法證明連續性—— 它必須假設任何一步都可能跳到一個完全不同的記憶體位址， 於是只好退回 scalar 的逐元素處理。

這裡要對 benchmark 方法學誠實一點。 評測用的 MyInt 與 MyFatInt 是包了一層的 wrapper 型別 （4 bytes 與 32 bytes），而非裸 int， 用意是阻止編譯器把整段 fill 直接降解成 libc 的 memset—— 那會讓比較失去意義，因為 memset 是手寫組語等級的特化， 任何抽象都贏不了它。 用 wrapper 型別逼編譯器走 element-wise 賦值路徑， 才能真正量到「auto-vectorization 能不能介入」這件事本身。 每個 deque 100,000 元素、block 固定 128 元素、上千次呼叫取平均—— 這個規模夠大到攤平 cache warm-up 與 timer 抖動。

這個損失隨 block 大小變動。block 越大，邊界出現得越稀疏， 純內部（interior）元素的比例越高，被邊界檢查拖累的相對開銷越小； block 越小，邊界越密集，越多元素卡在「邊界檢查綁定」的 scalar 程式碼裡， 可向量化的內部就被侵蝕掉。 下面這個 widget 讓你拖動 block 大小， 看可向量化的內部元素比例如何隨之變化—— deque 標準 block 是 128 個元素（對 4-byte 元素是 512 bytes / block）， 這是個甜蜜點，但如果你的元素很大、一個 block 只裝得下幾個，邊界就會主宰一切。

把滑桿拉到 2，可向量化比例只剩 50%—— 一半的工作卡在邊界轉換，這時 segmentation-awareness 幾乎沒有意義， 因為連續的內部 run 短到向量化都來不及攤平 setup 成本。 拉到 128（deque 標準 block），比例已經是 99.2%，曲線早就飽和。 這解釋了為什麼小型別的加速這麼大：4-byte 的 MyInt 在 128-element block 裡， 一個 block 是 512 bytes、足足 8 個 AVX2 暫存器寬度的資料， SIMD store 可以連續灌好幾輪； 而 32-byte 的 MyFatInt 在同樣 128-element block 裡是 4096 bytes， 但每個元素本身就佔半個 cache line，向量化的相對收益被記憶體頻寬上限壓住了。 這就是前面那張圖裡「元素變大、加速收斂」的物理原因。

階層演算法：頭段 + 整段內部 + 尾段，把連續內迴圈暴露出來

解法是讓演算法看見分段，而不是把容器壓平。 Austern 給的 canonical pattern 是把一個 range 拆成三塊： 部分的初始 segment（第一個 block 的尾巴）、 完整的內部 segment（中間整個整個的 block）、 部分的最終 segment（最後一個 block 的頭）。 關鍵在中間那塊：完整的內部 segment 是一整個 block 從頭灌到尾， 這時 local iterator 走的是純連續的 T*， 內迴圈是 std::fill(begin(seg), end(seg), x)—— 一個對連續記憶體的 tight loop，沒有任何邊界分支，編譯器一眼認出可向量化。

下面用三個分頁展開這個拆解：第一頁是 naive 扁平寫法（編譯器看不見結構）， 第二頁是 segmented_iterator_traits 提供的詞彙， 第三頁是完整的 hierarchical_fill 程式碼。 切換分頁對照同一件事的三種視角。

// 編譯器看見的只是一對 opaque 迭代器；
// deque::iterator::operator++ 內部藏著 block 邊界分支
std::deque<MyInt> d(100000);
std::fill(d.begin(), d.end(), MyInt{0});
//        ^^^^^^^^^^^^^^^^^^^
// 每步 ++ 都問：local 到 block 尾了嗎？要 ++segment 嗎？
// 這個資料相依分支 → vectorizer 無法證明連續性 → scalar fallback

segmented_iterator_traits<It> 提供：

  is_segmented_iterator   // 編譯期布林：It 是分段的嗎
  segment_iterator        // 外層型別（deque: T**）
  local_iterator          // 內層型別（deque: T*）
  segment(it)             // 取 it 所在的 segment iterator
  local(it)               // 取 it 在 segment 內的 local iterator
  begin(seg) / end(seg)   // 某 segment 的內層起訖（純連續 T*）
  compose(seg, local)     // 把兩層重新組回扁平 iterator

template <class SegIt, class 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 拿到的都是純 T* 的連續 range， 然後讓既有的、已經為連續記憶體優化到極致的 std::fill 重載去做它最擅長的事。 中間那個 for (++sf; sf != sl; ++sf) 迴圈， 每一輪都是一整個 block 的連續填充， block 內沒有任何邊界分支， vectorizer 看到的就跟對 std::vector 一樣乾淨。 這是責任的轉移：把「在哪裡跨 block」這個知識從 runtime 的每步檢查， 搬到 compile-time 的結構分解。

編譯器分歧：MSVC 吃 SIMD、Clang 怕 unroll hint、GCC 靠它翻身

同一個 hierarchical 改寫，三個編譯器的回報差異大到方向相反， 這是這篇評測最值得記住的一節。 把第一張圖切回幾何平均，逐個看。

MSVC 2026在小型別上一枝獨秀：MyInt 幾何平均 5.93×， MyFatInt 3.31×，fill 單項衝到 17.16×。 MSVC 2026 的後端對「連續記憶體寫同值」的 SIMD store recognition 做得最積極， 一旦結構暴露，它幾乎是把整段內部 block 編成寬向量寫入。 而且 MSVC 忽略 unroll pragma——你寫不寫 #pragma unroll 它都一樣， 因為它的 auto-vectorizer 已經自己決定好展開策略，手動提示對它是 no-op。

GCC 16是另一個極端：不開 unroll hint 時 MyInt 只有 1.96×， 是全場最低；但加上 #pragma unroll(4) 之後跳到 3.13×—— +60% 的提升。GCC 的 vectorizer 預設對這類內迴圈的展開比較保守， 需要顯式提示才會把連續 block 的填充展開到足以攤平 SIMD setup 成本的程度。 對 GCC codebase，這個 hint 不是可有可無，是把加速從「勉強」拉到「實用」的關鍵。

Clang則在 unroll hint 上退步： 乾淨的 hierarchical_fill 在 Clang 上是 4.09–4.11× 的健康加速， 但一旦你好心加上顯式 unroll hint，Clang 反而變慢。 Clang 的 loop vectorizer 與 unroller 之間有自己的成本模型協商， 顯式 hint 會干擾這個協商、強制一個次優的展開因子， 結果是干擾了它本來就會做對的事。 這是最反直覺的一點：對 GCC 有益的 hint，對 Clang 有害。

這三種行為交叉起來，得到一張很實際的對照表。 下面這張表把「扁平 vs 分段感知」的差異， 以及三個編譯器對 unroll hint 的反應，擺在同一個畫面裡。 點欄位 header 可重排，方便你依自己的編譯器找對應那一列。

把這張表跟前面的長條圖合起來看， 可以提煉出一個工程上很乾淨的觀察： hierarchical_fill 這個改寫本身在所有編譯器上都是正收益 （最差的 GCC 無 hint 也有 1.96×）， 真正分歧的是「該不該再疊一個 unroll hint」這個次決策。 這個次決策完全被編譯器後端綁架—— 對 GCC 加，對 Clang 不要加，對 MSVC 加不加都一樣。 如果你的 codebase 要跨編譯器編譯，最安全的做法是用 #if defined(__GNUC__) && !defined(__clang__) 把 unroll pragma 包起來，只對純 GCC 開。

zero-overhead 抽象：這是 Stepanov 命題的一次體檢

退一步看，這整件事是 Stepanov 的 zero-overhead abstraction 原則的一次體檢。 Stepanov 的核心主張是：抽象應該有接近零的開銷—— generic programming 如果做對了，相較手寫的特化程式碼， 不應該帶來可察覺的執行成本（abstraction penalty）。 STL 的整個設計哲學就建立在這個命題上： std::fill 不該比手寫 for-loop 慢。

但扁平 deque iterator 違反了這個命題。 把 deque 當扁平 range 走，付出的是 Austern 量到的約 20% throughput penalty， 在現代 SIMD 後端下放大成一個數量級的差距—— 這個 penalty 不是來自 STL 的演算法本身， 而是來自「迭代器抽象把分段結構藏起來了」。 抽象藏掉的不只是不必要的細節，連編譯器需要的優化線索也一起藏掉了。 這正是 abstraction penalty 的教科書案例。

segmented_iterator_traits 與 hierarchical algorithm 是對這個命題的修補： 它不是放棄抽象、退回裸指標， 而是設計一個更精確的抽象—— 讓迭代器抽象同時暴露「我是分段的，這是我的外層、這是我的內層」這個結構， 於是通用演算法可以在不犧牲泛型的前提下， 為每個 segment 內部生成跟手寫一樣乾淨的連續迴圈。 這是 Stepanov 命題的正確實現方式： 零開銷不是靠「抽象越薄越好」，是靠「抽象暴露的資訊剛好夠編譯器做對的優化」。

現代標準庫已經在往這個方向走。 libc++ 在 2023 年為 segmented iterator 特化了 std::for_each—— 這意味著你今天在 libc++ 上對 deque 呼叫 std::for_each， 很可能已經免費吃到了 hierarchical 的好處，不用自己寫 traits。 Boost.PolyCollection 則把 segmented algorithm 做成它的核心賣點。 但 std::fill、std::find、std::transform 等其餘演算法的特化覆蓋率，在三家標準庫實作之間並不一致—— 這正是你需要自己量測、必要時自己寫 hierarchical 版本的灰色地帶。

怎麼快速驗證你的標準庫有沒有偷偷幫你做了 hierarchical。 最直接的方法是看 codegen：把對 deque 的 std::fill 編出組語 （-O3 -march=native），grep 一下有沒有寬向量 store 指令—— x86 上找 vmovdqu ymm 或 vmovups zmm， ARM 上找 st1 帶 SVE 暫存器。 如果只看到一連串 scalar 的 mov 加上每隔幾步一個比較分支， 代表 vectorizer 被邊界檢查擋住了，這個演算法在你的標準庫上沒被特化， 自己套 hierarchical_fill 會有收益。 反過來，如果已經看到密集的寬向量 store，標準庫替你做完了，別重複造輪子。 這個十分鐘的 codegen 檢查，比直接相信「libc++ 2023 特化過了」更可靠—— 因為特化的是 for_each，不一定涵蓋你正在呼叫的那個演算法。

該不該做：先量你的元素大小與編譯器，再決定要不要寫 traits

把兩條軸交叉起來，決策其實相當清楚。

如果你的容器是 deque 或其他分段結構，元素小（≤ 8 bytes）、 熱迴圈跑的是 fill / copy / find / transform 這類 element-wise 演算法、 且你的編譯器是 MSVC 2026 或 Clang—— 這是 segmentation-awareness 的甜蜜點，加速 4–17×，值得做。 優先確認你的標準庫實作（尤其 libc++）有沒有已經特化你呼叫的演算法； 有的話一行都不用改。沒有的話，hierarchical_fill 這個 pattern 二十行就能套上。

如果你用 GCC——一樣值得做，但記得加 #pragma unroll(4)， 否則你只拿到 1.96× 而不是 3.13×，會誤以為這個技術不值得。 用 #if defined(__GNUC__) && !defined(__clang__) 把 hint 圈起來， 避免它溢出去害到 Clang。

如果你的元素很大（≥ 32 bytes）—— 加速收斂到 2.4–3.3×，仍是正收益，但別期待 17×； 記憶體頻寬而非邊界檢查才是你的瓶頸， 這時更該優先看的是資料布局（SoA vs AoS）而不是迭代器分段。

如果你的容器是 vector—— 這整篇與你無關。vector 的迭代器本來就是裸指標， std::fill 早就向量化好了，沒有分段結構要暴露。 segmentation-awareness 是 deque 與分段容器的專屬議題， 不要對連續容器套這個 pattern——你只會得到沒有意義的 single-segment fast path。

Take-away：對小型別、element-wise 熱迴圈跑在 deque 上的場景， 先確認標準庫有沒有特化、再決定要不要自己寫 hierarchical traits；MSVC 與 Clang 直接做（最高 17×）， GCC 記得包 #pragma unroll(4)（1.96× → 3.13×），Clang 千萬別加 hint，元素大或容器是 vector 就別費這個工。