AST およびその他のコンパイラ用データ構造のフラット化

• アリーナまたはリージョンは、コンパイラやコンパイラに似たものに対するシンプルで効果的な技法です。
• アリーナを使って抽象構文木（AST）をフラット化すると、性能を向上させつつ利便性も得られます。
• フラット化とは、AST ノードを単一の配列に詰め込み、ポインタの代わりに配列インデックスを使うことを意味します。
• フラット化された AST には、局所性の改善、参照の小型化、低コストな割り当てと解放といった利点があります。
• フラット化された AST はメモリ管理を簡素化し、便利な重複排除を可能にします。
• 性能結果は、フラット化されたインタプリタ版が通常版より 2.4 倍高速になり得ることを示しています。
• AST のフラットな表現を活用することで、再帰を取り除き、線形走査を利用して性能をさらに向上させることができます。
• この記事では、プログラミング言語インタプリタにおいて、データ構造のフラット化によって達成された性能向上について論じています。
• さらに、フラット化されたインタプリタは、再帰インタプリタと比べて 1.2 秒対 1.3 秒で、8.2% の性能向上を示します。
• この技法は、実質的にはバイトコードインタプリタのアイデアを再発明したものであり、Expr 構造体はバイトコード命令として使われます。
• LuaJIT、Sorbet type checker、Oil shell などに関連する、データ構造のフラット化についての他の記事やプロジェクトにも言及されています。
• ビデオゲーム、シリアライズ済みデータ処理、データ指向設計、エンティティ・コンポーネント・システムといった分野でも、フラット化や局所性最適化に関する類似の概念が登場します。
• この記事では、Rust で実装されたおもちゃの「電卓」言語に同じ技法を適用した Inanna Malick の投稿を読むことも勧めています。
• Rust でこの技法を使う際の制約についても議論されており、Expr 構造体の内部に別の Expr をインラインで含められないという限界があります。
• 性能比較は、M1 Max プロセッサと 32GB メモリを搭載した MacBook Pro で、macOS 13.3.1 と Rust 1.69.0 を実行した環境で行われました。

[GN⁺]

Hacker Newsの意見

• Blender は、高速で損失のないファイルの読み込みと保存のために、ディスク上とメモリ上で同じ表現を使用します。
• 効率的なインラインマークアップ解析のために、pulldown-cmark では平坦化された AST が使われています。
• 平坦化された AST 表現により、ノード数やスタック深さに関係なく O(1) のツリー変換が可能になります。
• pulldown-cmark の性能は、他の CommonMark パーサーと比べて卓越しています。
• Warren Abstract Machine (WAM) は、Prolog 用の平坦化された表現をヒープ上で使用します。
• AST の平坦化は、Lisp のような言語ですでに使われていた概念です。
• サイズ変更可能な配列にノードを保存することはメモリ割り当ての問題を引き起こす可能性がありますが、ページサイズのブロックでプーリングすることで緩和できます。
• AST ノードがコード内でどのように表現されるかには注意が必要であり、不要なパディングは避けるべきです。
• ポインタの代わりにインデックスを使うと、より小さく高速なコードを得られます。
• 特定のシナリオで有用なカスタムメモリアロケータを使って、平坦化メモリを実装できます。
• メモリ制約のある環境で JavaScript パーサーとインタープリタを実装するために、簡潔な AST 構造が使用されました.