二分查找被擊敗：一個工程師的SIMD野路子

「Virtually all processors today have data parallel instructions.」——當算法研究者Daniel Lemire寫下這句話時，他正在做一件看似瘋狂的事：挑戰計算機科學里最經典的二分查找。

沒人覺得二分查找慢。它是對數復雜度，是教科書級別的優雅。但Lemire盯著Roaring Bitmap里那些16位整數數組，發現了一個被所有人忽略的細節：現代CPU的SIMD指令，一次能比較8個值，而二分查找每次只比較1個。

為什么二分查找成了瓶頸

Roaring Bitmap是一種流行的壓縮數據結構，內部用數組存儲16位整數，長度從1到4096不等。查找某個值是否存在，標準做法是二分查找。

二分查找的邏輯很直觀：取中間元素對比，目標小就查左半，大就查右半。C++里用std::binary_search一行搞定，返回布爾值表示是否存在。

但Lemire算了一筆賬：每次迭代只消除一半數據，卻要付出一次內存訪問和分支預測的代價。對于4096個元素，最壞情況要12次迭代。而現代CPU的內存并行度（memory-level parallelism）早已能同時加載多個值——二分查找的串行結構，反而成了硬件能力的浪費。

更關鍵的是SIMD（單指令多數據）。ARM和x64處理器都支持用一條指令同時比較8個16位整數。二分查找卻堅持"一次比一個"，像開著跑車送外賣。

四分查找+SIMD的混合野路子

Lemire的解法叫SIMD Quad算法，核心是兩步分層搜索：

第一步，把數組切成16元素一塊的固定區塊，用最后一個元素作為插值鍵（interpolation key）。不是二分，是四分——每次把搜索空間切成四份，快速定位到目標可能在哪個區塊。

第二步，用SIMD指令一次性比較區塊內全部16個元素。ARM和x64都支持這條指令，零分支，純數據并行。

插值搜索（interpolation search）在這里扮演關鍵角色。不同于二分查找機械地取中點，插值搜索根據目標值的分布估算位置，對均勻數據能逼近O(log log n)的比較次數。Lemire把它用在區塊邊界的粗粒度定位上，避免了對數級別的逐層下沉。

四分而非二分，是另一個反直覺設計。更多分割意味著更多指令，但指令數從來不是瓶頸——內存延遲才是。四分查找減少迭代深度，讓CPU的亂序執行和預取有更多發揮空間。

性能數字：快了多少

在Roaring Bitmap的典型場景（數組長度1-4096）中，SIMD Quad相比標準二分查找有顯著加速。具體幅度取決于數組長度和硬件，但核心優勢來自兩個維度：

比較次數：插值搜索將區塊定位的比較次數從O(log n)壓縮到接近常數；SIMD把最終區塊內的比較從最多16次降到1條指令。

內存訪問模式：固定大小的16元素區塊對CPU緩存極度友好，預取器能準確預測下一步加載位置。二分查找的跳躍式訪問則不斷刷新緩存行。

分支預測：SIMD比較無分支，消除了二分查找最頭疼的預測失敗懲罰。對4096長度的數組，12次迭代的二分查找意味著12次潛在的分支冒險。

Lemire的代碼已開源。他沒有動Roaring Bitmap的數據結構，只是替換了查找算法——這種"即插即用"的優化路徑，對生產系統尤其有吸引力。

一個更廣泛的啟示

這件事的有趣之處，不在于某個具體加速比。它揭示了一個被忽視的優化空間：經典算法的復雜度分析，往往假設"一次操作一個單位成本"，但現代硬件的成本結構早已不同。

SIMD讓"批量比較"和"逐個比較"的成本幾乎相同。內存并行度讓"同時加載多個位置"成為可能。插值搜索在均勻數據上的理論優勢，終于能在實際硬件上兌現。

二分查找誕生于1946年，那時計算機還是電子管時代。它的數學正確性無可置疑，但"最優"的定義變了——從最小化比較次數，變成最小化實際時鐘周期。當硬件能力曲線和算法假設出現錯位，就是野路子機會出現的時候。

Roaring Bitmap選擇16位整數和4096長度上限，當初是為了壓縮效率和緩存對齊。Lemire的發現是：這些設計參數恰好落在SIMD的甜點區。這不是刻意優化，是架構約束和硬件特性的一次意外共振。

類似的錯位還有多少？B樹的分支因子、哈希表的負載因子、排序算法的遞歸深度——這些數字大多來自 decades-old 的硬件假設。用今天的CPU特性重新掃描一遍基礎數據結構，可能是低垂的果實。

當然，SIMD Quad并非萬能。它對數據分布有要求（插值搜索在極端偏斜數據上會退化），對數組長度有要求（太短則SIMD啟動 overhead 不劃算，太長則需要更深的分層）。但在Roaring Bitmap的特定場景里，它證明了經典算法可以被擊敗。

最后留個思考題：你手頭的代碼里，有多少"理所當然"的算法選擇，其實從未被硬件特性重新檢驗過？