GitHub、文字列比較の高速化技術「ケースフォールディング」をメモリ速度で実装

記事の3ポイント

1. 1

   ケースフォールディングと小文字変換の明確な区別

   表示用である小文字変換（locale 依存）とは異なり、比較用のケースフォールディングは文脈に依存しない対称的な関係を保つため、Unicode CaseFolding.txt の単純な対応のみを実装する。

2. 2

   非 ASCII バイトでの早期停止を廃止した最適化

   ソースコードの大部分が ASCII であるという前提に基づき、最初の非 ASCII バイトでループを中断する従来の手法よりも、分岐なしでバッファ全体を掃引する方が高速であることを実証した。

3. 3

   Rust クレート「casefold」のオープンソース化

   GitHub が Blackbird のインデックス作成やクエリ処理で得た知見を基に、メモリ速度で動作するケースフォールディングライブラリとして Rust クレート「casefold」を公開した。