HN 日本語サマリー

← 一覧へ戻る
プログラミング

ArenaAllocatorsはArrayListと相性が悪い

ArenaAllocators don't play nicely with ArrayLists (openmymind.net)

7 pointsby ibobev1 コメント

要約

ArenaAllocatorは、メモリを解放しても即座にアリーナに返却されるとは限らないため、ArrayListのような動的にサイズが変更されるデータ構造と組み合わせると、メモリ使用量が想定以上に増加する可能性があります。これは、ArrayListの拡張時に古いメモリが解放されるタイミングが、ArenaAllocatorの解放条件を満たさない場合に発生します。

全文翻訳

ArenaAllocators は ArrayList と相性が悪い

以前、ArenaAllocator について、そして「なぜその解放処理を noop (何もしないこと) として扱うべきか」について考察しました。

要点は、free または destroy が実際にアリーナにメモリを返却するためには、2つの条件を満たす必要があるということです。

  1. 解放されたメモリは、最後に確保されたメモリであること。
  2. 解放されたメモリは、アリーナの現在のノード (アリーナがどのように成長するかを示す内部的な詳細) 上で確保されたものであること。

したがって、このコードを考えると:

var a = try arena.alloc(u8, 100);
var b = try arena.alloc(u8, 100);
arena.free(b);
arena.free(a);

b のメモリはアリーナに返却されると確信できますが、a のメモリについてはどうなるか断言できません。なぜなら、b は最後に確保されたメモリであり、定義上アリーナの現在のノードから確保されたものでなければならないため、解放されるからです。b が解放された後、a は最初の条件を満たします。つまり、最後に確保されたメモリになります。しかし、b の確保が新しいノードを作成したかどうかはわかりません。アリーナの現在のノードは、a が確保されたノードである場合も、そうでない場合もあります。

ノードの件が混乱するように思えるなら、元の投稿を読むか、単に忘れてください。なぜなら、最初の単純なルールが満たされない一般的な状況があるからです。それは ArrayList (または Writer.Allocating) の成長です。データが ArrayList に追加されるとき、まず既存のメモリを再マッピングしようとします (つまり、インプレースで成長させます)。しかし、それが失敗した場合、より大きな新しいチャンクを確保し、以前のメモリをコピーして解放します。問題が見えますか? array_list.zig からのコードは以下の通りです。

const new_memory = try gpa.alignedAlloc(T, alignment, new_capacity);
@memcpy(new_memory[0..self.items.len], self.items);
gpa.free(old_memory);

ArrayList の成長と他の確保処理をインターリーブしていなくても、確保 + コピー + 解放という処理は、old_memory が最後に確保されたメモリではないことを保証します (最後に確保されたメモリは new_memory です)。

解決策はありますか? あまりありませんが、2つのことができます。第一に、ArrayList のサイズを適切に設定します (例: initCapacity または ensureTotalCapacityPrecise を使用)。第二に、他の確保処理と append/write 操作をインターリーブすることを避けます。もしそれができれば、remap ブランチにヒットする頻度が高くなり、この問題を回避できます。どちらも、どのような種類の Allocator を使用しているかに関わらず、念頭に置くべき良いことです。しかし、ArenaAllocator の場合、最悪のケースではメモリ使用量が約3倍になる可能性があります。

これは明白なことだとわかっていますが、私は実際に考えたことがありませんでした。おそらく私だけではないでしょう。