静的アロケーション、定数ワーク

静的確保、定数作業

2026年9月2日

このメールへの返信です。

メモリ安全性の最も難しい問題 は、私が遭遇したものの言葉にできなかったものを特定しました。あなたのケースは、異なるバリアントへの書き込みを生き延びたユニオンバリアントへのポインタであり、ライブな型付きポインタが、今は別のものに属するバイトを読み取ることになります。

昨年、リミットオーダーのマッチングエンジンを書いて、ユース・アフター・フリー（use-after-free）を発生させてしまいました。キャンセルされたオーダーは、まだ価格レベルにリンクされたままでプールに返却され、次の確保でそのメモリが新しいオーダーに割り当てられ、古いリンクが解決され続けました。私はこれを「ライフタイムの扱いに不注意だった」として分類していました。

あなたの投稿の後、それが本当にそうだったのか疑問に思っています。リサイクルプールは、タグが「このスロットに現在存在するオブジェクトの世代」であるタグ付きユニオンのように見えますが、型システムにはそれを追跡するものはありません。これは妥当な解釈でしょうか、それともプールケースは世代インデックスが実際にそれを解決するため、そしてユニオンケースには同等のものがないため、依然として本質的に簡単なのでしょうか？

はい、オブジェクトプールはメモリ安全性と、より一般的な正しさの関係を明確にする興味深いケースです。

まず、オブジェクトプールを使用せず、オーダーオブジェクトを malloc と free する場合を考えます。この場合、ユース・アフター・フリーという論理的なエラーは、物理的な型混乱に変わり、容易に任意のコード実行などに繋がります。異なる型の2つのオブジェクトが同じメモリ位置を共有している場合、一方のオブジェクト内のユーザー制御の整数が、もう一方では関数ポインタになる可能性があります。これは悪用可能な goto プリミティブです。

では、型 T の「デッド」オブジェクトのリストを格納するオブジェクトプールを導入するとどうなるでしょうか？論理的なユース・アフター・フリーは依然として可能ですが、その物理的な影響は異なります。メモリのエイリアシングは依然として発生しますが、型混乱はありません。インライン列挙型（inline enum）を格納する難しいケースに偶然当たらない限り、関数ポインタを変更するために整数をいじくり回すことはできません。それが起こらないと仮定すると、結果に満足できなくても、完全に定義された決定論的な動作が得られます。

これは、Fil から学んだ、コードを強化するための興味深い解決策を示唆しています。もしあなたの確保関数が型付き（ランタイムで型消去されたサイズとアラインメントではなく、T をコンパイル時パラメータまたはランタイム型証拠として受け取る）であれば、内部で型分離されたプールを使用するアロケータを書くことができます。これは、アロケータが型 U の解放されたメモリを型 T のオブジェクトのために再利用できないため、メモリ効率はやや低下しますが、メモリオーバーヘッドは小さいでしょう（まれなオブジェクト型は問題にならず、一般的なオブジェクト型は型内再利用が多くなる）、メモリ局所性が向上する可能性があり、そして型混乱のほとんどを解決できます。ここでも、インライン列挙型はこれを壊しますが、興味深いことに、列挙型のバリアントを常にヒープ確保する場合、これは再び機能します。Cのアロケータインターフェースは型付けされていないため、Fil-Cはこの方法を使用できませんが、他の誰かはできるでしょう :P

しかし、これは学術的な話です。バグをどのように回避するのでしょうか？世代インデックスは一般的な解決策ですが、私はそれらを使ったことがないので、このパターンに関する一般的な知識以外の洞察はありません。代わりに、TigerStyle からの別のトリックのペアを共有します。オーダーマッチングエンジンが何であるかについては漠然とした理解しかありませんが、これらのトリックがそこで役立つ可能性があると推測しています。

静的確保

最初のトリックはこれです。

初期化後の動的なメモリ確保は行わない

https://www.youtube.com/watch?v=GRJtYwneG2Q&t=1823s

これはプールという考え方を論理的な結論まで推し進めたものです。起動時に処理したいオーダーの最大数を指定し、それ以上は増やしません。したがって、プログラムは次のように開始されるかもしれません。

$ order-engine --orders-max=1_000_000

そして、その main 関数の最初の数行の1つが次のようになります。

const orders: []Order = try gpa.alloc(Order, cli_args.orders_max);

実行時に、orders_max 以上のリクエストが来た場合、超過したリクエストは拒否されます。誰かが異議を唱えるかもしれません。「でも、もう1つオーダーを処理できるだけの空きメモリがある場合はどうすればいいのですか？少なくともそれを処理しようとするのは良い考えではないでしょうか？」

私の反論は「では、もしそうでない場合は？」です。容量で動作するシステムは、厳格な制限なしでは壊滅的に失敗します。もう1つ Order を確保しようとすると、カーネルのOOM killerがオーダーマッチングエンジン全体を終了させ、他の100万件のオーダーを失うか、最悪の場合、スーパーバイザープロセスを終了させて再起動すらできなくなる可能性があります。

静的確保は心の平穏を与えてくれます。メモリが不足しているとシステムが起動に失敗するかもしれませんが、起動できたなら、過負荷に優雅に対処し、より強力なマシンをプロビジョニングしている間もサービスを提供し続けることができると確信できます。

定数作業

オーダーのスライスをどう使いますか？1つのアプローチは、@memset(orders, undefined) して、ビットセットで空きオブジェクトを追跡するプールにスライスを渡すことです。

const OrderPool = struct {
    orders: []Order,
    free: DynamicBitSet,

    fn acquire(pool: *OrderPool) ?*Order { ... }
    fn release(pool: *OrderPool, order: *Order) { ... }
};

またはフリーリストで。

const OrderPool = struct {
    orders: []union {
        order: Order,
        next_free: ?u32,
    },
    first_free: ?u32,
};

しかし、別の代替アプローチがあります。オーダー数の上限を考える代わりに、ノープ（no-op）、中立的なオーダーを導入することで、常に固定量のオーダーを持つようにシステムを設計できます。

const Order = {
    id: u128,
    price: u32,
    count: u32,

    tag: enum { bid, ask, reserved },

    pub const reserved: Order = .{ 
        .id = 0,
        .price = 0,
        .count = 0,
        .tag = .reserved,
    };
};

初期化は @memset(orders, .reserved) となります。

この利点の1つは認知的です。オーダーの作成と破棄という観点ではもはや考えません。代わりに、オーダーはオーダーの数の保存の法則に従ってシステム内を循環するだけです。オーダーがどこへ行ったかだけでなく、どこから来たのかにも常に注意を払わなければならない場合、オーダーを見失うことはより困難になります。各ペアの状態遷移関数を明示的に書き、それによってすべてのケースを網羅的に列挙することが容易になります。そして、すべての時点で状態が期待通りであることをアサートし（その後、アサートをDST化します）、それで二重に確認します。

もう1つの利点は、コードの単純化と予測可能性です。「ライブ」オーダーの別のコレクションを追跡する必要はなくなります。代わりに、常にフルセットを反復処理し、予約済みのものについてはノープを実行します。これは無駄に思えるかもしれません。オーダーが少ないときにコードを速く実行すべきでしょうか？しかし、考えてみてください。オーダーの最大数を事前に指定することで、その量を提供できることを約束します。最大量のオーダーがアクティブな場合、システムは許容できるパフォーマンスを持っていますか？もしそうでないなら、それはバグです！グレー障害（システムが使用不能なほど遅くなること）も、制限に達したときに失敗する別の方法です。

インデックスを回避することは、最大負荷ケースのパフォーマンスを向上させます。これは

for (orders) |order| {
    process(order)
}

は、コンパイラがベクトル化しやすく、CPUキャッシュがプリフェッチしやすいですが、これは異なります。

for (orders_active) |order_index| {
    const order = orders[order_index];
    process(order);
}

静的確保と同様に、「定数作業」の原則はパフォーマンスに関して心の平穏を与えてくれます。P100レイテンシは、負荷に関係なく一定です。不十分なパフォーマンスは、システムをロールアウトするときに発見されるのであり、ブラックフライデーのオンコール中に発見されるのではありません。

TigerBeetleでは、このパターンを小規模に適用しています。早期リターンで検索ループを書く代わりに。

const item = for (items) |item| {
    if (predicate(item)) break item;
} else null;

私たちは時々、ループをその自然な全コースで実行させ、さらに一意の一致するアイテムがあることをアサートします。

https://github.com/tigerbeetle/tigerbeetle/blob/0.17.9/src/vsr/grid.zig#L715-L725

---

いつものように、これはあなたの武器庫に役立つ1つのトリックですが、プログラミングのすべての問題に対する普遍的な解決策ではありません。