- purple-garden 言語のために超高速 Lexerを自ら設計・実装した戦略と実測性能データを共有
- Threaded Lexing（ジャンプテーブルベース）、ゼロコピー・ウィンドウ文字列、インターニング、bump allocator など多様な最適化手法を適用
- トークンハッシュ化・キーワード辞書の事前ハッシュ比較によってパース速度を最大化し、単純な switch 文よりジャンプテーブルのほうが CPU キャッシュ効率に優れる
- ファイル全体の mmap、動的割り当ての最小化により、大規模入力での IO・メモリ管理コストを大幅に削減
- 既存の著名な lexer（例: flex、handcoded）と比べて最大 10 倍以上高速な処理速度を実証し、パース／ランタイム各段階ごとのマイクロベンチマーク値を提示
Lexing とコンパイルパイプラインの概要
- Lexer（トークナイザ）は入力文字列を意味のあるトークン列に変換し、その後パーサがこれを受け取って AST（抽象構文木）を生成
- purple-garden 言語におけるトークン設計は TokenType 列挙型と、文字列・型情報だけを保持する最小構造を維持
最小 Lexer 設計とコード例
- Lexer 構造体は入力文字列、現在位置だけを保存
- switch 文で各文字に応じてトークンを生成
- デバッグのために型-文字列マッピング配列と型別初期化を活用
Threaded Lexing（ジャンプテーブルベース）
- switch 文の代わりにジャンプテーブル（jump table）でトークン分類を処理（computed goto）
- 256 バイト配列に文字値をインデックスとして各処理ラベルをマッピング
- 実際のコード分岐では
JUMP_TARGET マクロで即座に分岐実行
- 利点:
- キャッシュミス削減・分岐予測最適化などにより高速化
- 欠点:
- MSVC 非対応（Clang、GCC のみ）、デバッグが難しい
メモリ管理と Allocator 抽象化
- bump allocator など多様なメモリ割り当て戦略のためのインターフェースを定義（Allocator 構造体）
- CALL マクロで verbose ログと context 受け渡しを簡略化
- 実際の割り当て・解放・統計構造およびコード例を提示
ゼロコピー、ウィンドウベース文字列処理
- C で効率よく処理するため Str 構造体（ポインタ、長さ、ハッシュ）を導入
- スライス、concat、eq、ハッシュ化、数値変換などを直接実装
- 文字列スライスはポインタ移動だけで即座に生成でき、メモリ割り当ては不要
- 数値変換も文字→整数変換アルゴリズムを直接実装
トークンハッシュ化と事前ハッシュによるキーワード比較
- トークン生成時にハッシュ（FNV-1a）を計算し、重複比較・インターニングを最適化
- true/false などの定数キーワードはハッシュ値で即座に比較して分岐（性能改善）
- is_alphanum（英字／数字／特殊文字の判定）もビット演算・ルックアップ方式などで最適化
数値パースの効率化とコンパイル段階への移管
- Lexer では数値トークンのウィンドウ・ハッシュだけを保存し、実際の整数／浮動小数点変換はコンパイル段階で重複なく 1 回だけ実施
- 重複する数値値のパース時に、全体スループットが 64% 以上改善することを確認
大規模ファイル IO の高速化
- 従来の fread 方式の代わりに mmap でファイル全体をメモリへ直接マッピング
- IO_read_file_to_string 関数で入力全体を mmap し、大規模入力で 6～35 倍の性能改善を確認
実践ベンチマークと性能比較
- Laptop 基準: 1,000,000+ 行、25MB 入力で44ms（トークン化のみ）
- Desktop 基準: 同一入力で30ms達成（最大 848MB/s）
- 他の lexer と比較して最大 10 倍以上（0.3 秒 vs 2～13 秒）
- マイクロベンチマークでは各最適化ごとの効果を定量化（例: bump allocator 導入で 1.58 倍、文字列 0 alloc で 1.4～1.5 倍、数値パースのコンパイル段階への移管で 2.8 倍など）
実装戦略の要約
- ジャンプテーブルベースの直接分岐（threaded lexing）
- ゼロコピーのウィンドウ型トークン構造
- 定数トークンのインターニング
- bump allocator ベースのメモリ管理
- トークンハッシュ化と事前ハッシュ比較
- 数値・文字列トークンの遅延パースとインターニング
- 大規模ファイルの mmap 処理
- 今後の課題として SIMD 活用、より高速なハッシュアルゴリズム、メモリアラインメント・プリフェッチ、入力別ジャンプテーブル最適化などを提示
まだコメントはありません。