用多搬一倍資料換回排序速度——拆 blqsort 的 branchless partition 與 fallback

blqsort 是一份 single-header 的 branchless quicksort，它的整個設計圍繞一個微架構事實打轉：在現代 out-of-order CPU 上，一個被預測錯的條件分支會清空 pipeline、丟掉十幾到二十級的 in-flight 指令，代價遠大於多執行幾條算術指令。quicksort 的 partition 內迴圈裡那個「這個元素比 pivot 小嗎」的判斷，對隨機輸入而言幾乎是擲硬幣——branch predictor 在 50% 命中率的資料上等於沒用。blqsort 把這個 if 整個拆掉，改用「無條件寫入、再用比較結果推進指標」的寫法，對 trivially-copyable 的型別（double、int、POD struct）跑得比 std::sort 與 pdqsort 快不少。代價是它把每個元素都搬了不只一次，但只要省下的 misprediction 成本大於多搬的 copy 成本，這筆帳就划算。本文拆它的五個零件：branchless partition 的核心 trick、1024-element block 的雙向處理、處理 2–12 元素的 sorting network、median-of-medians 的 pivot 選法、以及在壞輸入與非平凡型別上的兩條 fallback。

branchless partition：把 if 換成 smlen += (x < pivot)

先看最小的那個 trick，因為整份 library 都建立在它上面。一個 textbook 的 partition 內迴圈長這樣：對每個元素判斷它在不在 pivot 的某一側，是的話寫進輸出緩衝、並把長度加一。寫成程式碼就是一個 if：

// branchy：每次迭代都要猜一次分支
if (numbers[i] < 500) {
    small_numbers[smlen] = numbers[i];
    smlen += 1;
}

這段碼在邏輯上無懈可擊，問題全在 if 這個字。當 numbers[i] < 500 對輸入而言是接近隨機的——例如你在 partition 一段已經被 shuffle 過的資料、pivot 又落在中位數附近——branch predictor 的命中率就會掉到 50% 上下。每一次預測錯，CPU 必須把已經 speculatively 執行進 pipeline 的後續指令全部作廢、從正確的分支重新抓指令。在一條十幾級深的 pipeline 上，這是十幾個 cycle 的純粹浪費，而且 partition 的內迴圈會跑 n 次。blqsort 的改寫只有兩行，關鍵在第二行：

// branchless：無條件寫入，用 0/1 推進指標
small_numbers[smlen] = numbers[i];
smlen += (numbers[i] < 500);

差別在哪？第一行無條件地把 numbers[i] 寫進 small_numbers[smlen]。如果這個元素其實不該進這個桶，沒關係——下一次迭代 smlen 不會前進，這個位置就會被下一個元素覆寫掉。第二行把布林比較的結果（C/C++ 裡 true 是 1、false 是 0）直接加到 smlen 上。元素該收就 smlen += 1、不該收就 smlen += 0 原地踏步等著被覆寫。整段沒有任何 if，沒有條件跳轉，CPU 不需要猜任何東西，pipeline 永遠不會因為這裡而清空。編譯器通常把 numbers[i] < 500 編成一條 setcc（把比較結果寫成 0/1 的 byte），再用一條 add 加到指標上——兩條無分支的指令，吞吐量是固定的。

但天下沒有白吃的午餐，這個寫法的代價非常具體：它把每個元素都無條件搬了一次，即使該元素根本不屬於這個桶。在最壞情況下，你執行了大約兩倍於「必要 copy」的記憶體寫入——branchy 版只在條件成立時才寫，branchless 版每次都寫。這就是標題說的「多搬一倍資料」。為什麼這還能贏？因為對 double 這種 8 byte、trivially-copyable 的型別，一次 copy 只是一條 store 指令，幾乎免費、而且可以被 CPU 的 store buffer 吸收、跟其他指令重疊執行；而一次 branch misprediction 是十幾個 cycle 的硬停頓，無法被隱藏。把「可隱藏的便宜操作」做兩倍，換掉「不可隱藏的昂貴停頓」，淨值為正。這個 trade 的成立條件很明確——元素要夠便宜搬（trivially-copyable）、分支要夠難預測（隨機輸入）。兩個條件只要有一個不成立，branchless 的優勢就會縮水甚至翻負，這也正是為什麼 blqsort 要準備後面那兩條 fallback。

下面這個互動小工具把兩種 partition 並排跑給你看。上半是 branchless 版本：元素一個一個流過 pivot 線，write head（smlen 指標）每次只前進 0 或 1 格，無論元素該不該收，那一格永遠先被寫上。下半是 branchy 版本：同樣的資料流，但每個元素都要先過一次「分支預測」——predictor 猜對就順順走，猜錯就觸發一次紅色的 pipeline flush、那一拍整條 pipeline 停住。把資料的「可預測度」滑桿往隨機端拉，看 branchy 版的紅色 flush 怎麼密集起來、而 branchless 版完全不受影響。

有一個容易混淆的點先講清楚：branchless 不等於「沒有比較」。比較還是要做——numbers[i] < 500 那條 cmp 永遠存在。被消掉的是條件跳轉（conditional branch），也就是「根據比較結果決定接下來執行哪段碼」的那個 jump。比較本身在現代 CPU 上是一條便宜、可亂序執行的指令；真正貴的是它後面那個會讓 fetch unit 押錯邊的 branch。另一個常見的等價寫法是用 cmov（conditional move）：把「要不要更新某個值」編成一條無分支的條件搬移指令。cmov 跟 setcc + add 是同一個哲學的兩種手段——讓資料相依性取代控制相依性，把「猜測」這件事從 hot path 上拿掉。blqsort 的整個 partition 引擎就是把這個原則推到極致。

1024-element block 與 sorting network：partition 引擎的兩個尺度

單一個元素的 trick 講完，接下來是怎麼把它組織成一個完整的 partition。blqsort 的做法受 fluxsort 啟發，用固定大小的 block 來分段搬運。它不是一個一個元素掃，而是以 1024 個元素為單位處理：先從一側把 1024 個元素複製進一個輔助緩衝區（auxiliary buffer），騰出空間，接著「交替地把一個 1024-element block 往左、往右 branchlessly 搬」。為什麼要先複製出 1024 個？因為 in-place partition 的麻煩在於：你要往某個位置寫一個元素時，那個位置可能還住著一個你還沒處理的元素。先把一整個 block 搬進旁邊的緩衝區，原地就空出了 1024 個格子可以無條件寫入，branchless 的「永遠先寫、再決定要不要前進指標」才能安全運作而不覆蓋掉未讀資料。

這個輔助緩衝區的另一個關鍵設計決定是：它是stack 上的固定陣列，不是 heap 配置。1024 個元素的緩衝區大小在編譯期就定死，直接吃 stack frame，沒有任何 malloc／new。這省掉的不只是配置本身的時間——堆積配置會引入不可預測的延遲（可能觸發 page fault、可能要走 allocator 的 lock）、會打亂 cache locality、而且在多執行緒情境下 allocator 本身可能成為 contention 點。把緩衝區釘在 stack 上，partition 的每一層遞迴都用同一塊熱的、已經在 L1 裡的記憶體，搬運的 store 幾乎都打在 cache 裡。1024 這個數字也不是隨便挑的：它要夠大，讓 block 內的 branchless 搬運能攤平 setup 成本、也讓 prefetcher 有足夠連續的存取模式可以預取；又要夠小，能整個塞進 stack 緩衝而不溢出、且留在 L1/L2 cache 的容量之內。

「往左、往右交替搬」是 fluxsort 那套雙向掃描的精神。partition 的本質是把一段資料分成「小於 pivot」與「不小於 pivot」兩塊，雙向處理的意思是同時從緩衝區與目標區的兩端推進，小的往左堆、大的往右堆，兩個 write head 相向而行直到會合。每一個 block 的內部搬運都用前一節那個 smlen += (x < pivot) 的 branchless 寫法，所以整個 partition——不論資料分佈如何——都不會在內迴圈產生任何 data-dependent 的分支。block 邊界的處理（什麼時候換下一個 block、左右會合時剩下的尾巴怎麼收）會有少量分支，但那是 O(n / 1024) 次、不是 O(n) 次，對整體 misprediction 預算可以忽略。

block 是「大尺度」的搬運單位，但 partition 遞迴到很小的子陣列時需要另一種收尾——這是 partition 引擎的另一個尺度。quicksort 在 partition 到很小的子陣列時會把遞迴停掉、改用別的方法收尾，因為對小陣列而言遞迴的 overhead 跟 pivot 選擇的成本反而主導了。傳統作法是切到 insertion sort，但 insertion sort 的內迴圈也充滿 data-dependent 分支——「這個元素要不要再往前挪一格」每一步都要判斷。blqsort 在 2 到 12 個元素的子集上改用 sorting network：一組對固定位置 pair 做「比較並在需要時交換」的操作序列，操作的順序與要比較哪些 index 完全由陣列大小決定，跟資料內容無關。

sorting network 的好處正是它的「資料無關」性質：一個 size-N 的 network 永遠執行同樣那幾個 compare-exchange，不管輸入是已排序、逆序還是隨機，執行的指令序列一模一樣。這意味著它天生 branchless——每個 compare-exchange 都可以用一個「branchless sort-2 primitive」實作：取兩個元素，無條件算出 min 與 max，把小的寫回前面、大的寫回後面。沒有「如果順序對了就跳過」的分支，就是兩條 cmov 或一組 min/max 指令。代價是當輸入剛好已經有序時，sorting network 仍然執行所有 compare-exchange、不像 insertion sort 那樣可以提早結束——但因為完全沒有 misprediction，固定成本的 sorting network 在小陣列上的實測吞吐反而穩定勝出。

實作上，2 到 12 每一個大小都有一段專屬的、人工或工具產生的最佳 network——不同大小的最佳 compare-exchange 序列不同，沒辦法用一個通用迴圈涵蓋，所以這部分是分大小展開的程式碼。這是用程式碼體積換速度的典型取捨：十幾段針對固定大小特化、展開的 network，每一段都是直線無分支的指令流，編譯器可以把它們排得很緊、暫存器配置也固定。對只有少數元素的子陣列，這種「全展開、零分支」的收尾比任何帶迴圈帶分支的通用排序都快。

median-of-medians：大 partition 的 pivot 與壞輸入偵測

branchless partition 把「掃過一遍資料」這件事做到了極致，但 quicksort 的整體複雜度仍取決於 pivot 選得好不好。pivot 選得爛——例如每次都挑到接近最小或最大的元素——partition 會極度不平衡，遞迴深度退化到 O(n)、總比較數退化到 O(n²)。blqsort 對較大的 partition 採用 median-of-medians 策略來挑 pivot：把資料分組、各組取中位數、再對這些中位數取中位數，得到一個保證落在「不會太偏」區間內的 pivot。這比單純取頭尾中三個值的 median-of-three 更穩健，能擋掉更多刻意構造的壞輸入。配合前面的 branchless 引擎，pivot 計算裡的比較也盡量用展開的、固定次數的迴圈來做，避免在 pivot 選擇這一小段又把分支引回來。

但再好的 pivot 啟發式都可能被對抗性輸入打穿，所以 blqsort 還有一層即時的壞輸入偵測。它在 partition 進行時觀察兩側的大小：如果偵測到嚴重的不平衡（partition 一面倒），它會切換到 heapsort 來處理那一段。heapsort 的最壞情況是 O(n log n)、沒有 quicksort 那種 O(n²) 的退化坑，代價是常數項較大、cache 行為較差——所以它只在偵測到 quicksort 要退化時才被當作保險拉出來用，這正是 introsort 家族的核心思想（pdqsort、libstdc++ 的 std::sort 也都有類似的 heapsort 後援）。除了不平衡偵測，blqsort 還會檢查 partition 是否已經有序：如果一段資料本來就排好了，提早辨認出來可以直接跳過、不做無謂的遞迴。對「幾乎有序」這種實務上極常見的輸入（append-only log、時間序列、已排序後小幅更動的資料），這個檢查能把整體成本壓得很低。它還能把相等的元素聚在一起，避免在大量重複 key 的資料上退化——這也是 pdqsort 著名的 strength。

把這幾層放在一起，blqsort 的控制流大致是：大 partition 用 median-of-medians 挑 pivot、用 1024-block 的 branchless 引擎切開；偵測到嚴重不平衡就對那段切 heapsort；偵測到已排序就跳過；遞迴到 2–12 元素就交給 sorting network 收尾。下面這個小工具讓你掃一遍「mispredict 機率」這個變數，看 branchless 與 branchy 兩種 partition 的建模成本怎麼隨之分岔——關鍵是找到那個 crossover：在多高的 mispredict 率之上，多搬一倍資料才開始划算。

這個模型把問題化約成最乾淨的形式：branchless 的每元素成本是固定的（大約兩次 copy 加一次 compare，與資料無關，所以是一條水平線）；branchy 的成本則是「一次 compare 加上 p 乘以 flush penalty」，隨 mispredict 率線性上升。兩線的交點告訴你：只要 mispredict 率高於某個門檻（在 flush penalty 16 cycle、branchless 固定成本約 3 cycle 的假設下，這個門檻只有百分之十幾），多搬一倍資料就開始划算。而隨機資料的 partition mispredict 率接近 50%——遠在 crossover 右側，所以 branchless 大勝。反過來，對已經有序、分支極好預測的資料（p 接近 0），branchy 反而便宜——這也是為什麼 blqsort 要先做「是否已排序」的檢查，把那種輸入分流到不必要付 branchless copy 成本的快路徑。

fallback：非平凡型別切 BlockQuicksort，只搬 index

整個 branchless-copy 的論證有一個沒明說的前提：copy 必須便宜。對 double、int 這種 trivially-copyable 的型別，一次 copy 是一條 store，把它做兩倍幾乎無感。但如果元素是一個帶 heap 配置的 std::string、一個有自訂 copy constructor 的物件、或任何 non-trivially-copyable 的型別呢？這時「無條件搬一次，可能還要被覆寫」就不再是一條便宜的 store——它可能是一次記憶體配置、一次深拷貝、一次 constructor 呼叫。把昂貴的 copy 做兩倍，前面那筆「用 copy 換 misprediction」的帳直接翻負。

blqsort 的解法是：偵測型別是不是 trivially-copyable，不是的話自動切到 BlockQuicksort 變體。BlockQuicksort 的關鍵 insight 是——你不需要 branchless 地搬資料，你只需要 branchless 地計算出「哪些元素該換到哪邊」這份排列。所以它先用 branchless 的方式處理一批元素的index：掃過一個 block，把「需要被換到另一側」的元素的 index 無條件寫進一個小的 index 緩衝、用 0/1 推進緩衝長度（跟前面 partition 的 trick 一模一樣，只是寫的是 index 而非資料本身）。index 是 trivially-copyable 的整數，搬兩倍完全沒問題。等到這批 index 算完，才真正去移動資料，而且因為已經知道精確的對應關係，可以用最少次數的 swap 完成——「processes only the element indices in a branchless manner and then moves the actual data with fewer swaps」。

這條 fallback 的精神是把「branchless」這個好處留在便宜的整數運算上，把「昂貴的資料移動」這件事用 swap 次數最小化來保護。對 non-trivially-copyable 的型別，一次 swap（三次 move）仍然比一次「無條件 copy、可能浪費」便宜得多，尤其當 move 語意可以避免深拷貝時。最終結果是：branchless 的分支消除好處還在（在 index 計算階段），但資料移動回到「只動必要次數」的紀律。下面這個 tab 把兩條 path 並排——trivially-copyable 走「branchless copy 整個資料」、non-trivial 走「branchless 算 index、最少 swap 搬資料」——讓你看清楚同一個 branchless 原則在兩種型別上的不同落點。

// 直接搬資料：write head 用比較結果推進
out[head] = data[i];          // 無條件 store（便宜）
head += (data[i] < pivot);    // 0 或 1，無分支

// 代價：~2x copy；收益：零 data-dependent branch
// 淨值為正，因為 copy 是一條 store、misprediction 是 ~16 cyc

// 階段一：branchless 收集要換邊的 index（便宜的整數運算）
idx_buf[cnt] = i;
cnt += (data[i] >= pivot);    // 0/1 推進，無分支

// 階段二：依 idx_buf 配對，用最少次數 swap 真正搬資料
for each (l, r) in paired offsets:
    swap(data[l], data[r]);   // move 語意，避免深拷貝

// branchless 好處留在 index 計算；資料只動必要次數

值得強調，這個型別分派在 C++ 版是編譯期決定的——blqs::sort 用 std::is_trivially_copyable 之類的 trait 在 compile time 選 path，沒有 runtime 的型別判斷成本。C 版則靠使用者透過 macro 明示型別與比較子。這也意味著對 trivially-copyable 的快路徑，編譯出來的碼裡完全沒有「檢查型別、跳到另一條 path」的分支——分派本身也是 branchless 的。

benchmark：50M doubles 與 structs 上的實測

論證再漂亮，也要看數字。blqsort 在 50,000,000 個 double 與 50,000,000 個自訂 struct 上、分別在 Apple M1 與 AMD Ryzen 上對照 std::sort 與 pdqsort。先講 doubles：在 M1 上 std::sort 與 pdqsort 都是 1.33 s，blqsort 單執行緒 0.97 s——快約 27%。在 Ryzen 上差距更戲劇化：std::sort 5.56 s、pdqsort 2.81 s、blqsort 2.06 s。注意 pdqsort 在 Ryzen 上就已經把 std::sort 打了快一倍（pdqsort 本身也是 branchless-aware 的設計），blqsort 在 pdqsort 之上再快約 27%。

struct 的數字更能說明 branchless copy 的威力。50M 個自訂 struct：M1 上 std::sort 與 pdqsort 都是 3.46 s，blqsort 只要 0.96 s——快了三倍多。Ryzen 上 std::sort 4.75 s、pdqsort 4.72 s、blqsort 2.20 s，約兩倍。為什麼 struct 的相對優勢比 double 還大？因為 struct 較大，branchy 版在搬運與比較時的 cache 與分支壓力都更重，而 blqsort 的固定成本搬運模式對這種 workload 的 locality 更友善——只要這個 struct 仍是 trivially-copyable，branchless copy 路徑就成立。下面這張圖把四組情境（doubles／structs × M1／Ryzen）的三方對照畫成 grouped bars，數字直接取自原文。

還有兩個面向沒進這張圖。一是多執行緒：blqsort 提供 blqs_thr.h（C++、走 std::thread）與 blqsort_thr.h（C、走 pthreads）兩份多執行緒 header，在 M1 上相對單執行緒版「再快 3 到 4 倍」。quicksort 的遞迴結構天生好平行——partition 完的兩半互不相依，可以丟到不同執行緒——所以這個加速符合預期。二是這些是單一來源的 benchmark，跑在作者的機器上、用作者選的資料分佈；任何排序 benchmark 都對輸入分佈、key 型別、機器的 cache 階層與 branch predictor 實作高度敏感。把這些數字當成「在這類 workload 上 branchless 路線值得一試」的證據，而不是「blqsort 在所有情況都快 N 倍」的保證——尤其在已排序、幾乎有序、或大量重複 key 的資料上，三者的差距會被各自的特化路徑（blqsort 的已排序檢查、pdqsort 的 pattern-defeating 啟發式）重新洗牌。

API：四份 single-header 與兩種語言

落到實際使用，blqsort 是四份 single-header 檔案，按「語言 × 執行緒模型」分成 2×2：blqs.h（C++ 單執行緒）、blqs_thr.h（C++ 多執行緒，std::thread）、blqsort.h（C 單執行緒）、blqsort_thr.h（C 多執行緒，pthreads）。single-header 的意義是沒有 build 步驟、沒有連結階段——把標頭丟進專案、#include 就能用，跟它要對標的 std::sort、pdqsort 一樣是 header-only 的接入體驗。

C++ 端的 API 故意做得跟 std::sort 同形，用 iterator pair：

#include "blqs.h"

// 跟 std::sort(data, data + SIZE) 同形
blqs::sort(data, data + SIZE);

這個同形是刻意的——它讓 blqsort 成為 std::sort 的 drop-in，遷移成本低到只是換一個函式名。型別分派（trivially-copyable 走 branchless copy、否則走 BlockQuicksort）在 blqs::sort 內部用 trait 在編譯期自動完成，使用者不需要知道自己的型別走哪條 path。C 沒有 template，所以 C 版改用 macro 在 #include 之前注入型別與比較子：

#define BLQS_CMP(a, b) ((a) < (b))
#define BLQS_TYPE double
#include "blqsort.h"

// 之後直接呼叫
blqsort(data, SIZE);

BLQS_CMP 定義了「小於」的語意、BLQS_TYPE 給定元素型別，header 被 include 時用這兩個 macro 把排序碼針對這個型別特化展開。這是 C 世界用 macro 模擬 C++ template 特化的經典手法——把型別與比較邏輯在 preprocess 階段內聯進來，編譯器看到的是針對 double 完全展開、沒有 function pointer 間接呼叫的碼。比起 C 標準庫 qsort 那種「比較子是 function pointer、每次比較都要一次間接呼叫且無法 inline」的設計，macro 特化讓比較被 inline、迴圈被向量化的機會大得多——這本身就是 qsort 在實務上慢的主因之一。

這套零件湊起來解鎖了什麼：把一個 textbook partition 的 if 改寫成 smlen += (x < pivot)，再用 1024-element 的 stack block 雙向搬運、用 sorting network 收尾、用 median-of-medians 配 heapsort 後援守住最壞情況、最後用 BlockQuicksort 替非平凡型別止血——blqsort 把「branch misprediction 是排序熱路徑上最大的隱形稅」這個微架構觀察，變成一份可以 drop-in 替換 std::sort、對 trivially-copyable 資料實測快 1.3 到 3.6 倍的 single-header library。它沒有發明新的排序演算法；它只是認真對待了一件大多數實作忽略的事——在隨機資料上，CPU 猜分支猜錯的代價，比多搬一倍便宜的 byte 貴得多。