文字比較に使う大小文字の統一処理で、入力の途中で止まる判定を取り除くことが高速化につながった。GitHubの測定では、ASCIIのみの入力に対し、Apple M4の単一コアで3.1GiB/sだった処理が45GiB/s超に達した。
コード検索の比較処理をライブラリ化
大文字と小文字を区別せずにコードを検索するには、比較する文字の表現をそろえる必要がある。GitHubのコード検索エンジンBlackbirdは、検索用インデックスを作る際、文字列の断片であるngramを抽出する前に、全バイトへケースフォールディングと呼ぶ比較用の変換を施す。
GitHubは、この処理を高速化したRustライブラリcasefoldをオープンソース公開した。変換対象はUnicodeで定められた1文字対1文字の対応で、複数文字へ展開する変換やトルコ語向けの変換は含めない。例えば、ßをssへ変換する処理は対象外となる。
非ASCIIの判定をループの外へ移す
ASCIIの大文字は小文字へ変換し、それ以外のバイトはそのまま残す。最適化した処理は、非ASCIIバイトを見つけても途中で終了せず、各バイトのビットORを一つの値に蓄積する。全体の走査が終わってから蓄積値の最上位ビットを調べれば、入力に非ASCIIバイトが含まれていたかを判定できる。
大文字かどうかの判定も、分岐を使わない演算へ置き換えた。各バイトからAに相当する値を折り返し減算し、結果が26未満かを調べることでAからZを識別する。その判定結果をビット演算で書き込みへ組み込み、大文字だけを小文字に変えながら、各バイトへの書き込み自体は毎回行う。
16バイトずつの処理で45GiB/sを超える
途中終了とデータに依存する条件分岐を除くと、コンパイラは複数バイトをまとめて処理できる。GitHubによると、LLVMはこのループから16バイト単位で動くNEON命令を生成する。
GitHubがApple M4の単一コアで5.7KBのASCIIのみのバッファを測定したところ、最適化した実装は45GiB/s超となった。非ASCIIバイトで終了し、大文字の場合だけ書き込む比較用の実装は3.1GiB/sだった。この数値が示すのはASCII処理の速度であり、Unicode文字を含む入力全般の処理速度ではない。
分岐の除去だけでは速度は上がらない
GitHubの同じ測定では、早期終了を残したまま大文字の判定と書き込みだけを分岐なしにすると、ベクトル化されず、速度は2.6GiB/sに下がった。GitHubは、小文字や数字など変更不要なバイトにも毎回書き込むため、書き込み量が増えると説明している。
別の比較では、まずASCII部分を走査し、その部分を別の処理で変換する二段階方式が約23GiB/sだった。この方式は検出と変換でデータを二度読み出す。最適化したループは、非ASCIIバイトの検出と大文字の変換を一度の走査に組み込んでいる。