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

メモリ安全性の最も難しい問題というメールへの返信です。それは私が遭遇したものの、言葉にできなかったものです。あなたのケースは、あるユニオンバリアントのポインタが、別のバリアントの書き込みを生き延びるというものです。そのため、ライブな型付きポインタは、現在別のものに属するバイトを読み込むことになります。昨年、私はリミットオーダーのマッチングエンジンを書き、ユース・アフター・フリー（use-after-free）を発生させました。キャンセルされたオーダーは、その価格レベルにまだリンクされている間にプールに返却されました。そのため、次のアロケーションはそのメモリを新しいオーダーに割り当て、古いリンクは解決され続けました。私はそれを「ライフタイムの扱いに不注意だった」として分類していました。あなたの投稿の後、それが本当にそうだったのか疑問に思っています。リサイクリングプールは、タグが「どの世代のオブジェクトが現在このスロットに存在するのか」であるタグ付きユニオンのように見えますが、型システムにはそれを追跡するものはありません。これは妥当な解釈でしょうか、それともプールケースは世代インデックスが実際にそれを解決するため、ユニオンケースには同等のものがないため、本当に簡単なのでしょうか？ はい、オブジェクトプールは考える上で興味深いケースであり、メモリ安全性とより一般的な正しさとの関係を明確にします。まず、オブジェクトプールを使用せず、オーダーオブジェクトをmallocおよびfreeする場合を考えます。この場合、ユース・アフター・フリーという論理的なエラーは、物理的な型の混乱に変わり、容易に任意のコード実行などを引き起こす可能性があります。異なる型の2つのオブジェクトが同じメモリ位置を共有している場合、一方のオブジェクト内のユーザー制御の整数が、もう一方では関数ポインタになる可能性があります。これは悪用可能なgotoプリミティブです。 では、T型の「デッド」オブジェクトのリストを格納するオブジェクトプールを導入するとどうなるでしょうか？論理的なユース・アフター・フリーは依然として可能ですが、その物理的な影響は異なります。メモリのエイリアシングは依然として発生しますが、型の混乱はありません。インライン列挙型（inline enum）をヒットしない限り、必ずしも整数を操作して関数ポインタを変更できるわけではありません。それが起こらないと仮定すると、結果に満足できなくても、完全に定義された決定論的な動作が得られます。 これは、Filから学んだ、コードを強化するための興味深い解決策を示唆しています。アロケーション関数が型付けされている場合（実行時型消去されたサイズとアラインメントではなく、comptimeパラメータまたは実行時型証拠を受け取る）、型分離プールを内部的に使用するアロケータを記述できます。これは、アロケータがU型のオブジェクトの解放されたメモリをT型のオブジェクトに再利用できないため、メモリ効率はやや低下しますが、メモリオーバーヘッドは小さいでしょう（まれなオブジェクト型は問題にならず、一般的なオブジェクト型は型内再利用が多くなります）。メモリ局所性で実際に利益を得て、型の混乱のほとんどを解決できるかもしれません。ここでも、インライン列挙型はこれを壊しますが、興味深いことに、列挙型バリアントを常にヒープアロケートする場合、これは再び機能します。Cのアロケータインターフェースは型付けされていないため、Fil-Cはこの方法を使用できませんが、他の誰かはできるかもしれません。 しかし、これは学術的な話です。バグをどのように回避するか？世代インデックスは一般的な解決策ですが、私はそれらを使用したことがないので、このパターンに関する一般的な知識以外の洞察はありません。代わりに、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つのオーダーを割り当てようとすると、カーネルの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つの利点は、コードの簡略化と予測可能性です。「ライブ」オーダーの別のコレクションを追跡する必要はなくなります。代わりに、常にフルセットを反復処理し、予約済みのものについてはノーオペレーションを実行します。これは無駄に思えるかもしれません。オーダーが少ないときにコードを速く実行すべきでしょうか？しかし、考えてみてください。オーダーの最大数を事前に指定することで、その量を提供できることを約束します。オーダーの最大数がアクティブな場合、システムは許容できるパフォーマンスを持っていますか？もしそうなら、それはバグです！グレー障害（システムが使用不能な遅くなること）も、制限に達したときに壊れるもう1つの方法です。インデックスを回避することは、最大負荷ケースのパフォーマンスを向上させます。 この for (orders) |order| { process(order) } は、この for (orders_active) |order_index| { const order = orders[order_index]; process(order); } よりも、コンパイラがベクトル化しやすく、CPUキャッシュがプリフェッチしやすいため、はるかに簡単です。 静的アロケーションと同様に、定数ワークの原則はパフォーマンスに関する安心感を与えます。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 いつものように、これはあなたの武器庫に持っておくと便利なトリックですが、プログラミングのすべての問題に対する普遍的な解決策ではありません。