blqsort：無分支快速排序如何在 AMD Ryzen 上超越 pdqsort 36%
tiki.li · 2026-06-04（ICML 2026 前後）
blqsort 是一套以 無分支（branchless）技術重新設計的快速排序實作，提供 C 與 C++ API，在 50 億個 double 元素的排序測試中，單執行緒效能分別達到 Apple M1 0.97 秒、AMD Ryzen 2.06 秒，而 pdqsort（libc++ 與 Rust 標準庫的排序基礎）在相同平台分別為 1.33 秒與 2.81 秒。
核心改動
傳統 quicksort 分區（partition）步驟的主要瓶頸是條件跳躍：每次比較都可能導致 CPU 分支預測器失敗，造成 pipeline flush。blqsort 使用一個 1,024 元素的輔助堆疊緩衝區，左右交替寫入而不插入條件分支，讓比較結果只影響指標偏移量而非控制流。
樞軸選擇採用 median-of-medians，並針對全等元素、已排序輸入等退化情境做偵測，確保最壞情況不落回 O(n²)。對 2 到 12 個元素的子陣列，演算法切換到預先設計好的 排序網路（sorting networks），以固定步驟完成排序，徹底排除條件跳躍。
對於不能低成本複製的型別（如 std::string），blqsort 改用 BlockQuicksort 變體：先無分支地計算元素應移動的索引序列，再批次執行移動，減少昂貴複製操作的次數。
效能數據
| 實作 | Apple M1（50M doubles） | AMD Ryzen（50M doubles） |
|---|---|---|
| std::sort | 1.33 s | 5.56 s |
| pdqsort | 1.33 s | 2.81 s |
| blqsort（單執行緒） | 0.97 s | 2.06 s |
自訂結構體（50M 元素）測試中差距更明顯：pdqsort 在 M1 與 Ryzen 分別為 3.46 s 與 4.72 s，blqsort 為 0.96 s 與 2.20 s，差距達 3.6x。多執行緒版本在 M1 上可再獲 3–4x 加速。
API 使用
// C++（標頭 blqs.h）
blqs::sort(data, data + SIZE);
// C（需先 define 型別與比較函式）
#define BLQS_CMP(a, b) ((a) < (b))
#define BLQS_TYPE double
#include "blqsort.h"
blqsort(data, SIZE);多執行緒版本分別對應 blqs_thr.h（C++）與 blqsort_thr.h（C）。整個實作為單一標頭檔，無外部依賴。
原始來源：tiki.li blog
IPv6 Zone ID 為何在 URL 中是個錯誤——以及 Go 標準庫的處理方式
xeiaso.net · 2026-06-05
IPv6 link-local 位址（如 fe80::4%eth0）使用百分號（%）附加 zone identifier，指定封包應從哪個網路介面送出。然而 URL 規範同樣以 % 開頭進行百分比編碼，兩者語義衝突，導致 Go 的 net/url 解析器在遇到 http://[fe80::4%eth0]:80 時直接拋出錯誤：invalid URL escape "%et"。
規格細節
RFC 6874 規定，URL 中的 IPv6 zone ID 必須先將 % 本身編碼為 %25，因此合法形式是 http://[fe80::4%25eth0]:80。這意味著開發者需要雙重編碼，並且在顯示給使用者時必須反向解碼——造成容易出錯的非對稱操作。
問題不只在 Go。Nginx、Python requests、以及各大瀏覽器對此的支援都不完整。瀏覽器的限制尤其根本：zone ID 會破壞「origin」的定義——同一個 fe80::1 在 eth0 與 eth1 上是不同的通信端點，但 Web 安全模型以 scheme+host+port 三元組來界定 origin，無從容納 zone 的概念。
影響範圍
在大多數伺服器端應用中，服務綁定在全球可路由位址上，zone ID 從不出現。但 容器網路、本地開發環境、以及 IoT 裝置直連場景下，link-local 位址使用頻率較高；當程式碼需要透過 HTTP 客戶端連接同一機器上的其他服務，且只有 link-local 位址可用時，就會撞上這個問題。Go 的解法是在 net.Dial 層面支援 zone（透過 net.TCPAddr.Zone 欄位），但一旦位址先經過 url.Parse 就會失敗，要求使用者顯式做 %25 編碼後再傳入。
原始來源：xeiaso.net