Chapter 2: Arenaアロケータの設計と実装
2.1 Arenaアロケータとは
概念の理解
Arenaアロケータは、メモリを「アリーナ」と呼ばれる領域にグループ化し、一括で解放できるようにするパターンです。
従来のアロケータ:
alloc(A) ──→ free(A)
alloc(B) ──→ free(B)
alloc(C) ──→ free(C)
↑ 個別管理が必要
Arenaアロケータ:
alloc(A)
alloc(B) ──→ arena.deinit() ← 一括解放
alloc(C)
↑ 個別のfreeは不要
Bump Allocatorとの違い
const std = @import("std");
// Bump Allocator: 固定バッファ
var buffer: [4096]u8 = undefined;
var bump = std.heap.FixedBufferAllocator.init(&buffer);
// バッファが足りなくなったら終わり
// Arena Allocator: 動的に拡張
var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
defer arena.deinit(); // 全て一括解放
// メモリが足りなくなったら自動で追加バッファを確保
主な違い:
特性 Bump Allocator Arena Allocator
----------------------------------------------------------------
バッファ 固定サイズ 動的拡張
親アロケータ 不要 必要
メモリ不足時 エラー 新しいバッファを確保
解放 reset()のみ deinit()で全解放
用途 一時バッファ 長時間稼働するスコープ
2.2 Arenaアロケータの内部構造
メモリレイアウト
ArenaAllocator:
parent_allocator: Allocator
state: State
State:
buffer_list: [][]u8
end_index: usize
メモリの内部構造:
+-------------------+
| Buffer 1 | ← 最初に確保
| [4KB] |
+-------------------+
|
v (足りなくなったら)
+-------------------+
| Buffer 2 | ← 次のバッファを確保
| [8KB] |
+-------------------+
|
v
+-------------------+
| Buffer 3 | ← さらに確保
| [16KB] | (指数的に増加)
+-------------------+
実装の詳細
const std = @import("std");
pub const SimpleArena = struct {
const FIRST_BUFFER_SIZE = 4096;
const GROWTH_FACTOR = 2;
parent_allocator: std.mem.Allocator,
buffers: std.ArrayList([]u8),
current_index: usize,
pub fn init(parent: std.mem.Allocator) SimpleArena {
return .{
.parent_allocator = parent,
.buffers = std.ArrayList([]u8).init(parent),
.current_index = 0,
};
}
pub fn deinit(self: *SimpleArena) void {
// 全てのバッファを一括解放
for (self.buffers.items) |buffer| {
self.parent_allocator.free(buffer);
}
self.buffers.deinit();
}
pub fn allocator(self: *SimpleArena) std.mem.Allocator {
return .{
.ptr = self,
.vtable = &.{
.alloc = alloc,
.resize = resize,
.free = free,
},
};
}
fn alloc(
ctx: *anyopaque,
len: usize,
ptr_align: u8,
ret_addr: usize,
) ?[*]u8 {
_ = ret_addr;
const self = @as(*SimpleArena, @ptrCast(@alignCast(ctx)));
// 現在のバッファで割り当て可能かチェック
if (self.buffers.items.len > 0) {
const current = self.buffers.items[self.buffers.items.len - 1];
const alignment = @as(usize, 1) << @as(u6, @intCast(ptr_align));
const aligned_index = std.mem.alignForward(
usize,
self.current_index,
alignment,
);
if (aligned_index + len <= current.len) {
const result = current.ptr + aligned_index;
self.current_index = aligned_index + len;
return result;
}
}
// 新しいバッファが必要
const new_size = if (self.buffers.items.len == 0)
FIRST_BUFFER_SIZE
else
self.buffers.items[self.buffers.items.len - 1].len * GROWTH_FACTOR;
// 要求サイズが大きい場合は調整
const actual_size = @max(new_size, len + 64);
const new_buffer = self.parent_allocator.alloc(u8, actual_size) catch
return null;
self.buffers.append(new_buffer) catch {
self.parent_allocator.free(new_buffer);
return null;
};
self.current_index = len;
return new_buffer.ptr;
}
fn resize(
ctx: *anyopaque,
buf: []u8,
buf_align: u8,
new_len: usize,
ret_addr: usize,
) bool {
_ = ctx;
_ = buf;
_ = buf_align;
_ = new_len;
_ = ret_addr;
return false;
}
fn free(
ctx: *anyopaque,
buf: []u8,
buf_align: u8,
ret_addr: usize,
) void {
_ = ctx;
_ = buf;
_ = buf_align;
_ = ret_addr;
// 個別の解放は何もしない
}
};
2.3 使用例とパターン
パターン1: リクエストスコープ
Webサーバーでのリクエスト処理に最適:
const std = @import("std");
const Request = struct {
path: []const u8,
headers: std.StringHashMap([]const u8),
body: []const u8,
};
fn handleRequest(
base_allocator: std.mem.Allocator,
raw_data: []const u8,
) !void {
// リクエスト専用のArenaを作成
var arena = std.heap.ArenaAllocator.init(base_allocator);
defer arena.deinit(); // リクエスト終了時に全解放
const allocator = arena.allocator();
// パース処理でメモリを自由に使える
const path = try allocator.dupe(u8, "/api/users");
var headers = std.StringHashMap([]const u8).init(allocator);
try headers.put(
try allocator.dupe(u8, "Content-Type"),
try allocator.dupe(u8, "application/json"),
);
const body = try allocator.alloc(u8, raw_data.len);
@memcpy(body, raw_data);
// 処理...
std.debug.print("Processing: {s}\n", .{path});
// deferで自動的に全てのメモリが解放される
}
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
// 複数のリクエストを処理
for (0..100) |i| {
const data = "Request data";
try handleRequest(gpa.allocator(), data);
std.debug.print("Request {} completed\n", .{i});
}
}
パターン2: パーサーとAST構築
const std = @import("std");
const ASTNode = struct {
kind: enum { number, binary_op, identifier },
value: union {
number: i64,
binary: struct {
op: u8,
left: *ASTNode,
right: *ASTNode,
},
identifier: []const u8,
},
};
fn parseExpression(
allocator: std.mem.Allocator,
source: []const u8,
) !*ASTNode {
// ArenaアロケータでASTノードを構築
// 各ノードのfreeを気にする必要がない
const node = try allocator.create(ASTNode);
if (std.mem.eql(u8, source, "42")) {
node.* = .{
.kind = .number,
.value = .{ .number = 42 },
};
} else {
// 複雑な式のパース...
const left = try allocator.create(ASTNode);
const right = try allocator.create(ASTNode);
left.* = .{
.kind = .number,
.value = .{ .number = 10 },
};
right.* = .{
.kind = .number,
.value = .{ .number = 32 },
};
node.* = .{
.kind = .binary_op,
.value = .{
.binary = .{
.op = '+',
.left = left,
.right = right,
},
},
};
}
return node;
}
pub fn parseProgram(source: []const u8) !void {
var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
defer arena.deinit(); // AST全体を一括解放
const ast = try parseExpression(arena.allocator(), source);
// ASTを使った処理...
switch (ast.kind) {
.number => std.debug.print("Number: {}\n", .{ast.value.number}),
.binary_op => std.debug.print("Binary op: {c}\n", .{ast.value.binary.op}),
else => {},
}
// 明示的なfreeは不要 - deferで全解放
}
パターン3: ゲームフレームメモリ
const std = @import("std");
const GameState = struct {
frame_arena: std.heap.ArenaAllocator,
permanent_allocator: std.mem.Allocator,
entities: std.ArrayList(*Entity),
temp_data: std.ArrayList([]u8),
pub fn init(base_allocator: std.mem.Allocator) !GameState {
return .{
.frame_arena = std.heap.ArenaAllocator.init(base_allocator),
.permanent_allocator = base_allocator,
.entities = std.ArrayList(*Entity).init(base_allocator),
.temp_data = std.ArrayList([]u8).init(base_allocator),
};
}
pub fn deinit(self: *GameState) void {
self.entities.deinit();
self.temp_data.deinit();
self.frame_arena.deinit();
}
pub fn newFrame(self: *GameState) void {
// 前フレームのメモリを全解放
_ = self.frame_arena.reset(.retain_capacity);
}
pub fn frameAllocator(self: *GameState) std.mem.Allocator {
return self.frame_arena.allocator();
}
};
const Entity = struct {
x: f32,
y: f32,
velocity: struct { x: f32, y: f32 },
};
pub fn gameLoop() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
var game = try GameState.init(gpa.allocator());
defer game.deinit();
// ゲームループ
for (0..60) |frame| {
game.newFrame(); // 前フレームのメモリをクリア
const frame_alloc = game.frameAllocator();
// フレーム内の一時データ
const render_list = try frame_alloc.alloc(*Entity, 100);
const particle_buffer = try frame_alloc.alloc(u8, 4096);
// 処理...
_ = render_list;
_ = particle_buffer;
std.debug.print("Frame {}: completed\n", .{frame});
// newFrame()で自動的にメモリがリセットされる
}
}
2.4 パフォーマンス特性
ベンチマーク比較
const std = @import("std");
fn benchmarkGeneralPurpose() !u64 {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
var timer = try std.time.Timer.start();
for (0..10000) |_| {
const buf = try allocator.alloc(u8, 100);
allocator.free(buf);
}
return timer.read();
}
fn benchmarkArena() !u64 {
var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
defer arena.deinit();
const allocator = arena.allocator();
var timer = try std.time.Timer.start();
for (0..10000) |_| {
const buf = try allocator.alloc(u8, 100);
_ = buf;
// freeなし
}
return timer.read();
}
pub fn main() !void {
const gpa_time = try benchmarkGeneralPurpose();
const arena_time = try benchmarkArena();
std.debug.print("GeneralPurpose: {} ns\n", .{gpa_time});
std.debug.print("Arena: {} ns\n", .{arena_time});
std.debug.print("Speedup: {d:.2}x\n", .{
@as(f64, @floatFromInt(gpa_time)) / @as(f64, @floatFromInt(arena_time)),
});
}
典型的な結果:
GeneralPurpose: 2,500,000 ns
Arena: 800,000 ns
Speedup: 3.12x
メモリ使用量の分析
シナリオ: 10,000個の小さい割り当て(100バイト)
GeneralPurposeAllocator:
- 各割り当てにメタデータ(~32バイト)
- フラグメンテーション
- 合計: ~1.3MB
ArenaAllocator:
- 連続したバッファ
- メタデータ最小
- 合計: ~1.0MB
利点:
✓ 23%のメモリ削減
✓ キャッシュ効率向上
✓ 割り当て速度3倍
2.5 使用上の注意点
アンチパターン1: 長時間稼働するArena
// 悪い例: 無限に成長する
pub fn badExample() !void {
var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
defer arena.deinit();
while (true) {
// 終わらないループでArenaを使用
const data = try arena.allocator().alloc(u8, 1024);
_ = data;
// メモリが解放されず、無限に成長する
}
}
// 良い例: 定期的にリセット
pub fn goodExample() !void {
var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
defer arena.deinit();
for (0..1000) |i| {
const data = try arena.allocator().alloc(u8, 1024);
_ = data;
if (i % 100 == 0) {
_ = arena.reset(.retain_capacity); // 定期的にリセット
}
}
}
アンチパターン2: Arenaからのポインタ保持
// 危険: Arenaのスコープ外でポインタを使用
fn dangerousPattern() ![]const u8 {
var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
defer arena.deinit(); // ここで解放される
const data = try arena.allocator().dupe(u8, "Hello");
return data; // dangling pointer!
}
// 安全: 適切なアロケータを使用
fn safePattern(allocator: std.mem.Allocator) ![]const u8 {
return try allocator.dupe(u8, "Hello");
}
2.6 実世界の使用例
Zigコンパイラ
Zigコンパイラ自身がArenaアロケータを多用しています:
コンパイルフェーズごとにArena:
1. Lexing/Parsing Phase
→ ASTをArenaに構築
→ パース完了後、AST全体を保持
2. Semantic Analysis Phase
→ 型情報をArenaに構築
→ 各関数の解析でローカルArena
3. Code Generation Phase
→ IR(中間表現)をArenaに構築
→ 最適化パスごとにリセット
ゲームエンジン(例: Unreal Engine相当)
メモリ階層:
Permanent Arena: ゲーム全体で保持
Level Arena: レベルロード時に確保、アンロード時に解放
Frame Arena: 毎フレームリセット
Temp Arena: 関数スコープの一時データ
2.7 まとめ
Arenaアロケータは以下の特性を持ちます:
利点:
✓ 個別のfreeが不要
✓ 高速な割り当て
✓ キャッシュ効率が良い
✓ コードがシンプルになる
✓ メモリリークしにくい
欠点:
✗ 個別の解放ができない
✗ 長時間稼働で肥大化
✗ メモリ効率が悪い場合がある
適用例:
✓ リクエストスコープ(Webサーバー)
✓ パーサー・コンパイラ
✓ ゲームのフレームメモリ
✓ 一時的なデータ処理
次の章では、Poolアロケータについて学びます。固定サイズのオブジェクトを効率的に管理する方法を見ていきます。
参考資料
- Zig Standard Library - ArenaAllocator: https://ziglang.org/documentation/master/std/#A;std:heap.ArenaAllocator
- Memory Management Patterns: https://www.gingerbill.org/article/2019/02/08/memory-allocation-strategies-002/
- Game Programming Patterns - Object Pool: https://gameprogrammingpatterns.com/object-pool.html