這篇文章是 GitHub 工程團隊撰寫的技術文章,說明公司內部的程式碼搜尋引擎 Blackbird,如何針對「case folding(大小寫摺疊)」這個基礎文字處理步驟做效能優化。case folding 是讓「café」與「CAFÉ」這類只差在英文大小寫或重音的文字,能被視為相同以利搜尋比對,Blackbird 必須用這套處理來應付高達 480TB 的原始碼資料。
文章的關鍵發現是:把程式寫成「看到非 ASCII 字元就提早跳出迴圈」反而比較慢,因為這種提早結束的分支會讓編譯器沒辦法把運算向量化。改成整個緩衝區一路無分支掃描到底,並用算術運算而非條件判斷式來決定要不要改寫大寫,實測在 Apple M4 晶片上,處理速度從每秒 3.1 GiB 提升到超過 45 GiB,達到記憶體頻寬的上限。團隊也設計了一份僅 1776 位元組的精簡對照表來處理 Unicode 字元。
這個結果之所以受到工程社群關注,是因為它顛覆了「提早結束迴圈一定比較快」的直覺,示範了在現代 CPU 上,能被向量化的簡單迴圈,往往比看起來聰明但充滿分支判斷的程式碼快上十幾倍。GitHub 也把這套 case folding 的實作以 casefold 套件的形式開源到 Rust 的套件庫 crates.io,讓其他專案可以直接使用。
這篇文章技術含量偏高,牽涉到 CPU 向量化與位元運算,比較適合已經有一定程式基礎、對效能優化有興趣的學生參考,而不是初學者的入門教材。不過裡面有一個很好的觀念值得讓孩子知道:寫程式時感覺比較聰明的寫法(提早跳出迴圈)不見得真的比較快,實際測量、拿數據說話,才是判斷程式好壞的正確方法。
開源開發工具演算法