消除分支之後：二元搜尋為何能快上 6.5 倍
pythonspeed.com · 2026-07-11
原始問題
這篇文章由 Itamar Turner-Trauring 發表於 pythonspeed.com，主題是二元搜尋（binary search）在真實 CPU 上的效能表現，往往和教科書上的 O(log n) 分析對不上號。文章從最標準的 if/else 版本二元搜尋出發，逐步拆解編譯器產出的組合語言，指出真正拖慢速度的並非演算法本身，而是CPU 對每一次比較分支的預測行為。作者測量發現，原始版本執行時有高達 16.6% 的分支預測失誤率——這個數字遠高於一般迴圈程式碼，原因是搜尋區間的走向（往左或往右）本質上是資料相依、無法被硬體規律學習的。
分支預測與硬體行為
現代 CPU 為了維持管線（pipeline）滿載，會用分支預測器先猜測接下來要執行哪一條路徑並提前運算，等到真正的比較結果出爐才確認對錯。文章原句是：「To ensure fast execution, the CPU has a branch predictor that heuristically chooses which branch to execute in parallel.」一旦猜錯，CPU 必須把已經投機執行（speculative execution）的結果整個丟棄，重新從正確分支開始，這個代價在現代處理器上可能是十幾個時脈週期。二元搜尋的分支模式幾乎無法預測，因為每次比較的結果都取決於你搜尋的值，不像一般迴圈有固定的重複模式。
解法是把 if/else 換成條件選擇（conditional move），讓 CPU 兩條路徑都算完、再用一個不涉及分支的指令挑出正確答案。作者在 Rust 中用 select_unpredictable 達成這件事：
left = select_unpredictable(
less_than(boundaries[middle], value),
middle,
left,
);這個寫法把「跳或不跳」的決策從分支指令變成一個純資料運算，CPU 不需要猜測，也就沒有預測失誤的懲罰。文章同時把迭代次數固定為 log2(桶數)，讓整個迴圈變成規律、可被編譯器攤平（unroll）的結構。
效能實測
作者的最終版本疊加了三項優化：拿掉邊界檢查（unsafe bounds-check elimination）、重排迴圈讓編譯器能做 SIMD 自動向量化，以及針對 x86-64-v3 目標編譯。三者合計後，分支預測失誤率從 16.6% 降到 0%，整體執行時間也大幅縮短。
| 版本 | 執行時間（µs） | 相對加速 | 分支預測失誤率 |
|---|---|---|---|
| Classic（標準版） | 45,981 | 1.0× | 16.6% |
| Branchless v3（最終版） | 7,106 | 6.5× | 0.0% |
文章強調這整個過程沒有換掉演算法——搜尋的複雜度依然是 O(log n)，差異完全來自於編譯出的機器碼如何配合 CPU 的執行方式，也就是文章標題所說的「mechanical sympathy」。
原始來源：6× faster binary search: from compiled code to mechanical sympathy
從 MariaDB 搬到 SQLite：Lobsters 論壇如何用單一檔案資料庫撐住尖峰流量
lobste.rs · 2026-07-11
原本的問題
技術新聞社群 Lobsters（lobste.rs）長年使用 MariaDB 作為後端資料庫。促成這次遷移的直接導火線，是社群對 K1 收購 MariaDB 這件事的疑慮，開發者 thomas0 在 2025 年 6 月正式接下遷移任務，社群一度討論過 PostgreSQL，但最後選擇了更輕量、單檔案的 SQLite 作為務實方案。第一版 PR 在 2025 年 8 月提出，後來因為擱置太久被關閉；第二次嘗試則補上了效能測試與資料遷移腳本，PR 討論串就在 lobsters/lobsters#1927。
遷移方式
SQLite 和 MariaDB 在型別與排序規則上有不少差異，團隊必須逐一填坑：
- 無號整數不相容：SQLite 不支援 unsigned bigint，原本 MariaDB 用來存 ID 的欄位得改成一般 bigint。
- 排序規則變窄：MariaDB 用的是
utf8mb4_general_ci，SQLite 對應改用NOCASE，但 NOCASE 只認得 ASCII 字元，無法處理完整的 Unicode 大小寫折疊（case folding）。 - 自訂函式補齊：SQLite 原生沒有
regexp、if、stddev這類函式，團隊自行實作使用者定義函式（UDF）把它們補上，盡量減少對原本查詢邏輯的改動。 - 全文檢索改用 Contentless-Delete Tables，這是 SQLite 內建 FTS 機制裡專門為效能優化設計的資料表型態。
第一次正式上線是在 2 月 21 日，結果唯讀查詢流量瞬間把所有 CPU 都打到 100%，團隊緊急回退。事後排查發現問題出在幾張大表的全表掃描（full table scan）缺少索引，加上一個 N+1 query 的隱藏效能陷阱。修完這兩個問題後，第二次部署在 7 月 11 日（週六）重新上線。
實際效果
上線後遇到週一的流量高峰，SQLite 版本撐了下來。討論串裡的第一手回報是：「cpu usage is down, memory usage is down, site seems to be snappier」。單檔案的 SQLite 資料庫目前大約 3.8GB，等到原本的 MariaDB 執行個體正式除役後，VPS 成本預估可以砍半。這個案例某種程度上呼應了近年 SQLite 社群一直在推的論點：對於讀多寫少、單機可承受的網站規模，拿掉一個獨立資料庫伺服器、換成進程內嵌的檔案資料庫，反而能省下網路往返與維運複雜度。
原始來源：lobste.rs is now running on SQLite、lobsters/lobsters PR #1927
侏儸紀公園片場裡的真實電腦：SGI、蘋果與思考機器的鉅細靡遺考證
fabiensanglard.net · 2026-07-13
電影中的畫面
知名技術部落客 Fabien Sanglard 在這篇長文裡，逐格重看 1993 年的電影《侏儸紀公園》控制室場景，把片中每一台看似「未來科技」的電腦都對應回真實存在的 1990 年代硬體。最經典的畫面莫過於 Lex Murphy 那句「這是 Unix 系統，我知道怎麼用」——她操作的其實是 SGI 工作站上一個叫 fsn 的實驗性 3D 檔案總管，畫面裡她瀏覽的目錄是 /usr，子目錄還帶著故意加了空格的「Visitor.Center」字樣。片中反派 Dennis Nedry 觸發的鎖定畫面「White Rabbit」（檔名 whte_rbt.obj），把他自己的臉疊在貓王的緊身衣上，也是這篇文章重點還原的彩蛋之一。
實際使用的硬體/軟體
文章統計，片場總共借用了價值約 172.5 萬美元的電腦設備，其中 87.5 萬美元來自 Silicon Graphics（SGI）、35 萬美元來自 Apple，其餘則是額外採購或租借。控制室裡出現的機器包括：
- SGI IRIS Crimson：Dennis 的主力工作站，紅色機殼，搭載
R4000/R4400處理器，畫面上曾顯示 3D 西洋棋程式。 - SGI R4000 Indigo：Ray Arnold 用來跑颶風 3D 動畫的工作站。
- Macintosh Quadra 700（片場共 3 台）：Motorola
68040@ 25MHz，Dennis 桌上兩台、Ray 桌上一台，其中一台螢幕播的是電影《大白鯊》。 - Thinking Machines CM-5 超級電腦（5 台）：每台配備 Sparc CPU 加四個向量運算單元、32MB RAM，單價高達
46,000美元，機身上一整排會隨機閃爍的紅色 LED 純粹是裝飾，沒有實際功能意義。Dennis 在片中的台詞還直接點名它：「You know anybody who can network 8 connection machines and debug 2 million lines of code for what I bid?」 - Apple PowerBook 100：Alan Grant 在行動拖車裡用的筆電，Motorola 68000 @ 16MHz，跑的是
System 7.0.1。 - PLI Mini Array 外接磁碟陣列：Dennis 桌邊疊了五台、Ray 兩台，1GB 版本當年售價
3,598美元。 - Motorola Envoy PDA：Dennis 桌上那台掌上裝置，其實電影 1992 年 8 到 11 月拍攝時這款產品根本還沒上市（要到 1995 年 2 月才發售）。
考證細節
Motorola Envoy 出現在片中曾是多年懸案——電影拍攝時間早於產品正式發售兩年多，直到有 Hacker News 網友指出：frogdesign 創辦人曾在飛機上向史匹柏展示過一台量產前的原型機，才解開這個時間矛盾。片中控制室黑板螢幕上一閃而過的原始碼，最初被誤認成一般 Mac OS API 呼叫，後來同樣被 Hacker News 網友考證出那其實是 MPW（Macintosh Programmer's Workshop）寫的 Pascal 程式碼。文章也抓出一個穿幫鏡頭：Dennis 桌邊那五台 PLI Mini Array 早期鏡頭是面朝左邊，等到 Ray 接手同一張桌子後，同一批磁碟陣列卻莫名其妙轉向面朝右邊；而不論哪個鏡頭，這些磁碟陣列上的指示燈其實始終沒有亮起，暗示它們根本沒有真正通電運作。
Sanglard 還原了拍攝現場的幕後安排：Michael Backes 帶領的四人團隊，其實提前六個月就把控制室螢幕上會出現的所有動畫都預先算好存進硬碟，開拍時由幕後操作員透過對講機聽現場口令，即時把對應的畫面送到片場對的那台螢幕上——換句話說，演員在鏡頭前操作的「即時運算」，其實是一群人在片場旁邊克難搭起的機房裡手動播放出來的。fsn 檔案總管在電影上映後迴響太好，SGI 後來甚至直接在官網打出「YOU SAW IT IN JURASSIC PARK!」的廣告詞。