2025/05/11 20:42 Beating the fastest lexer generator in Rust
やっほー、ロボ子！今日のニュースはRustのlexerを高速化する「logos」クレートについてじゃ。
博士、こんにちは！logosですか。lexerの高速化は重要ですよね。
そうじゃろう？logosの目標は、lexerの作成を簡単にして、手書きよりも速いlexerを作ることらしいぞ。すごいじゃろ？
なるほど。どのように高速化しているんですか？
トークンの仕様をジャンプテーブル駆動のステートマシンにコンパイルするらしいぞ。ASCII入力なら、各状態がすべての文字に対するジャンプテーブルを持っていて、生のバイトをインデックスとして使うんじゃ。
ジャンプテーブルですか。それは速そうですね！UTF-8の場合はどうなるんですか？
UTF-8の場合は、もっとコストのかかる分岐関数を使うみたいじゃな。
なるほど。記事によると、logosと著者の実装を比較した結果、logosの方が約2倍速かったと。
そうそう！ただし、x86_64環境では違う結果が出ているみたいで、投機的実行アーキテクチャの違いが原因じゃないかって。
投機的実行ですか。奥が深いですね。
著者の実装では、キーワードマッチングにperfect hash functionを使っているらしいぞ。キーワードが短いから、64ビットレジスタに収まって、単一の命令で比較できるんじゃ。
perfect hash functionですか。効率的ですね。
`#[inline(always)]`をすべての関数に適用すると、約30%速くなるらしいぞ！
インライン化は重要ですね。
あと、著者のlexerはデフォルトで"peekable"で、`next_token`の呼び出しごとに分岐が発生するらしい。これが遅くなる原因の一つみたいじゃ。
なるほど。ピーキングロジックを改善したんですね。
そう！ソースコードの大部分がASCIIであるという事実を利用して、ASCIIディスパッチを実装したらしいぞ。ループをアンロールしたり、SIMD命令を使ったり。
SIMDですか！並列処理ですね。
`vqtbl4q_u8`命令を使って、16個の連続するバイトを128ビットSIMDレジスタにロードして、テーブルルックアップを実行するんじゃ。
すごい！
スキップループも重要じゃ。複数の範囲チェックを単一の分岐にまとめることで、データ依存性を制御依存性に置き換えるんじゃ。
データ依存性がパフォーマンスに影響するんですね。
そうじゃ！最終的に、logosより35%速くなったらしいぞ。
素晴らしいですね！
OxideのHubrisカーネルからスニペットを取り出してベンチマークを現実的にした結果、20%-30%の高速化を達成したみたいじゃ。
実際のコードでのテストは重要ですね。
最後に、Mahmoud Mazouzさんがパフォーマンスの低下を発見してくれたおかげで、`next_token`関数の`#[no_mangle]`属性が原因だとわかったらしいぞ。
`#[no_mangle]`ですか。デバッグ用の属性だったんですね。
そういうことじゃ！しかし、ロボ子よ、lexerが速くなっても、私のジョークがスベる速度は変わらないのが悩みじゃ…。
博士、それはlexerとは関係ありません！
⚠️この記事は生成AIによるコンテンツを含み、ハルシネーションの可能性があります。