7 個のトリガーバイトを 12 GB/s で探す: Teddy を選んだ理由
aozora は青空文庫記法の Rust パーサで、字句解析の最初のフェーズが「ソース全体から 7 種類のトリガーバイトを探す」というマルチパターンスキャンになっている。この記事は、その 1 フェーズに Intel Hyperscan 由来の Teddy アルゴリズムを採用した経緯と、対立候補に勝った算術的な根拠を整理したもの。
handbook の対応章: SIMD scanner backends。
問題設定
aozora-pipeline の Phase 1 (字句解析の最初のフェーズ) は、ソース文字列の中から次の 7 文字の出現位置を全て列挙する。
｜ 《 》 ※ ［ ］ 全角空白
これらは青空文庫記法の構文トリガー (ルビ・注釈・字下げの開始/終了マーカ) で、出現する位置だけが分かれば後段のフェーズで「これは何の構文か」を解釈できる。
UTF-8 で見ると 7 文字 × 3 バイト = 21 バイト分のパターンを探すことになる。青空文庫の典型的な作品は 500KiB 前後で、本文は日本語が大半なので各文字が 3 バイト、トリガーバイトの出現密度は 1KB あたり 1 個前後しかない。ほとんどミスする探索 をいかに速く回すか、というのが性能上の主題になる。
handbook の章で言及している通り、この Phase 1 のスキャンが Phase 2 以降の解釈処理を 1 桁上回る時間を占めるので、SIMD で殴る価値が出る。
候補 1: memchr3 を 7 回回す
memchr クレートには複数バイトを同時に探す memchr3 がある (最大 3 バイトまで同時探索可能)。これで素直に書くと:
// 擬似コード
for trigger in TRIGGERS.chunks(3) {
for offset in memchr3(trigger[0], trigger[1], trigger[2], src) {
record(offset);
}
}
7 パターン × 3 バイト = 21 バイトに対して memchr3 は 1 回で 3 バイトしか同時に扱えないから、最低でも 7 回 (各パターンに 1 パス) ソースを舐めなおすことになる。1 パスごとにソース全体を SIMD レーンで流す勘定なので、純粋に 読み込み回数が 7 倍 になる。
memchr 自身の packed multi-pattern API (新しめのもの) を使えば 1 パスにできるが、内部が SSE2 16 バイトレーンに固定されているため、aozora のコーパス計測では 5 GB/s 程度で頭打ちになる。
候補 2: Teddy
Teddy は Intel Hyperscan の中核アルゴリズムで、aho-corasick クレートの packed::teddy モジュールから直接呼べる。
挙動の概略:
- パターン群 (最大 64 パターンまで) から SIMD shuffle table を構築する
- 入力を AVX2 で 32 バイトずつ取り、shuffle table と照合する
- 候補となるオフセット集合を生成し、各候補で本物の一致かを最終確認する
aozora の用件と Teddy の得意領域がきれいに重なる。
- パターン数が小さい (7 ≤ 64): Teddy は N ≤ 64 の小さい N で本領を発揮する
- パターンが短い (UTF-8 で 3 バイト): 32 バイトレーンに 10 パターン分が同時に乗る
- パターン同士に共通プレフィクスが無い: 全角句読点同士なので Boyer-Moore 系の suffix table は効かない。Teddy は構造に依存しない
ベンチマーク
aozora-bench の corpus probe (青空文庫全作品、AVX2 有効、Linux x86_64) で計測:
| バックエンド | ターゲット | スループット | 選択条件 |
|---|---|---|---|
| Teddy | x86_64 + AVX2 | 約 12 GB/s | AVX2 が使える時の第 1 候補 |
| Hoehrmann DFA | ポータブル | 約 3.5 GB/s | x86_64 fallback、native arm64 等 |
| Memchr-multi | wasm32 | 約 1.2 GB/s | wasm SIMD proposal が乗るまで |
Teddy が memchr3 7 パスより約 3.5 倍、memchr の packed path より約 2.5 倍速い。
AVX2 が無い環境: Hoehrmann 系 DFA
x86_64 でも AVX2 が無い CPU や、Rosetta 経由で動く Docker コンテナ、Alpine ビルドのような場面ではフォールバックが必要。aozora は regex-automata の dense::Builder でビルド時に高密度バイト DFA を生成しておき、ランタイムでこちらに切り替える。
DFA は遷移表を引くだけで分岐がない (Aho-Corasick の NFA + failure link 走査と違って 1 バイトあたり 1 回のテーブル参照で済む) ため、ポータブル経路でも 3.5 GB/s が出る。Aho-Corasick の標準実装に対しては 2 倍程度速い。
バックエンドの切り替えはコンパイル時 cfg! ではなく runtime detection。
pub fn best_scanner_name() -> &'static str {
if is_x86_feature_detected!("avx2") {
"teddy"
} else if cfg!(target_arch = "wasm32") {
"memchr-multi"
} else {
"hoehrmann-dfa"
}
}
docker run --platform linux/amd64 を arm64 Mac で動かすと AVX2 が無い x86_64 が降ってくるので、コンパイル時固定だと SIGILL で落ちる。runtime dispatch にしておけば 1 バイナリで両方カバーできて、配布物は (linux-gnu, darwin-arm64, windows-msvc) の 3 種で済む。
整理
aozora の Phase 1 スキャナで Teddy を採用したのは、
- パターン数 (7) が Teddy の得意領域 (N ≤ 64) に収まり、
- パターン長 (3 バイト) が AVX2 32 バイトレーンに乗りやすく、
memchr37 パスや memchr packed path に対して算術的に 2.5–3.5 倍の差が出るため。
AVX2 が使えない環境向けには Hoehrmann 系 DFA をフォールバックとして同梱し、runtime dispatch で 1 バイナリにまとめている。
実装は aozora-scan クレートにある。handbook の scanner.md には Hoehrmann DFA を Aho-Corasick textbook NFA より選んだ理由や、samply で実際にどのバックエンドが走っているか確認する手順も書いてある。