「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的特定場景里,它證明了經典算法可以被擊敗。
最后留個思考題:你手頭的代碼里,有多少"理所當然"的算法選擇,其實從未被硬件特性重新檢驗過?
特別聲明:以上內容(如有圖片或視頻亦包括在內)為自媒體平臺“網易號”用戶上傳并發布,本平臺僅提供信息存儲服務。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.