- サイズの異なるvariantを持つenum/tagged unionを大量に保存すると、最大variantを基準にした領域予約のため、
VecやHashMapでパディングと断片化のコストが大きくなる
- Zigは
comptimeと型リフレクションを通じてフィールドサイズ・アラインメント・discriminantを確認し、enumコンテナをメモリレイアウト基準でジェネリックに変えられる
- 単純な
Vec<Enum>は各要素が最大variantサイズ分の領域を使い、SoAはタグのパディングを減らすが、値領域のvariant fragmentationは残る
- 同じサイズのvariantをまとめるdense AoVAは、例のenumでは15個のベクタを2・4・8バイトの3クラスタに減らすが、同じallocationに複数のvariantが混在すると型安全な走査が難しくなる
- Rustのproc macroは型サイズ・アラインメント情報にアクセスしにくく、genericな配列長の計算にも制約があるため、Zigの型認識stagingはシステムコードにおけるメモリ効率の合成可能性をよりよく示す
Rustのenum配列が浪費する領域
- サイズの異なるvariantを持つenum/tagged unionは、最大のvariantを格納できるだけのメモリを予約する必要がある
- 例のenum
Fooはu8、u16、u32、u64のvariantを持ち、タグとアラインメントのため型サイズが16バイトになる
- このようなenumを
VecやHashMapに大量に入れると、各要素が最大variantを基準に領域を占有し、パディングと断片化が大きくなる
- タグを別allocationに置く**struct of arrays（SoA）**変換は一部のパディングを減らすが、variantサイズの違いから生じる値領域の断片化まではなくせない
- Rustでも特定のenum向けデータ構造を自作することはできるが、任意のenumに対して可能な限りメモリ効率のよいジェネリックなデータ構造を作るのは難しく、事実上ほぼ不可能に近い
- proc macroはサードパーティ型やtype aliasに
#[derive]を付けるのが難しく、合成可能性が低い
- 型認識がなく、
generic_const_exprベースの回避策は冗長なwhere節を呼び出しグラフに広げ、generic type parameterとうまく合わない
コンパイラASTで問題が目立つ理由
- 効率的なenum配列の大きな動機の1つは、コンパイラASTのメモリ使用量である
- 大きなASTはコンパイル中にメモリ遅延とキャッシュevictionを引き起こし、フロントエンド性能に大きなコストを生む
- Chandler CarruthのCarbon compiler動画では、パース済みのclang ASTが元のソースコードより50倍多いメモリを消費することがよくあるとされている
- Rustで式ノードを表現する例は
Expr enumで構成される
UnitNumberBinary(Operation, ExprId, ExprId)Ident(Symbol)Eval(ExprId, ExprSlice)BlockExpression(ExprId, StatementSlice)
- OCamlはランタイムシステムとGCがメモリ管理を担うため、明示的なindirectionなしに再帰データ型を表現できる
- Rustの
Vec<Expr>はすべての要素がsizeof(Enum)分の領域を使い、これには最大variantサイズとタグ、パディングが含まれる
SoAとAoVAで断片化を減らす
- 単純な3-variant enumが8・16・32ビットサイズのメンバーを持つ場合、通常の
Vecは32ビットvariantとアラインメント条件に合わせるため、すべての要素に大きな領域を予約する
- よくある改善策はtagged indexなどを使い、enum variant自体を小さく保つ方式である
- Rust compilerの
tagged_index crate
- small-string optimizationの事例
- 言語ランタイム、GC、コンパイラ、ゲームエンジン、OSカーネルのような高性能コードでよく使われる最適化である
- コンテナを変え、discriminantと値を別allocationに保存するSoA方式も可能である
- self-hosted Zig compilerがこの方式を使っている
- タグによって生じるパディングは減るが、union値のcollectionには依然としてvariant fragmentationが残る
- Zigのstaged compilationは、任意の型に対してSoA変換を行うコンテナをジェネリックに作れる
- Rustは
soa_deriveのようなproc macroに依存する必要があり、サードパーティ型のソースを変えずに#[derive]を付けられないという制約がある
variant別配列とサイズ別クラスタリング
- 値領域の断片化をさらに減らすには、variantごとに1つのベクタを持たせることができる
- 挿入時には、enumタグと該当variant配列内のindexを一緒に含むtagged indexを返す
- このパターンは**array of variant arrays（AoVA）**と呼ばれる
- AoVAはRustではproc macro、Zigでは
comptimeで実装できる
- variantが多く、同じサイズのvariantが複数あると、variant別ベクタが過剰に増える
- 例の
Foo enumは15個のvariantを持つ
- variant別ベクタ方式は15個のベクタを追加する
- 再割り当てとシステムコール数が増える可能性があり、naiveな
Vecと比べてamortizationにより多くのメモリが必要になることがある
- ベクタがメモリ上に任意に散らばり、キャッシュconflictの可能性が高まる
- AoVAコンテナ自体も多くのメモリを使い、内包される構造体を膨らませる可能性がある
- サイズ別にまとめると、例のenumは2バイト、4バイト、8バイトの3クラスタに分かれる
c_2: Vec<[u8; 2]>はAからDまでを保存するc_4: Vec<[u8; 4]>はEからIまでを保存するc_8: Vec<[u8; 8]>はJからOまでを保存する
- dense AoVA方式は全体のベクタ数を**80%**減らせる
- 異なるvariantを同じallocationに一緒に置くと、ベクタを型安全に走査するのが難しくなる
- アクセスは挿入時に作られたtagged pointerを通じてのみ可能である
- blind iterationが不要なflattened indexベースのtree構造では、受け入れられるtrade-offになり得る
- 型安全な走査が必要なら、パディングコストを受け入れてタグを戻すこともできる
- パディングが大きすぎる場合は各variant配列にSoA変換を適用できるが、この場合ベクタ数は2倍になる
Zigのcomptimeが生むメモリレイアウトの合成可能性
- Zigプロトタイプはosmiumに実装されている
- 核心は、コンパイラbuilt-inでフィールド型、バイトサイズ、ビットサイズ、discriminantを検査するコンパイル時リフレクションである
- 例のコードは
@typeInfo(inner)で型の種類を確認し、unionの場合のみ処理する
- union fieldを走査する
@max(field.alignment, @sizeOf(field.type))で必要な領域を計算する- サイズ情報をstack-allocated vectorに保存する
- union fieldからcluster indexへのmappingを構成する
- unionでなければcompile errorを発生させる
- 正確なコード片は該当ソースにある
- Rustのproc macroで同じ例を作るのは基本的に不可能である
- proc macroは型のsizeやalignment情報にアクセスできない
- 特定のenum向けcluster計算
const fnを生成することはできても、generic typeの配列長指定には使えない
- Rustのgeneric container実装は、与えられた型がenumかstructかに応じて条件付きで変わることが難しい
- Zigでは概念的に
T.isEnum()に応じてEfficientEnumArray<T>とEfficientStructArray<T>を選ぶ形が可能である
- AoVA実装もenumの特性に応じて選択できる
- たとえば、異なるvariantを一緒に配置する利点がベクタ数を90%超削減するときだけ意味があると判断する、といった特殊化が可能である
- 最大capacityをコンパイル時に把握できれば、型生成関数がtagged indexに必要なbitwidthを決定できる
- このtagged indexが別のデータ構造、たとえばさらに別のenum内に含まれると、余ったビットをdiscriminantに活用できる
- Zigは必要なビット数を具体的に指定できるため、コードの他の部分がその情報を自然に活用する合成可能なメモリ効率を提供する
- implicit widening integer coercionのおかげで、bitwidthの異なるAPIを扱うときも使い勝手が保たれる
- 効率性とzero-cost abstractionを重視するシステムプログラミング言語なら、staged programming、とくにZigの
comptimeを見直す必要がある
1件のコメント
Hacker News のコメント
保存効率がよく、要素の走査も維持できる別の戦略がある。1つ目のベクターはタグの一覧、2つ目のベクターは各要素のバイトオフセット、3つ目はベクターというより、2つ目のベクターが指す圧縮された variant データとして持つ方式だ。
こうすると、筆者の最終的な解法よりベクター数が半分で済み（6個 vs 3個）、アラインメントのために必要な場合を除けばパディングバイトを無駄にせず、型に関係なくデータがメモリ上に順番に配置されるので、キャッシュフレンドリーに走査できる。インデックスによる要素への O(1) アクセスも可能だ。全体として、異種データに対して
Vecに近い性能特性を持つ。Tに比べてかなりの領域を使うことがある。たとえば 64ビットのsize_tとuint8_t Tの組み合わせがそうで、オフセットサイズだけ気をつければ妥当なアプローチに見える。この AoVA データ構造が実際にはどう動くのか気になる。配列という観点ではインデックス演算がもはや意味を持たないかもしれないという点で、インデックスベースのアクセスを失うのではないか。走査も挿入順を保持しなさそうだ。
この文脈では、キャッシュ特性がよりよい TLV（tag-length-value） のほうが一般的に使われると思う。長さはタグから暗示できる場合もあるし、少なくとも意味のある前方走査を提供する。
getdents、inotify、Netlink メッセージングを見ればよい。以前の SoA レイアウトと比べると、全体順序ではなく部分順序が生じる。挿入時には、enum タグと該当する variant 配列内のインデックスの両方を含むタグ付きインデックスを返す構造だ。なので、順序付きアクセスはここでは範囲外と見ているようだ。各要素にグローバルインデックスを保存すれば順序付き走査は復活できるだろうが、順序付きランダムアクセスには依然として役に立たず、分岐もかなり多いコードになりそうだ。
サイズごとに物を保存する方式は、ガベージコレクタや汎用アロケータでも使われている。可能なオブジェクトサイズをすべて知っているという点で効率を得られることもあるし、arena のようにより単純な解放方式によって効率を得ることもできる。
この場合、配列群はヒープに似た構造の一構成要素、つまり arena のように見なせる。コストは、インデックスが
(tag_idx, va_for_tag_idx)のように2次元でなければならないことだ。ただしタグ数はコンパイル時に分かっているので、tag_idxを上位4〜5ビットに入れ、va_for_tag_idxが残りを使うようにパックして保存を最適化できる。参考: https://www.cs.cornell.edu/~asampson/blog/flattening.htmlRust のパターンマッチが、独自の保存構造を持つ明示的なファーストクラスのハードコードされたオブジェクト型ではなく、任意の構造体が従える型システム上の trait のような形としてもっと表現できないのは、少し残念だ。
最近この記事のように AST も実装したし、opcode/バイトコードインタプリタも実装したが、Rust の enum はどちらにも完全に理想的ではないと感じた。AST ではすべての statement ノードに行番号/列属性を付けたかったが、
Stmtenum のすべての場合に行/列を入れるとボイラープレートが汚くなり、enum を元の enum と行/列属性を一緒に持つ新しいStmt構造体で包むと、リファクタリングが多く優雅ではなかった。opcode 側でも、パターンマッチされる Rust enum が VM opcode インタプリタの性能上理想的なエンコーディングとは言いがたいが、言語はこの方向へ誘導し、分解パターン機能は非常に魅力的だ。望む低レベル実装を使いながらパターンマッチ機能も得られるようにする型システム改善の余地があるように思う。https://en.wikipedia.org/wiki/Structural_type_system
computed goto拡張があり、Rust なら関数ポインタと末尾呼び出し最適化を強制する何かが必要になりそうだ。各 opcode 実装の先頭にこうした間接ジャンプを置くと、CPU が OOP のために持っている間接ジャンプ予測器が、異なる opcode の末尾ごとに別々のモデルを持てるようになり、予測成功率が上がる可能性がある。次の命令そのものは予測しにくくても、たとえば test の後には branch が来る可能性がずっと高いかもしれない。ただし、スタックマシンでスタックトップをレジスタに保存するといった別の技法のほうが重要だと思うし、上の技法が今でも意味を持つのかはよく分からない。
「パース済みの clang AST が元のソースコードより定期的にメモリを 50 倍も食う」というのはかなり大きく見えるが、欠けている文脈は どれだけ改善できるのか という点。各トークンのソース位置を保持し、AST から正しく復元できるだけの情報をエンコードしなければならないなら、元ソース比で理想的な増加率が 1.5 倍なのか、15 倍なのかが気になる
ユーザーにもコンパイラ開発者にもやさしい言語で、理想的なソース→AST の膨張率がどれくらいかは言いにくいが、50 倍でも動きはする。原文では、50 倍の膨張率を特定の最適化を自動化しようとする動機として使っている。Rust の enum ベクタが enum 値を自動的にタグと不透明な値に分解し、Zig で原文がやっているように配列の構造体形式で保存できるなら面白そうだと思う。
unsafeの使用を隠す場所もあまり多くなさそう大部分が
[]文字、または0,文字で構成される文書では、最大オーバーヘッドは 8 倍程度に見えるソースバイト: 139 KiB、トークン: 24646 個（120 KiB）、AST ノード: 10998 個（140 KiB）。各トークンは 5 バイトでかなり最小化されており（1 バイトのタグ + 4 バイトのファイルオフセット）、AST ノードも密で不均一にエンコードされ、この場合ノードあたり約 13 バイト。こうした最小エンコードでも parse tree はソースファイルサイズのほぼ 2 倍になる。それでも 2 倍は 50 倍よりはるかにまし。出典:
zig ast-check -t lib/std/zig/Parse.zig | head -n7この問題空間は パッキング問題の変種のように感じる
最終結果である人間が扱いやすい構造から始めて、メモリの無駄を減らし、アラインメント規則を守り、空間的局所性を高めるデータ構造の推奨を生成できるとよさそう。https://en.wikipedia.org/wiki/Packing_problems
proc macro がコンパイラに情報を問い合わせられるように発展するとよい。そうするにはコンパイル段階の追加について慎重な設計が必要だろうが、「この構造体はこの trait を実装しているか」「具体的に実装されているすべての trait の一覧をくれ」といったことは proc macro で非常に有用な場合が多い
記事は一部しか理解していないが、Rust で スプレッドシートエンジンを書こうとしている立場からすると非常に関連がありそう。セル値にはこのような形が必要になる
pub enum Expr { Number(i32), String(String), Reference(Position), Binary(Box, char, Box), Function(String, Vec), }続けて読んで勉強するつもりで、参考になる資料があれば歓迎
ゲーム方面から来たよくある手法は、構造体の配列（AoS）を配列の構造体（SoA）に分割すること。たとえば
struct Humans { healths: Vec, ammo: Vec, … }のようにすると、各ベクタの i 番目のインデックスが AoS レイアウトの i 番目のHumanになる。こうした並列ベクタは例にすぎず最適効率ではない。フィールドごとに長さと容量の帳簿が重複して無駄になるため。この文章は基本的に enum に対して似たアイデアを自動的に適用しようとするもので、Rust ではそのままやるのは難しい。この問題が実際にどれほど大きいかは、やや誇張されている可能性もある。スプレッドシートでは、まず可能な最適化としてだけ念頭に置き、速度のために作るのか、それとも単純さと理解しやすさのために作るのかを先に判断すべき100 万 × 100 万セルを許可し、埋まっていないすべてのセルに
nullを保存するとメモリが尽きる。したがって、セル内容をスパースに保存する方法を検討できる。一つの方法はhashbrownのようなハッシュマップ実装を使うこと。この文章のポイントは低レベルの詳細なので、最初からハッシュマップで始めて初期のメモリ制約を避けるなら、当面は深く考えなくてもよい最も難しい単一の問題は 評価戦略
https://doc.rust-lang.org/reference/type-layout.html#the-alignment-modifiers はどうだろう
サンプルコードにバグがあるように思う
field_map[idx] = svec.len - 1;svecがすでに最後のエントリではない場所にsizeを含んでいる場合、誤りになるはず