Explanation 04: General Purpose Allocator - 深層解説
概要
このセクションでは、Zigの General Purpose Allocator（GPA）の内部実装を詳細に解説します。GPAがどのようにメモリを管理し、高速で安全な割り当て/解放を実現しているかを理解することで、より効果的にメモリ管理を行えるようになります。
サイズクラスバケットシステム
サイズクラスの設計思想
GPAの核心は、メモリ要求を予め決められたサイズクラスに分類することです。これにより、フラグメンテーションを最小化し、割り当て速度を向上させます。
// Zigの標準ライブラリにおけるサイズクラスの概念
const size_classes = [_]usize{
8, // Size Class 0
16, // Size Class 1
32, // Size Class 2
64, // Size Class 3
128, // Size Class 4
256, // Size Class 5
512, // Size Class 6
1024, // Size Class 7
2048, // Size Class 8
4096, // Size Class 9
};
fn getSizeClass(size: usize) usize {
// 要求サイズに最適なサイズクラスを決定
for (size_classes, 0..) |class_size, i| {
if (size <= class_size) return i;
}
return size_classes.len; // 大規模割り当て
}
サイズクラスの選択アルゴリズム
const std = @import("std");
// サイズクラスを決定する実際のロジック
pub fn demonstrateSizeClassSelection() void {
const allocations = [_]usize{ 1, 15, 33, 100, 500, 5000 };
for (allocations) |size| {
const aligned_size = std.mem.alignForward(usize, size, 8);
std.debug.print("要求: {}B -> アライメント済み: {}B -> ", .{ size, aligned_size });
if (aligned_size <= 8) {
std.debug.print("サイズクラス 0 (8B)\n", .{});
} else if (aligned_size <= 16) {
std.debug.print("サイズクラス 1 (16B)\n", .{});
} else if (aligned_size <= 32) {
std.debug.print("サイズクラス 2 (32B)\n", .{});
} else if (aligned_size <= 64) {
std.debug.print("サイズクラス 3 (64B)\n", .{});
} else if (aligned_size <= 4096) {
std.debug.print("サイズクラス N\n", .{});
} else {
std.debug.print("大規模割り当て\n", .{});
}
}
}
バケットの構造
各サイズクラスには、複数のバケットが存在し、それぞれが複数のブロックを管理します。
バケットの詳細構造:
┌────────────────────────────────────────────────────────┐
│ Bucket Header (サイズクラス 2: 32バイト) │
├────────────────────────────────────────────────────────┤
│ total_blocks: 64 // バケット内の総ブロック数 │
│ used_blocks: 23 // 使用中のブロック数 │
│ free_list_head: 0x... // フリーリストの先頭ポインタ │
│ prev_bucket: 0x... // 前のバケットへのポインタ │
│ next_bucket: 0x... // 次のバケットへのポインタ │
├────────────────────────────────────────────────────────┤
│ Bitmap (各ビットがブロックの使用状態を表す) │
│ 11101110 11011101 10111011 ... (64ビット = 8バイト) │
├────────────────────────────────────────────────────────┤
│ Data Area │
│ [32B Block 0] ← 使用中 (1) │
│ [32B Block 1] ← 使用中 (1) │
│ [32B Block 2] ← フリー (0) │
│ [32B Block 3] ← 使用中 (1) │
│ [32B Block 4] ← フリー (0) │
│ ... │
│ [32B Block 63] │
└────────────────────────────────────────────────────────┘
フリーリスト管理
フリーリストの実装
フリーリストは、解放されたメモリブロックを効率的に再利用するための仕組みです。
const std = @import("std");
// フリーリストノードの構造
const FreeNode = struct {
next: ?*FreeNode,
// 解放されたメモリブロック内に直接この構造体を配置
fn fromMemory(ptr: [*]u8) *FreeNode {
return @ptrCast(@alignCast(ptr));
}
fn toMemory(self: *FreeNode) [*]u8 {
return @ptrCast(self);
}
};
// フリーリストを管理する構造体
const FreeList = struct {
head: ?*FreeNode,
count: usize,
fn init() FreeList {
return .{
.head = null,
.count = 0,
};
}
// ブロックをフリーリストに追加
fn push(self: *FreeList, ptr: [*]u8) void {
const node = FreeNode.fromMemory(ptr);
node.next = self.head;
self.head = node;
self.count += 1;
}
// フリーリストからブロックを取得
fn pop(self: *FreeList) ?[*]u8 {
const node = self.head orelse return null;
self.head = node.next;
self.count -= 1;
return node.toMemory();
}
// フリーリストが空かどうか
fn isEmpty(self: *const FreeList) bool {
return self.head == null;
}
};
フリーリストの動作例
const std = @import("std");
pub fn demonstrateFreeList() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
std.debug.print("=== フリーリストの動作デモ ===\n\n", .{});
// 複数のブロックを割り当て
std.debug.print("ステップ 1: 5つのブロックを割り当て\n", .{});
const blocks = try allocator.alloc([*]u8, 5);
defer allocator.free(blocks);
var i: usize = 0;
while (i < 5) : (i += 1) {
blocks[i] = @ptrCast(try allocator.alloc(u8, 32));
std.debug.print(" Block {}: 割り当て完了\n", .{i});
}
// いくつかのブロックを解放
std.debug.print("\nステップ 2: Block 1, 3を解放\n", .{});
allocator.free(blocks[1][0..32]);
allocator.free(blocks[3][0..32]);
std.debug.print(" フリーリスト: [Block 3] -> [Block 1] -> null\n", .{});
// 新しいブロックを割り当て（フリーリストから再利用）
std.debug.print("\nステップ 3: 新しいブロックを2つ割り当て\n", .{});
const reused1 = try allocator.alloc(u8, 32);
std.debug.print(" 再利用: Block 1\n", .{});
const reused2 = try allocator.alloc(u8, 32);
std.debug.print(" 再利用: Block 3\n", .{});
// クリーンアップ
allocator.free(reused1);
allocator.free(reused2);
allocator.free(blocks[0][0..32]);
allocator.free(blocks[2][0..32]);
allocator.free(blocks[4][0..32]);
}
フリーリストのパフォーマンス
割り当て操作:
┌─────────────────────────────────────┐
│ 1. フリーリストをチェック │ O(1)
│ 2. headからノードを取得 │ O(1)
│ 3. headを次のノードに更新 │ O(1)
│ 4. メモリを返却 │ O(1)
└─────────────────────────────────────┘
総合: O(1) - 定数時間
解放操作:
┌─────────────────────────────────────┐
│ 1. メモリをノードに変換 │ O(1)
│ 2. ノードのnextを現在のheadに設定 │ O(1)
│ 3. headを新しいノードに更新 │ O(1)
└─────────────────────────────────────┘
総合: O(1) - 定数時間
スレッドセーフティ
マルチスレッド対応の実装
GPAは、設定により完全なスレッドセーフティを提供します。
const std = @import("std");
// スレッドセーフな割り当ての例
pub fn threadSafeAllocation() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{
.thread_safe = true, // スレッドセーフモードを有効化
}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
// 複数のスレッドから同時に使用可能
var threads: [4]std.Thread = undefined;
for (&threads, 0..) |*thread, i| {
thread.* = try std.Thread.spawn(.{}, workerThread, .{ allocator, i });
}
for (threads) |thread| {
thread.join();
}
std.debug.print("全てのスレッドが完了しました\n", .{});
}
fn workerThread(allocator: std.mem.Allocator, thread_id: usize) !void {
var i: usize = 0;
while (i < 100) : (i += 1) {
// スレッドセーフな割り当て
const buffer = try allocator.alloc(u8, 1024);
defer allocator.free(buffer);
// バッファを使用
@memset(buffer, @intCast(thread_id));
if (i % 10 == 0) {
std.debug.print("Thread {}: {}回目の割り当て完了\n", .{ thread_id, i });
}
}
}
ロック戦略
// GPAのスレッドセーフティ実装の概念
const std = @import("std");
const ThreadSafeBucket = struct {
mutex: std.Thread.Mutex,
free_list: FreeList,
used_count: usize,
fn init() ThreadSafeBucket {
return .{
.mutex = .{},
.free_list = FreeList.init(),
.used_count = 0,
};
}
fn allocate(self: *ThreadSafeBucket, size: usize) ![]u8 {
// バケット全体をロック
self.mutex.lock();
defer self.mutex.unlock();
// フリーリストから取得
if (self.free_list.pop()) |ptr| {
self.used_count += 1;
return ptr[0..size];
}
// 新しいメモリを割り当て
// （実装の詳細は省略）
return error.OutOfMemory;
}
fn free(self: *ThreadSafeBucket, ptr: []u8) void {
self.mutex.lock();
defer self.mutex.unlock();
// フリーリストに返却
self.free_list.push(ptr.ptr);
self.used_count -= 1;
}
};
const FreeList = struct {
head: ?*FreeNode,
count: usize,
fn init() FreeList {
return .{ .head = null, .count = 0 };
}
fn push(self: *FreeList, ptr: [*]u8) void {
_ = self;
_ = ptr;
}
fn pop(self: *FreeList) ?[*]u8 {
_ = self;
return null;
}
};
const FreeNode = struct {
next: ?*FreeNode,
};
ロック競合の最小化
スレッド間のロック戦略:
Thread 1 Thread 2 Thread 3
| | |
| Size Class 2 | Size Class 2 | Size Class 5
| lock() | wait... | lock()
| allocate() | | | allocate()
| unlock() | | | unlock()
| | lock() |
| | allocate() |
| | unlock() |
各サイズクラスごとに独立したロックを持つため、
異なるサイズクラスへのアクセスは競合しない
大規模割り当ての処理
ラージアロケーションの閾値
GPAは、特定のサイズを超える割り当てを「大規模割り当て」として特別に扱います。
const std = @import("std");
const LARGE_ALLOC_THRESHOLD = 4096; // 4KB
pub fn demonstrateLargeAllocation() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
// 小規模割り当て（サイズクラスバケットから）
const small = try allocator.alloc(u8, 1024);
defer allocator.free(small);
std.debug.print("小規模: 1KB - サイズクラスバケットから割り当て\n", .{});
// 中規模割り当て（まだサイズクラスバケットから）
const medium = try allocator.alloc(u8, 2048);
defer allocator.free(medium);
std.debug.print("中規模: 2KB - サイズクラスバケットから割り当て\n", .{});
// 大規模割り当て（直接OSから）
const large = try allocator.alloc(u8, 1024 * 1024);
defer allocator.free(large);
std.debug.print("大規模: 1MB - OSから直接割り当て\n", .{});
// 超大規模割り当て
const huge = try allocator.alloc(u8, 100 * 1024 * 1024);
defer allocator.free(huge);
std.debug.print("超大規模: 100MB - OSから直接割り当て\n", .{});
}
大規模割り当ての戦略
大規模割り当てのフロー:
┌─────────────────────────────────────┐
│ 割り当て要求: 1MB │
└───────────┬─────────────────────────┘
│
▼
┌─────────────────────────────────────┐
│ サイズチェック: > 4KB ? │
│ YES: 大規模割り当てパスへ │
└───────────┬─────────────────────────┘
│
▼
┌─────────────────────────────────────┐
│ ページサイズにアライメント │
│ 1MB -> 1MB (すでにアライメント済み) │
└───────────┬─────────────────────────┘
│
▼
┌─────────────────────────────────────┐
│ OSのmmap/VirtualAllocを直接呼び出し │
│ - ページテーブルに直接マップ │
│ - バケット管理をバイパス │
└───────────┬─────────────────────────┘
│
▼
┌─────────────────────────────────────┐
│ メタデータを記録 │
│ - 割り当てサイズ │
│ - アドレス範囲 │
│ - タイムスタンプ（デバッグ用） │
└─────────────────────────────────────┘
他のアロケータとの統合
アロケータチェーン
GPAは、他のアロケータと組み合わせて使用できます。
const std = @import("std");
pub fn allocatorChainExample() !void {
// ベースアロケータとしてGPAを使用
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const base_allocator = gpa.allocator();
// その上にArenaAllocatorを構築
var arena = std.heap.ArenaAllocator.init(base_allocator);
defer arena.deinit();
const arena_allocator = arena.allocator();
// Arenaで一時的なメモリを大量に割り当て
var i: usize = 0;
while (i < 1000) : (i += 1) {
const temp = try arena_allocator.alloc(u8, 1024);
_ = temp;
// 個別の解放は不要
}
// arena.deinit()で一括解放され、GPAに返却される
}
カスタムバッキングアロケータ
const std = @import("std");
// GPAのバッキングアロケータをカスタマイズ
pub fn customBackingAllocator() !void {
// ページアロケータを直接使用
var gpa_with_page = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa_with_page.deinit();
const allocator = gpa_with_page.allocator();
// 内部的には page_allocator を使用してメモリを確保
const memory = try allocator.alloc(u8, 1024);
defer allocator.free(memory);
}
実世界のユースケース
ケーススタディ1: Zigコンパイラ
Zigコンパイラ自体がGPAを広範に使用しています。
// Zigコンパイラでの使用例（簡略化）
const std = @import("std");
const Compilation = struct {
gpa: std.heap.GeneralPurposeAllocator(.{}),
arena: std.heap.ArenaAllocator,
fn init() !Compilation {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
const arena = std.heap.ArenaAllocator.init(gpa.allocator());
return Compilation{
.gpa = gpa,
.arena = arena,
};
}
fn deinit(self: *Compilation) void {
// Arenaで割り当てたメモリを一括解放
self.arena.deinit();
// GPAでメモリリークをチェック
const leaked = self.gpa.deinit();
if (leaked == .leak) {
std.debug.print("コンパイラ内でメモリリークが検出されました！\n", .{});
}
}
fn compile(self: *Compilation) !void {
// 長期間必要なデータはGPAから直接割り当て
const gpa_allocator = self.gpa.allocator();
const module_list = try gpa_allocator.alloc(Module, 100);
defer gpa_allocator.free(module_list);
// コンパイルパスごとの一時データはArenaで管理
const arena_allocator = self.arena.allocator();
// パース段階
const ast = try parseSource(arena_allocator);
_ = ast;
// セマンティック解析段階
const analyzed = try analyzeSemantics(arena_allocator);
_ = analyzed;
// コード生成段階
const code = try generateCode(arena_allocator);
_ = code;
// 各段階が終わるとArenaがリセットされる
}
};
const Module = struct {
name: []const u8,
path: []const u8,
};
fn parseSource(allocator: std.mem.Allocator) !void {
_ = allocator;
}
fn analyzeSemantics(allocator: std.mem.Allocator) !void {
_ = allocator;
}
fn generateCode(allocator: std.mem.Allocator) !void {
_ = allocator;
}
ケーススタディ2: CLIツール
const std = @import("std");
pub fn cliToolExample() !void {
// CLIツールの標準的な構造
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer {
const leaked = gpa.deinit();
if (leaked == .leak) {
std.debug.print("警告: メモリリークが検出されました\n", .{});
}
}
const allocator = gpa.allocator();
// コマンドライン引数の処理
const args = try std.process.argsAlloc(allocator);
defer std.process.argsFree(allocator, args);
if (args.len < 2) {
std.debug.print("使用法: {s} <command>\n", .{args[0]});
return;
}
// コマンドの実行
const command = args[1];
if (std.mem.eql(u8, command, "build")) {
try runBuild(allocator);
} else if (std.mem.eql(u8, command, "test")) {
try runTest(allocator);
} else {
std.debug.print("未知のコマンド: {s}\n", .{command});
}
}
fn runBuild(allocator: std.mem.Allocator) !void {
std.debug.print("ビルドを開始します...\n", .{});
// ビルド設定の読み込み
const config = try allocator.alloc(u8, 1024);
defer allocator.free(config);
// ファイルリストの構築
var files = std.ArrayList([]const u8).init(allocator);
defer files.deinit();
try files.append("src/main.zig");
try files.append("src/utils.zig");
// ビルド実行
for (files.items) |file| {
std.debug.print("コンパイル中: {s}\n", .{file});
}
std.debug.print("ビルド完了！\n", .{});
}
fn runTest(allocator: std.mem.Allocator) !void {
_ = allocator;
std.debug.print("テストを実行します...\n", .{});
}
ケーススタディ3: ゲームエンジン
const std = @import("std");
const GameEngine = struct {
gpa: std.heap.GeneralPurposeAllocator(.{ .thread_safe = true }),
frame_arena: std.heap.ArenaAllocator,
level_arena: std.heap.ArenaAllocator,
fn init() !GameEngine {
var gpa = std.heap.GeneralPurposeAllocator(.{ .thread_safe = true }){};
const gpa_allocator = gpa.allocator();
return GameEngine{
.gpa = gpa,
.frame_arena = std.heap.ArenaAllocator.init(gpa_allocator),
.level_arena = std.heap.ArenaAllocator.init(gpa_allocator),
};
}
fn deinit(self: *GameEngine) void {
self.frame_arena.deinit();
self.level_arena.deinit();
_ = self.gpa.deinit();
}
fn gameLoop(self: *GameEngine) !void {
var frame: usize = 0;
while (frame < 10) : (frame += 1) {
try self.updateFrame(frame);
// フレーム終了時にArenaをリセット
_ = self.frame_arena.reset(.retain_capacity);
}
}
fn updateFrame(self: *GameEngine, frame_num: usize) !void {
const frame_allocator = self.frame_arena.allocator();
// フレームごとの一時データ
const particles = try frame_allocator.alloc(Particle, 1000);
_ = particles;
const ui_elements = try frame_allocator.alloc(UIElement, 50);
_ = ui_elements;
std.debug.print("フレーム {} 更新完了\n", .{frame_num});
}
fn loadLevel(self: *GameEngine, level_name: []const u8) !void {
// 前のレベルデータを解放
_ = self.level_arena.reset(.free_all);
const level_allocator = self.level_arena.allocator();
// レベルデータの読み込み
const entities = try level_allocator.alloc(Entity, 500);
_ = entities;
const terrain = try level_allocator.alloc(TerrainChunk, 100);
_ = terrain;
std.debug.print("レベル '{s}' を読み込みました\n", .{level_name});
}
};
const Particle = struct {
x: f32,
y: f32,
velocity_x: f32,
velocity_y: f32,
};
const UIElement = struct {
text: []const u8,
x: i32,
y: i32,
};
const Entity = struct {
id: u32,
position: [3]f32,
};
const TerrainChunk = struct {
vertices: [64]f32,
};
pub fn gameEngineDemo() !void {
var engine = try GameEngine.init();
defer engine.deinit();
// レベル読み込み
try engine.loadLevel("level_1");
// ゲームループ
try engine.gameLoop();
// 別のレベル読み込み
try engine.loadLevel("level_2");
}
パフォーマンス最適化技法
メモリプールの事前割り当て
const std = @import("std");
pub fn preallocationExample() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
// 大量の小規模オブジェクトを扱う場合、
// ArrayListの容量を事前に確保
var objects = std.ArrayList(Object).init(allocator);
defer objects.deinit();
// 1000個のオブジェクトを格納する予定
try objects.ensureTotalCapacity(1000);
// これで再割り当てなしで追加可能
var i: usize = 0;
while (i < 1000) : (i += 1) {
objects.appendAssumeCapacity(.{
.id = i,
.data = i * 2,
});
}
std.debug.print("{} オブジェクトを効率的に割り当てました\n", .{objects.items.len});
}
const Object = struct {
id: usize,
data: usize,
};
バッチ処理
const std = @import("std");
pub fn batchAllocationExample() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
std.debug.print("=== 個別割り当て vs バッチ割り当て ===\n\n", .{});
// ❌ 非効率: 個別に割り当て
{
var timer = try std.time.Timer.start();
var buffers: [100][]u8 = undefined;
for (&buffers) |*buf| {
buf.* = try allocator.alloc(u8, 64);
}
const individual_time = timer.read();
for (buffers) |buf| {
allocator.free(buf);
}
std.debug.print("個別割り当て: {}ns\n", .{individual_time});
}
// ✅ 効率的: 一括で割り当て
{
var timer = try std.time.Timer.start();
const batch = try allocator.alloc([64]u8, 100);
const batch_time = timer.read();
allocator.free(batch);
std.debug.print("バッチ割り当て: {}ns\n", .{batch_time});
}
}
トラブルシューティング
よくある問題と解決策
const std = @import("std");
// 問題1: メモリリーク
pub fn memoryLeakExample() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer {
const leaked = gpa.deinit();
if (leaked == .leak) {
// ここでメモリリークが検出される
std.debug.print("メモリリークが検出されました！\n", .{});
}
}
const allocator = gpa.allocator();
// ❌ メモリリーク
const leaked_memory = try allocator.alloc(u8, 1024);
_ = leaked_memory;
// freeを忘れている！
}
// 問題2: ダブルフリー
pub fn doubleFreeExample() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{
.safety = true, // 安全性チェックを有効化
}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
const memory = try allocator.alloc(u8, 1024);
allocator.free(memory);
// allocator.free(memory); // ❌ パニックが発生
}
// 問題3: use-after-free
pub fn useAfterFreeExample() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{
.safety = true,
}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
const memory = try allocator.alloc(u8, 1024);
allocator.free(memory);
// ❌ 解放後の使用（デバッグモードで検出される）
// memory[0] = 42; // パニックが発生
}
まとめ
このセクションでは、GPAの内部実装について詳しく学びました。
重要なポイント
- サイズクラスシステム: メモリを予め決められたサイズに分類し、効率的に管理
- フリーリスト: 解放されたメモリを再利用するための高速なデータ構造
- スレッドセーフティ: ロックによるマルチスレッド対応
- 大規模割り当て: 閾値を超える割り当ては直接OSから取得
- 実用例: コンパイラ、CLIツール、ゲームエンジンでの活用
次のステップ
次のセクション「Exercise 04」では、これらの知識を実践的な課題で確認します。GPAを使用した様々なプログラムを実装し、理解を深めましょう。