技術
7 個のトリガーバイトを 12 GB/s で探す: Teddy を選んだ理由
aozora は青空文庫記法の Rust パーサで、字句解析の最初のフェーズが「ソース全体から 7 種類のトリガーバイトを探す」というマルチパターンスキャンになっている。この記事は、その 1 フェーズに Intel Hyperscan 由来の Teddy アルゴリズムを採用した経緯と、対立候補に勝った算術的な根拠を整理したもの。 handbook の対応章: SIMD scanner backends。 問題設定 aozora-pipeline の Phase 1 (字句解析の最初のフェーズ) は、ソース文字列の中から次の 7 文字の出現位置を全て列挙する。 | 《 》 ※ [ ] 全角空白 これらは青空文庫記法の構文トリガー (ルビ・注釈・字下げの開始/終了マーカ) で、出現する位置だけが分かれば後段のフェーズで「これは何の構文か」を解釈できる。 UTF-8 で見ると 7 文字