早期終了は禁止：GitHubがメモリ速度でソースコードのケースフォールディングを実現

Don't stop early: Case-folding source code at memory speed

GitHubのコード検索エンジンBlackbirdは、1億8000万以上のリポジトリ、480TB以上のソースコードを処理します。その際、すべてのバイトにケースフォールディング（大文字小文字の正規化）を適用します。この処理を高速化するため、開発者は直感に反する最適化を発見しました。ASCIIパスで最も効果的なのは「早期終了」を削除することでした。分岐をなくし、ベクトル化を可能にすることで、処理速度は3 GiB/sから45 GiB/s以上に向上しました。さらに、Unicodeのケースフォールディングを効率的に処理するために、テーブルを1776バイトに圧縮し、文字のデコードを回避する方法も紹介します。この成果はRustクレート「casefold」としてオープンソース化されました。