ArenaAllocatorsはArrayListと相性が悪い
ArenaAllocators don't play nicely with ArrayLists (openmymind.net)
要約
ArenaAllocatorは、メモリを解放しても即座にアリーナに返却されるとは限らないため、ArrayListのような動的にサイズが変更されるデータ構造と組み合わせると、メモリ使用量が想定以上に増加する可能性があります。これは、ArrayListの拡張時に古いメモリが解放されるタイミングが、ArenaAllocatorの解放条件を満たさない場合に発生します。
全文翻訳
ArenaAllocators は ArrayList と相性が悪い
以前、ArenaAllocator について、そして「なぜその解放処理を noop (何もしないこと) として扱うべきか」について考察しました。
要点は、free または destroy が実際にアリーナにメモリを返却するためには、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倍になる可能性があります。
これは明白なことだとわかっていますが、私は実際に考えたことがありませんでした。おそらく私だけではないでしょう。