blog.dopana

戻る

多くのプログラミング言語において、「配列」といえば固定長配列(C言語の int a[10] やRustの [T; N])か、ヒープ上に確保される可変長ベクタ(C++の std::vector やRustの Vec<T>)の二者択一でした。

しかし、FlatBuffersの作者でもあるGooseの設計者 Wouter van Oortmerssen 氏は、この二分法が現代のCPUハードウェアに対して深刻な非効率をもたらしていると見抜きました。

  • 従来の動的ベクタは、コールスタック上に常に (ポインタ, 長さ, キャパシティ) の3要素を保持します。
  • 実データはヒープ上の離れたアドレスに置かれ、CPUは常にポインタをたどる(ポインタチェイシング)必要があります。
  • ネストされた構造体(文字列や可変長の子リスト)を持つと、ポインタの間接参照が何層にも重なり、CPUキャッシュライン(通常64バイト)の連続性がズタズタに分断されてしまいます。

Gooseはこの根本的なハードウェアの不一致を解消するため、独自の 配列ファミリー(The Array Family) と 可変長Enum(Variable-Sized Enums) を導入しました。

1. Gooseの配列ファミリー分類学(The Array Taxonomy)#

Gooseはすべての動的配列を1つの Vec<T> に詰め込むのではなく、「配列のサイズがどのように変化するか」 に応じて5つの型に細分化しています。

汎用非所有スライスGooseにおける配列ファミリー分類Slice WindowSlice WindowSlice WindowSlice WindowSlice WindowT[k]: コンパイル時固定長T[] / T[varint]: 生成時決定・以後完全凍結T[..k]: インライン容量限定(Small-Vector)T[>..]: 伸長専用 (Grow-Only) 参照が常に生存T[>..<]: 伸縮自在 (Grow-Shrink)スタック/キュー用T[:]: 万能スライスビューPointer + Length ペア (ゼロ割り当て)
型シグネチャメモリ配置と動作セマンティクス最適なユースケース
T[k]コンパイル時に既知の固定サイズ kk。メタデータ消費ゼロで完全にインライン化。3Dベクトル f32[3]、4x4変換行列 f32[16]、SHA-256ハッシュ u8[32]。
T[] / T[varint]生成時に長さが決定され、以後完全に不変(凍結)。完成した固定文字列、ファイルから読み込んだ静的レコード。
T[..k]最大容量 kk が構造体内に直接インライン化され、その範囲内で伸縮。短い識別子(16バイト以下の文字列)、小規模タグ配列。
T[>..]伸長専用(Grow-Only)。追加のみ許可され、途中の削除は不可。主データテーブル、注文台帳、木ノード。内部への参照は絶対に無効化されない。
T[>..<]伸縮自在(Grow-Shrink)。末尾でのpush/popをサポート。スタック、キュー、リングバッファ、グラフ探索リスト。
T[:]スライスビュー。借用された { pointer, length } ペア。コピーを発生させずに汎用処理を行う関数引数。

2. 超高密度文字列:T[varint]#

C++の std::string はポインタと管理情報でスタック上に24〜32バイトを消費します。Rustの String も24バイトを消費します。

Gooseでは、文字列は単なる u8 の配列として表現されます。これを varint と組み合わせると驚異的なコンパクトさを発揮します。

  • 長さヘッダーが可変長整数(varint)として符号化されます。
  • 128文字未満の短い文字列(商品コード、ユーザー名、メールアドレスなど実用文字列の9割以上)では、長さメタデータはわずか1バイトしか消費しません!
strings.goose
// 長さヘッダー1バイト + 文字列5バイト = メモリ上でわずか6バイト!
let sku: u8[varint] = "SKU-7";

// データスタック上の文字列ビルダー
var builder: u8[>..] = [];
builder.push_str("Hello ");
builder.push_str("Goose!");

// ビルダーを参照する非所有スライス
let view: u8[:] = builder[..];
rust

ヒープへのポインタ参照も外部割り当てのオーバーヘッドもありません。文字列は親構造体のメモリ上にそのまま直接鋳造されます。

3. 代数データ型の革命:可変長Enum(Shape..)#

Rustの enum やC++の std::variant などの代数データ型(ADT)では、列挙型のメモリサイズは常に最大サイズのバリアントに合わせてパディングされます。

従来のEnumの無駄:#

典型的な図形型を例に挙げます。

shapes.rs
enum Shape {
    Circle { r: f64 },       // 1 tag + 8 bytes = 9 bytes (16へパディング)
    Rect { w: f64, h: f64 }, // 1 tag + 16 bytes = 17 bytes (24へパディング)
    Dot,                     // 1 tag = 1 byte
}
rust

RustやC++で100万個の図形配列を作成すると、Dot や Circle であっても最大の Rect に合わせて24バイトに引き伸ばされます。結果として、配列全体のメモリの半分以上が無駄なパディングで埋め尽くされてしまいます。

Gooseのブレークスルー:Shape..(Variable Mode)#

Goose Variable-Mode Enum: Shape.. (実データ分のみ格納)Rust / C++ Enum: 最大バリアントに合わせて均一化 (17〜24バイト)Circle: Tag (1B) + Radius (8B) +Padding (8B) = 17 BytesRect: Tag (1B) + Width (8B) +Height (8B) = 17 BytesDot: Tag (1B) + Padding (16B)= 17 Bytes3要素の合計: 51バイト (半分近くが空きパディングで無駄)Circle: Tag (1B) + Radius (8B) =9 BytesRect: Tag (1B) + Width (8B) +Height (8B) = 17 BytesDot: Tag (1B) = 1 Byte3要素の合計: 27バイト (メモリ消費量を半減!)

Gooseでは、利用目的に応じて格納モードを選択できます。

  1. Fixed Mode (Shape): 従来どおり均一サイズで保持し、O(1)O(1) のランダムアクセス(shapes[i])を可能にします。
  2. Variable Mode (Shape..): 各要素がそのバリアントの実サイズ分だけをメモリ上に隙間なく消費します。
    • Dot: わずか 1バイト
    • Circle: わずか 9バイト
    • Rect: わずか 17バイト

[!NOTE] 公式ベンチマークにおいて、Shape.. を用いた配列はRustの Vec<Shape> と比較して メモリ消費量が4分の1に減少し、実行速度は2倍に高速化 しています。

4. Vtable不要の高速ディスパッチ:Case Functions#

Gooseは冗長な match や switch ブロックの代わりに、バリアントごとに多重定義できる Case Functions を備えています。

case_functions.goose
// バリアントごとの個別オーバーロードを定義
fn area(s: Shape.Circle) -> f64 { 3.14159 * s.r * s.r }
fn area(s: Shape.Rect) -> f64   { s.w * s.h }
fn area(s: Shape.Dot) -> f64    { 0.0 }

// コンパイラが網羅性を検証し、高速なジャンプテーブルに変換!
for s in packed {
    print("面積: ", area(s));
}
rust

仮想関数テーブル(vtable)の参照コストも、オブジェクト指向の継承オーバーヘッドもありません。タグ番号に基づいたアセンブリ直結の高速ジャンプテーブルとして実行されます。

5. なぜCPUキャッシュ(L1/L2)はフラットメモリを愛するのか?#

現代のCPUは キャッシュラインプリフェッチャ(Cache Line Prefetcher) を内蔵しています。メモリから1バイト読み出すだけで、隣接する64バイトのブロック全体が超高速なL1キャッシュ(レイテンシ約1ns)へ引き込まれます。

CPUキャッシュライン (64バイト)
┌──────────────────────────────────────────────────────────────┐
│ [Item 1 (29B)] │ [Item 2 (29B)] │ [Item 3先頭...]            │
└──────────────────────────────────────────────────────────────┘
わずか1回のキャッシュライン読み込みでGooseの2レコードが丸ごと乗る!
text
  • C++ / Rust: ネストされたレコードはバラバラに散らばっています。ルート構造体、文字列、子ベクタが別々のヒープ領域にあるため、1つのデータを解釈するのに 3〜4回のキャッシュミス が発生し、CPUがストールします。
  • Goose: フラットな配列と可変長Enumにより、1本のキャッシュラインに 2つ以上の完全な親子レコード が丸ごと収まります。CPUはハードウェアのバス帯域をフル稼働させて、最高速でメモリを走査できます。

6. 各言語における配列機能の比較表#

比較機能C++ (std::vector)Rust (Vec<T>)Go ([]T)Goose (Array Family)
配列型の体系化単一のvector型単一のVec型ヒープ参照スライスサイズ特性に応じた5つの専門型
インライン小容量最適化外部ライブラリ必須smallvec クレート必須非対応言語標準組み込み (T[..k])
完全不変な凍結配列const修飾のみ非対応非対応言語標準組み込み (T[], T[varint])
要素追加時の参照維持❌ 再配置で無効化❌ 借用規則で禁止❌ 再配置される✅ 常に保証 (T[>..])
可変長Enum❌ 最大サイズにパディング❌ 最大サイズにパディングADT自体が非対応✅ 標準サポート (Shape..)
Enum要素のその場編集冗長困難非該当✅ &r で自然にインプレース変更

7. まとめ#

Gooseの配列ファミリーと可変長Enumは、「現代のハードウェア特性に合わせて言語を設計する」 という真のエンジニアリング精神を体現しています。

無駄なパディングを徹底的に削ぎ落とし、データをフラットに整列させることで、Gooseは以下の成果をもたらします。

  1. 高水準言語のような安全で明快なコーディング体験
  2. メモリ消費量の2倍〜4倍の削減
  3. CPUキャッシュの性能を限界まで引き出した圧倒的なスループット

参考文献#