- ASTをポインタでつながったオブジェクトグラフとして持つのではなく、単一配列とインデックスで表現すると、コンパイラ向けデータ構造のメモリ配置と管理方法が単純になる
- Rustの例では、
Box<Expr>を**ExprRef**に置き換え、ExprPoolにadd/getを追加する程度の小さな変更でフラット化されたASTを実装している
- 約1億個のASTノードを生成して即座に解釈するマイクロベンチマークでは、通常実装は3.1秒、フラット化実装は1.3秒で、2.4倍高速になった
- 性能差は、連続したメモリ配置による局所性、64ビットポインタの代わりに32ビットインデックスを使う小さな参照、低コストな割り当てとプール単位の解放によって生じる
- 配列では子が親より前に位置するという性質を活用すると、再帰的な木の走査が線形実行に変わり、bytecodeインタプリタに近い形へつながる
フラット化の基本アイデア
- Arenaまたはregionは現代の言語実装で広く使われており、ここで扱う方式は、単一の型だけを格納するarenaを単純な配列のように使うデータ構造のフラット化である
- ポインタの多いデータ構造で、ポインタを配列インデックスに置き換える手法であり、中心的な例はASTだが、他のコンパイラ用データ構造にも適用できる
- サンプルコードはflatcalcリポジトリにあり、通常実装とフラット化実装の違いはブランチ比較で見られる
- コード変更の幅は小さいが、マイクロベンチマークでは2.4倍の高速化が現れ、性能以外にもコードの使いやすさの面で利点がある
一般的なAST表現
- 例の言語は、整数リテラルと4種類の二項算術演算子だけをサポートする、非常に単純な算術式言語である
- 可能なプログラム例は
42、0 + 14 * 3、(100 - 16) / 2である
- Rustでの表現は
BinOpとExpr enumで構成される
Expr::Binary(BinOp, Box<Expr>, Box<Expr>)Expr::Literal(i64)
- Rustの
Box<Expr>はExprを指すポインタに相当し、CのExpr*と似た役割を果たす
- パーサ、出力フォーマッタ、インタプリタは典型的な構造で、インタプリタは
Exprに対する再帰メソッドとして書かれる
- 算術意味論は、すべての式が最終的に
i64として評価されるように構成されている
- 加算・減算・乗算はwrapping演算を使う
- 0による除算は
checked_divを使って0を返すように処理する
- 固定PRNG seedを使うランダムプログラム生成器により、パースと出力のコストなしでAST操作性能を測定する
ASTを配列とインデックスに置き換える
- フラット化は2つの変更から成る
Exprオブジェクトをヒープに個別割り当てせず、1つの連続配列に格納する- 子ノードをポインタではなく、配列内のインデックスで参照する
- Rustの例では、
ExprPoolをVec<Expr>のnewtypeとして定義する
struct ExprPool(Vec<Expr>);
- 既存のポインタの役割は、32ビット整数ベースの
ExprRefが担う
struct ExprRef(u32);
- 中核となる型の変更は、
Binaryの子フィールドをBox<Expr>からExprRefに変えることだ
enum Expr {
Binary(BinOp, ExprRef, ExprRef),
Literal(i64),
}
ExprPoolには、新しいExprを入れるaddと、ExprRefでExprを取り出すgetユーティリティが追加される- パーサは
Exprを直接返すのではなく、ExprPoolにノードを追加したうえで**ExprRef**を返す
- インタプリタも
ExprメソッドではなくExprPoolメソッドになり、パターンマッチの前にself.get(expr)で参照を逆参照する
- 全体の変更は、
Box<Expr>をExprRefに置き換え、必要な箇所にaddとgetを入れる程度の小さなものだ
性能上の利点
- フラット化されたASTの代表的な利点はメモリ局所性である
- 通常のポインタベース
Exprにはメモリ断片化のリスクがある
- フラット化された
Exprは連続メモリ領域に密集しているため、データキャッシュとprefetcherがよりうまく働く可能性がある
- 十分に賢いメモリアロケータが似た効果を出せるかもしれないが、密な配列を使えば不確実性は減る
- 参照サイズも小さくなる
- 通常のポインタは現代アーキテクチャでは64ビットである
- ASTノードが4,294,967,295個以下で済むなら、32ビット参照で十分である
- 参照ごとに50%の容量削減が可能で、ポインタの多いASTでは全体のメモリ使用量削減につながりうる
- さらに小さなデータ構造なら16ビットや8ビット参照も可能である
- 割り当てコストが下がる
- ノードごとに
mallocを呼ぶ必要がない
- 十分なメモリを事前確保していれば、tail pointerを増やすだけのbump allocationで新しい
Exprの領域を作れる
- 解放はプール単位で処理できる
- 個々の
Exprを解放しない前提がある
- 多くの言語実装ではASTはまとめて生成され、まとめて消える傾向がある
- 通常のASTはポインタをたどって各ノードを解放する必要があるが、フラット化ASTでは
ExprPool全体を一度に解放できる
- Arena allocationの紹介では低コストな解放が主な理由として強調されがちだが、コンパイラ文脈ではASTがコンパイル終了まで保持されることもあり、解放は最も重要度の低い理由かもしれない
コードの使いやすさの面での利点
- フラット化はライフタイム管理を単純化する
- n個のノードを持つASTを、n個のライフタイムではなく1つのASTライフタイムとして考えられる
- Rustではこの単純化がコード上のlifetime表現にも直接影響する
&Exprたちのlifetimeを管理する代わりに、u32であるExprRefを渡し、ExprPoolのライフタイムに依存できる
- 同じ単純さは、C++のように手動メモリ管理を行う言語にも当てはまる
- フラット化された配列は重複排除を実装しやすい
hash consingや、より単純な方法で同一式の生成を避けられる- 例えば、0から127までの頻出
Literal式をExprPoolの先頭128スロットに予約しておける
- 整数リテラル
42が必要なとき、新しいExprを作る代わりにExprRef(42)を返せる
- ポインタベース表現でも似たことは可能だが、補助データ構造が必要になる可能性が高い
マイクロベンチマーク結果
- ベンチマークでは、約1億個のASTノードを持つランダムプログラムを生成し、そのままインタプリタに入力する
- パーサと出力フォーマッタは含まれない
- 1つのプログラムを生成して即実行する方式であり、現実的なベンチマークではない
- 実験条件にはいくつか制約がある
Vec<Expr>にプログラム全体を収めるのに十分な容量を事前予約している- 実環境ではarenaサイズの見積もりがさらに必要になる
- 生成と実行以外の作業がほとんどなく、低コストな割り当て・解放の利点が誇張される可能性がある
- プログラムが大きすぎてCPUキャッシュに収まる割合が小さく、局所性の効果が過小評価される可能性がある
- HyperfineでノートPC上の10回実行平均を比較している
- 環境はM1 Max 10コア 3.2GHz、メモリ32GB、macOS 13.3.1、Rust 1.69.0である
- 通常実装は3.1秒、フラット化実装は1.3秒で、2.4倍の高速化を示した
- 解放コストを別に見るため、両実装でdeallocationをスキップするバージョンも作った
- フラット化実装はno-free版と標準版の時間がほぼ同じで、解放時間は大きくなかった
- 通常実装は3.1秒から1.9秒に短縮され、約**38%**をメモリ解放に使っていた
- no-free版どうしを比べても、フラット化実装は通常実装より1.5倍高速だった
フラット化表現を直接活用したインタプリタ
- フラット化は当初、通常の割り当てとポインタを置き換える内部実装変更のように使われたが、配列表現の性質そのものを直接利用することもできる
Exprが不変なら、子ノードを先に作り、親ノードを後で作る必要がある
a * bを作るとき、aとbはそれを参照する*よりExprPool内で前に位置する- 参照の矢印は配列内で常に後ろから前へ向き、データフローは前へ進む
- この不変条件を使えば、ルートから再帰的に下る代わりに、
ExprPoolを先頭から末尾までスキャンするインタプリタを作れる
- 走査は常に子を親より先に訪れる
- 各式の結果は
stateベクタに保存する
- 二項式は子の
ExprRefインデックスでstateを参照して値を取り出す
- 最後に要求された
rootに対応する結果を返す
- この「extra-flat」インタプリタには再帰呼び出しのスタック管理がなく、
ExprPoolを線形走査できる
- その一方で、大きな
stateベクタにランダムアクセスする必要があり、局所性には不利かもしれない
- 結果として、extra-flatインタプリタは1.2秒、再帰ベースのフラット化インタプリタは1.3秒で、8.2%改善した
Bytecodeインタプリタとのつながり
- Bob NystromのRedditコメントでは、この方式は実質的にbytecodeインタプリタのアイデアを再発明したものだと見ている
Expr構造体はbytecode命令のように振る舞い、変数参照はu32でエンコードされた参照のように入っている- 単純な
stateテーブルをスタックのような構造に変えると、最初から設計したbytecodeインタプリタとほとんど変わらなくなる
- ASTデータ構造を変えただけなのに、木の走査方式からbytecode方式へ自然に移行していく
関連資料
- コンパイラ文脈でのフラット化に関する資料
- 言語実装以外の性能志向分野でも似たアイデアが現れる
- Inanna MalickのRust製おもちゃ電卓言語の記事も同じ手法を適用しており、Haskell界隈のrecursion schemeの考え方もあわせて使っている
1件のコメント
Hacker Newsのコメント
Blender（3Dモデリングソフトウェア）は、この方式の興味深い事例。ファイルの読み込み/保存を高速かつ無損失にするため、ディスク上の表現とメモリ上の表現を同一にしている
つまり、すべてがアリーナ内にあり、保存/読み込みはアリーナ全体を
memcpyするのに近い。Blenderプロジェクトの潜在的な複雑さやシリアライズ/デシリアライズの問題を考えると、優れた設計に見える欠点は、古いバージョンのファイルも開けなければならないため、データ構造の設計が固定化しやすいこと
古いアプリのバージョンのデータをロードするときだけこうした変換を実行し、その後は更新済みバージョンとして直ちにディスクへ保存すれば、同じコストを再び払う必要はない
CRDTの文脈で作られたhttps://www.inkandswitch.com/cambria/は、この概念の実装例であり、直接適用できなくても良い着想になる
I/Oフレームワークの良し悪しにかかわらず構造体をそのままシリアライズしてしまうので、永遠にその構造に縛られると分かっており、常に将来を見越してデータ構造を設計しなければならなかった。暗黒時代だった
そのためコンバータ作成が大きな問題となり、文書化されていないWord内部のデータ構造を解読しなければならなかった記憶がある
ディスク上のファイルを改変できるなら、すでにその時点で機器を掌握しているという意味だった。そのおかげでロードはばかばかしいほど高速で、すべてをメモリに読み込んだあと、ポインタ位置を実際のロード先アドレスにパッチしていた
平坦化された抽象構文木が好きだ。pulldown-cmarkのインラインマークアップ処理で使われている方式が特に気に入っている。簡単な説明はhttps://fullyfaithful.eu/pulldown-cmark/にある
生の入力はノード列に分割され、
*のようなものは強調になる可能性もあれば、対応する相手がなければテキストのまま残る可能性もあるので、MaybeEmphasisノードになる次の段階ではスタックを使って順番にノードを走査し、対応しうる組を探す。組が見つかると、
MaybeEmphasisノードを適切な強調ノードに変換し、開始ノードと終了ノードの間にあるノード列全体を切り出して新しいノードの部分木にするこの木変換はかなり独特で、単純な実装では簡単にO(n)になりうるが、平坦化されたAST表現ではノード数やスタック深さに関係なく**O(1)**で処理できる
詳しい木表現はhttps://github.com/raphlinus/pulldown-cmark/blob/b7e709c0bd6...にあり、基本的にはノード本体とともに
child、nextインデックスを持つ。強調マッチング時の木の手術コードはhttps://github.com/raphlinus/pulldown-cmark/blob/b7e709c0bd6...にある性能は非常に高い。pulldown-cmarkが単独で最速のCommonMarkパーサーではないかもしれないが、十分に競争力があり、たとえばノードごとに割り当てるアプローチよりはるかに速い
Rustを称賛していたGDC発表を思い出した。Rustは借用チェッカーのせいで頭がおかしくなるか、さもなければエンティティコンポーネントシステムでコードを構造化するように仕向ける、という内容だった
複雑なライフタイム問題がある実例では、借用チェッカーの価値は、結局すべてを配列に入れてインデックスで参照し、借用チェッカーをできるだけ避ける方法を探すようになる点にある、というのが面白い
オブジェクト同士が直接参照しなくなるので型システムの有用性が大きく下がり、コードを推論するのが非常に難しかった。とても大きなシステムでは有用になるのだろうと信じているが、自分が書いていた小さなプログラムでは、ほとんど障害物に近かった
ゲーム、データベース、組み込み、高性能計算的なバッチ処理、さらにはコンパイラもこれに当てはまる
もちろん依然としてエイリアシング制限はあるのでデータ競合は起きないだろうが、生ポインタで生じるバグと本質的に同じバグは依然として起こりうる
その過程で借りる側は常に所有者より短く生き、所有中に確保されたメモリにしかアクセスできない。所有者が死ねば解放され、その後は誰もそれを使ったり再解放したりできないので、use-after-free、二重解放、未割り当てメモリアクセスを避けられる
Cでアリーナがメモリ安全性の問題を解決するという奇妙な主張もあるが、プログラムによっては、むしろダングリングポインタやuse-after-freeなどを同じように引き起こす可能性がある
同じ問題がC/C++とRustの両方で、少し違う形で現れる
2か月前にこの記事へ残した自分のコメント: https://old.reddit.com/r/ProgrammingLanguages/comments/1350d...
要するに利点は非常に現実的だが、欠点もあわせて語るべきだ。アリーナはメモリ安全性を後回しにし、所有権が扱いにくくなることがあり、変更やリスト/ベクタへの追加も複雑になり、ポインタ表現のほうがデバッガには親しみやすい
この記事の下部に自分のWikiページがリンクされていて、実際のコードと測定値があるのでありがたく見た: https://github.com/oilshell/oil/wiki/Compact-AST-Representat...
Prologの項もWarren Abstract Machine(WAM)ではヒープ上でこのように表現される。記事の例のように
+(*(a,b), c)というPrologの項を演算子記法で書くと次のようになるexpr(E) :- E = a*b + c.すると仮想マシンのグローバルスタックに平坦化された表現が作られる。Scryer Prologでは
?- wam_instructions(expr/1, Is), maplist(portray_clause, Is).でWAM命令を確認できる結果は
put_structure(*,2,x(3)).,set_constant(a).,set_constant(b).,put_structure(+,2,x(2)).,set_value(x(3)).,set_constant(c).,execute(=,2).のようになる2つの複合項はどちらも線形化され、ヒープ上では関数子の後ろに引数が続く形で置かれ、それぞれがWAMのメモリセル1つをちょうど占める。引数は別のメモリセルを指すことがある
ヒープはこうしたセルの配列で、すべてのセルは同じ具体型を持つ。たとえばScryer Prologはセルごとに8バイトを使うので、64ビットアーキテクチャではセルへのアクセスと変更が非常に効率的だ
「ヒープに
Exprオブジェクトを大量に割り当てる代わりに、1つの連続配列に入れ、子はポインタではなくその配列のインデックスで参照する」というのは、平坦化というより代替的なヒープ表現に近い。ASTの形そのものは変わっていないLisp系のようにconsセルや他のオブジェクトを配列に入れ、バンプアロケーションとインデックスポインタを使う形で、多くの言語がすでにやってきた方式だ
オブジェクトが配列にあれば、マークが終わった後でガベージコレクタがスイープ段階で巡回しやすい。マーク段階ではグラフをたどって到達可能なオブジェクトを見つけ、スイープ段階では平坦な配列を走査してGCビットを消し、到達不能なオブジェクトを再利用対象として印を付ける
ある程度本格的なLisp実装で、consセルごとに
mallocを個別に呼ぶものは簡単には見つからないはずだ。そうするとGCのスイープ段階のためにグローバル連結リストへ入れるか、ポインタだけを入れるグローバル配列が必要になる週末に作ったおもちゃのLispプロジェクトで、consセルを
mallocしてリークさせ、GCを巨大なTODOとして残しているものは少なくとも2回見たことがあるセルが圧縮配列ヒープから来る場合でも、結局はグローバル配列が生じうる。たとえばコピーしないアロケータで世代別ガベージコレクションを実装するとき、若いオブジェクトを集めて高速なGCサイクルでスイープするために補助配列へ追加でき、その配列がnurseryを表すことがある
良い記事ですが、2つの落とし穴があります
タグ付きユニオンも可能ですが、メモリ使用量をうまく扱う必要があります
「仮想メモリ」の仕組みによって、断片化した物理メモリ領域を連続した仮想メモリ領域としてつなぎ合わせられます。もし仮想アドレス空間がセグメント化されていたなら、そもそも断片化は起きず、どのメモリ領域も他の領域と衝突せずにその場で常に拡張できたはずです
そうであれば
realloc()の実装からmemcpy()経路をなくせたでしょうに、残念です内部は安全ではないでしょうが、読み取り専用の安全なインターフェースは実現できそうです。解放は O(n) になるでしょうが、それでもツリーよりずっと速いはずです
最初のポインタが常に正確に次のノードを指すと分かったあとでも、ノードにポインタ（「参照」）が2つ残っているのには驚きました
https://github.com/rswier/c4 がそういう方式を使っているのを見たことがあります。もちろんコードの可読性は良くありませんが、より小さくて高速です
メモリ管理で アリーナ と言うと、「フラット化」よりも単にアリーナアロケータを連想します
同じ寿命を持つ項目を多数割り当てるとき、1つ以上の大きなメモリ塊からより効率的に割り当て、共通の寿命が尽きたら個々の項目ではなく大きな塊を解放する方式です
親の塊の空間を順番に使っていくだけなので、汎用ヒープアロケータのようなフリーリストが不要で、割り当てもより効率的になりえます
この文脈で、ポインタの代わりにインデックスを使う「フラット化」は、親の塊を基準にした相対ポインタ、つまりオフセットを使うことだと見ることもできます
メモリが極端に制限された組み込み環境向けのJavaScriptパーサおよびインタプリタである V7(https://github.com/cesanta/v7) を実装したとき、こうした 簡潔なAST構造 を使っていました
後にはASTからバイトコードへコンパイルする段階に切り替えましたが、しばらくの間は暗黙的なASTを解釈中に直接たどっていました
https://yaml2sql.netlify.app にある自分の Yaml to Sql コンパイラでも似たようなことをしました
フラット化の過程は少し変ですが面白く、最終的には費やした労力に見合う価値がありました
たとえばブール式のフラット化は、試してみたい人には良い練習課題です: https://github.com/revskill10/yaml2sql/blob/main/app/query.r...