Exercise 04: General Purpose Allocator - 実践課題

課題の概要

このエクササイズでは、General Purpose Allocator（GPA）を使用した実践的なプログラムを実装します。GPAの特性を理解し、適切に使用する能力を身につけることが目標です。

評価基準

マンダトリー要件（80点）

以下の4つの課題をすべて完成させることで、80点を獲得できます。

ボーナス要件（20点）

マンダトリー要件をすべて完了した上で、追加課題に取り組むことで最大20点を獲得できます。

---

マンダトリー課題

課題1: メモリプールマネージャー（20点）

効率的なメモリプールマネージャーを実装してください。

要件

const std = @import("std");

/// メモリプールマネージャー
/// 頻繁に割り当て/解放されるオブジェクトを効率的に管理
pub const MemoryPool = struct {
    allocator: std.mem.Allocator,
    pools: std.AutoHashMap(usize, Pool),

    const Pool = struct {
        block_size: usize,
        free_list: std.ArrayList([]u8),
        allocated_count: usize,
        freed_count: usize,
    };

    pub fn init(allocator: std.mem.Allocator) MemoryPool {
        // TODO: 実装してください
    }

    pub fn deinit(self: *MemoryPool) void {
        // TODO: 実装してください
    }

    /// 指定サイズのメモリを割り当て
    pub fn alloc(self: *MemoryPool, size: usize) ![]u8 {
        // TODO: 実装してください
        // 1. サイズに対応するプールを検索
        // 2. フリーリストに空きがあればそこから取得
        // 3. なければ新規に割り当て
    }

    /// メモリを解放（フリーリストに追加）
    pub fn free(self: *MemoryPool, memory: []u8) void {
        // TODO: 実装してください
    }

    /// プールの統計情報を表示
    pub fn printStats(self: *const MemoryPool) void {
        // TODO: 実装してください
        // - 各プールのブロックサイズ
        // - 割り当て回数
        // - 解放回数
        // - 現在のフリーリストサイズ
    }
};

// テストコード
pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var pool = MemoryPool.init(allocator);
    defer pool.deinit();

    // 様々なサイズのメモリを割り当て
    var buffers: [10][]u8 = undefined;
    for (&buffers, 0..) |*buf, i| {
        const size = (i + 1) * 64;
        buf.* = try pool.alloc(size);
        std.debug.print("割り当て {}: {}バイト\n", .{ i, size });
    }

    // いくつかを解放
    pool.free(buffers[0]);
    pool.free(buffers[2]);
    pool.free(buffers[4]);

    // 再度割り当て（フリーリストから再利用されるはず）
    const reused = try pool.alloc(64);
    _ = reused;

    // 統計情報を表示
    pool.printStats();

    // 残りを解放
    pool.free(buffers[1]);
    pool.free(buffers[3]);
    pool.free(buffers[5]);
    pool.free(buffers[6]);
    pool.free(buffers[7]);
    pool.free(buffers[8]);
    pool.free(buffers[9]);
    pool.free(reused);
}

期待される出力例

割り当て 0: 64バイト
割り当て 1: 128バイト
割り当て 2: 192バイト
...
割り当て 9: 640バイト

=== メモリプール統計 ===
プール 64B: 割り当て=2回, 解放=1回, フリーリスト=1個
プール 128B: 割り当て=1回, 解放=0回, フリーリスト=0個
プール 192B: 割り当て=1回, 解放=1回, フリーリスト=1個
...

---

課題2: リソースマネージャー（20点）

ゲームやアプリケーションで使用するリソース（テクスチャ、サウンドなど）を管理するシステムを実装してください。

要件

const std = @import("std");

/// リソースの種類
pub const ResourceType = enum {
    texture,
    sound,
    model,
    script,
};

/// リソースデータ
pub const Resource = struct {
    id: u32,
    name: []const u8,
    resource_type: ResourceType,
    data: []u8,
    reference_count: usize,

    pub fn init(
        allocator: std.mem.Allocator,
        id: u32,
        name: []const u8,
        resource_type: ResourceType,
        size: usize,
    ) !Resource {
        // TODO: 実装してください
    }

    pub fn deinit(self: *Resource, allocator: std.mem.Allocator) void {
        // TODO: 実装してください
    }

    pub fn addRef(self: *Resource) void {
        self.reference_count += 1;
    }

    pub fn release(self: *Resource) bool {
        if (self.reference_count > 0) {
            self.reference_count -= 1;
        }
        return self.reference_count == 0;
    }
};

/// リソースマネージャー
pub const ResourceManager = struct {
    allocator: std.mem.Allocator,
    resources: std.AutoHashMap(u32, Resource),
    next_id: u32,

    pub fn init(allocator: std.mem.Allocator) ResourceManager {
        // TODO: 実装してください
    }

    pub fn deinit(self: *ResourceManager) void {
        // TODO: 実装してください
        // すべてのリソースを解放
    }

    /// リソースを読み込み
    pub fn loadResource(
        self: *ResourceManager,
        name: []const u8,
        resource_type: ResourceType,
        size: usize,
    ) !u32 {
        // TODO: 実装してください
        // 1. 新しいリソースIDを生成
        // 2. リソースを作成
        // 3. ハッシュマップに登録
        // 4. リソースIDを返却
    }

    /// リソースを取得（参照カウントを増やす）
    pub fn getResource(self: *ResourceManager, id: u32) ?*Resource {
        // TODO: 実装してください
    }

    /// リソースを解放（参照カウントを減らす）
    pub fn releaseResource(self: *ResourceManager, id: u32) !void {
        // TODO: 実装してください
        // 参照カウントが0になったらリソースを削除
    }

    /// 統計情報を表示
    pub fn printStats(self: *const ResourceManager) void {
        // TODO: 実装してください
    }
};

// テストコード
pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var manager = ResourceManager.init(allocator);
    defer manager.deinit();

    // リソースを読み込み
    const texture1 = try manager.loadResource("player.png", .texture, 1024 * 1024);
    const sound1 = try manager.loadResource("bgm.mp3", .sound, 512 * 1024);
    const model1 = try manager.loadResource("character.obj", .model, 2 * 1024 * 1024);

    // リソースを使用
    if (manager.getResource(texture1)) |res| {
        std.debug.print("リソース取得: {s} (参照カウント: {})\n", .{ res.name, res.reference_count });
    }

    // 同じリソースを複数回取得
    _ = manager.getResource(texture1);
    _ = manager.getResource(texture1);

    // 統計表示
    manager.printStats();

    // リソースを解放
    try manager.releaseResource(texture1);
    try manager.releaseResource(texture1);
    try manager.releaseResource(texture1); // 最後の参照を解放

    try manager.releaseResource(sound1);
    try manager.releaseResource(model1);

    std.debug.print("\n解放後の統計:\n", .{});
    manager.printStats();
}

---

課題3: 動的配列の実装（20点）

GPAを使用して、C++のstd::vectorに相当する動的配列を実装してください。

要件

const std = @import("std");

/// 動的配列（ジェネリック版）
pub fn DynamicArray(comptime T: type) type {
    return struct {
        const Self = @This();

        allocator: std.mem.Allocator,
        items: []T,
        capacity: usize,
        len: usize,

        pub fn init(allocator: std.mem.Allocator) Self {
            // TODO: 実装してください
        }

        pub fn deinit(self: *Self) void {
            // TODO: 実装してください
        }

        /// 要素を末尾に追加
        pub fn append(self: *Self, item: T) !void {
            // TODO: 実装してください
            // 容量が足りない場合は拡張（2倍にする）
        }

        /// 指定位置に要素を挿入
        pub fn insert(self: *Self, index: usize, item: T) !void {
            // TODO: 実装してください
        }

        /// 指定位置の要素を削除
        pub fn remove(self: *Self, index: usize) T {
            // TODO: 実装してください
        }

        /// 配列をクリア（容量は保持）
        pub fn clear(self: *Self) void {
            self.len = 0;
        }

        /// 指定容量を確保
        pub fn reserve(self: *Self, new_capacity: usize) !void {
            // TODO: 実装してください
        }

        /// 配列を縮小（未使用容量を解放）
        pub fn shrinkToFit(self: *Self) !void {
            // TODO: 実装してください
        }

        /// 要素を取得
        pub fn get(self: *const Self, index: usize) ?T {
            if (index >= self.len) return null;
            return self.items[index];
        }

        /// 統計情報を表示
        pub fn printStats(self: *const Self) void {
            std.debug.print("長さ: {}, 容量: {}, 使用率: {d:.1}%\n", .{
                self.len,
                self.capacity,
                @as(f64, @floatFromInt(self.len)) / @as(f64, @floatFromInt(self.capacity)) * 100.0,
            });
        }
    };
}

// テストコード
pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var array = DynamicArray(i32).init(allocator);
    defer array.deinit();

    // 要素を追加
    var i: i32 = 0;
    while (i < 10) : (i += 1) {
        try array.append(i);
    }

    std.debug.print("初期状態:\n", .{});
    array.printStats();

    // 挿入
    try array.insert(5, 999);
    std.debug.print("\n5番目に999を挿入後:\n", .{});
    array.printStats();

    // 削除
    _ = array.remove(5);
    std.debug.print("\n5番目を削除後:\n", .{});
    array.printStats();

    // さらに要素を追加（再割り当てが発生するはず）
    i = 10;
    while (i < 100) : (i += 1) {
        try array.append(i);
    }

    std.debug.print("\n100要素まで追加後:\n", .{});
    array.printStats();

    // 縮小
    try array.shrinkToFit();
    std.debug.print("\n縮小後:\n", .{});
    array.printStats();
}

---

課題4: マルチスレッドタスクキュー（20点）

複数のワーカースレッドでタスクを処理するシステムを実装してください。

要件

const std = @import("std");

/// タスク構造体
pub const Task = struct {
    id: usize,
    data: []u8,
    process_fn: *const fn ([]u8) void,

    pub fn execute(self: *const Task) void {
        self.process_fn(self.data);
    }
};

/// スレッドセーフなタスクキュー
pub const TaskQueue = struct {
    allocator: std.mem.Allocator,
    queue: std.ArrayList(Task),
    mutex: std.Thread.Mutex,
    condition: std.Thread.Condition,
    shutdown: bool,

    pub fn init(allocator: std.mem.Allocator) TaskQueue {
        // TODO: 実装してください
    }

    pub fn deinit(self: *TaskQueue) void {
        // TODO: 実装してください
    }

    /// タスクをキューに追加
    pub fn push(self: *TaskQueue, task: Task) !void {
        // TODO: 実装してください
        // 1. ミューテックスでロック
        // 2. キューに追加
        // 3. 待機中のワーカーに通知
        // 4. アンロック
    }

    /// タスクをキューから取得
    pub fn pop(self: *TaskQueue) ?Task {
        // TODO: 実装してください
        // 1. ミューテックスでロック
        // 2. キューが空なら待機
        // 3. タスクを取得
        // 4. アンロック
    }

    /// シャットダウン要求
    pub fn requestShutdown(self: *TaskQueue) void {
        self.mutex.lock();
        defer self.mutex.unlock();
        self.shutdown = true;
        self.condition.broadcast();
    }
};

/// ワーカースレッド
fn workerThread(queue: *TaskQueue, worker_id: usize) void {
    std.debug.print("ワーカー {} 起動\n", .{worker_id});

    while (true) {
        if (queue.pop()) |task| {
            std.debug.print("ワーカー {}: タスク {} を処理中\n", .{ worker_id, task.id });
            task.execute();
            std.debug.print("ワーカー {}: タスク {} 完了\n", .{ worker_id, task.id });
        } else {
            // シャットダウン要求
            break;
        }
    }

    std.debug.print("ワーカー {} 終了\n", .{worker_id});
}

// サンプルタスク処理関数
fn processTask(data: []u8) void {
    // 重い処理をシミュレート
    std.time.sleep(100 * std.time.ns_per_ms);
    _ = data;
}

// テストコード
pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{ .thread_safe = true }){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var queue = TaskQueue.init(allocator);
    defer queue.deinit();

    // ワーカースレッドを起動
    const num_workers = 4;
    var workers: [num_workers]std.Thread = undefined;

    for (&workers, 0..) |*worker, i| {
        worker.* = try std.Thread.spawn(.{}, workerThread, .{ &queue, i });
    }

    // タスクを投入
    var i: usize = 0;
    while (i < 20) : (i += 1) {
        const data = try allocator.alloc(u8, 1024);
        const task = Task{
            .id = i,
            .data = data,
            .process_fn = processTask,
        };
        try queue.push(task);
        std.debug.print("タスク {} を投入\n", .{i});
    }

    // すべてのタスクが完了するまで待機
    std.time.sleep(3 * std.time.ns_per_s);

    // シャットダウン
    queue.requestShutdown();

    // ワーカーの終了を待機
    for (workers) |worker| {
        worker.join();
    }

    std.debug.print("\nすべてのワーカーが終了しました\n", .{});
}

---

ボーナス課題

マンダトリー課題をすべて完了した場合のみ、以下のボーナス課題に取り組んでください。

ボーナス課題1: メモリ使用量の可視化（10点）

GPAを使用したプログラムのメモリ使用量を時系列で追跡し、グラフ化するツールを実装してください。

要件

const std = @import("std");

/// メモリ使用量のスナップショット
pub const MemorySnapshot = struct {
    timestamp: i64,
    allocated_bytes: usize,
    freed_bytes: usize,
    current_usage: usize,
    allocation_count: usize,
};

/// メモリプロファイラー
pub const MemoryProfiler = struct {
    allocator: std.mem.Allocator,
    snapshots: std.ArrayList(MemorySnapshot),
    total_allocated: usize,
    total_freed: usize,
    allocation_count: usize,

    pub fn init(allocator: std.mem.Allocator) MemoryProfiler {
        // TODO: 実装してください
    }

    pub fn deinit(self: *MemoryProfiler) void {
        // TODO: 実装してください
    }

    /// スナップショットを記録
    pub fn takeSnapshot(self: *MemoryProfiler) !void {
        // TODO: 実装してください
    }

    /// 割り当てを記録
    pub fn recordAllocation(self: *MemoryProfiler, size: usize) void {
        self.total_allocated += size;
        self.allocation_count += 1;
    }

    /// 解放を記録
    pub fn recordFree(self: *MemoryProfiler, size: usize) void {
        self.total_freed += size;
    }

    /// レポートを生成（ASCIIグラフ）
    pub fn generateReport(self: *const MemoryProfiler) !void {
        // TODO: 実装してください
        // 時系列でメモリ使用量をASCIIグラフで表示
    }
};

// 使用例
pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var profiler = MemoryProfiler.init(allocator);
    defer profiler.deinit();

    // プログラムの実行をシミュレート
    var i: usize = 0;
    while (i < 10) : (i += 1) {
        // メモリを割り当て
        const size = (i + 1) * 1024;
        const mem = try allocator.alloc(u8, size);
        profiler.recordAllocation(size);

        try profiler.takeSnapshot();

        std.time.sleep(100 * std.time.ns_per_ms);

        // 半分を解放
        if (i % 2 == 0) {
            allocator.free(mem);
            profiler.recordFree(size);
        }
    }

    // レポート生成
    try profiler.generateReport();
}

期待される出力例

=== メモリ使用量レポート ===

時刻    使用量(KB)  グラフ
0.0s    1.0        ▂
0.1s    3.0        ▃
0.2s    3.0        ▃
0.3s    9.0        ▆
0.4s    9.0        ▆
0.5s    21.0       █
...

総割り当て: 55KB
総解放: 15KB
現在使用中: 40KB
割り当て回数: 10回

---

ボーナス課題2: カスタムアロケータの実装（10点）

GPAをベースに、特定の用途に最適化したカスタムアロケータを実装してください。

要件

• Small Object Allocator: 小さなオブジェクト（< 128B）専用の高速アロケータ
• Slab Allocator: 固定サイズオブジェクト専用のアロケータ
• Zone Allocator: ゾーン単位でメモリを管理するアロケータ

const std = @import("std");

/// Slab Allocator（固定サイズオブジェクト専用）
pub fn SlabAllocator(comptime object_size: usize) type {
    return struct {
        const Self = @This();
        const slab_size = 4096; // 1ページ
        const objects_per_slab = slab_size / object_size;

        backing_allocator: std.mem.Allocator,
        slabs: std.ArrayList(Slab),
        free_list: ?*FreeNode,

        const Slab = struct {
            memory: []u8,
            used_count: usize,
        };

        const FreeNode = struct {
            next: ?*FreeNode,
        };

        pub fn init(backing_allocator: std.mem.Allocator) Self {
            // TODO: 実装してください
        }

        pub fn deinit(self: *Self) void {
            // TODO: 実装してください
        }

        pub fn allocator(self: *Self) std.mem.Allocator {
            return std.mem.Allocator{
                .ptr = self,
                .vtable = &.{
                    .alloc = alloc,
                    .resize = resize,
                    .free = free,
                },
            };
        }

        fn alloc(ctx: *anyopaque, len: usize, ptr_align: u8, ret_addr: usize) ?[*]u8 {
            // TODO: 実装してください
            _ = ctx;
            _ = len;
            _ = ptr_align;
            _ = ret_addr;
            return null;
        }

        fn resize(ctx: *anyopaque, buf: []u8, buf_align: u8, new_len: usize, ret_addr: usize) bool {
            // TODO: 実装してください
            _ = ctx;
            _ = buf;
            _ = buf_align;
            _ = new_len;
            _ = ret_addr;
            return false;
        }

        fn free(ctx: *anyopaque, buf: []u8, buf_align: u8, ret_addr: usize) void {
            // TODO: 実装してください
            _ = ctx;
            _ = buf;
            _ = buf_align;
            _ = ret_addr;
        }
    };
}

// 使用例
pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const backing = gpa.allocator();

    var slab = SlabAllocator(64).init(backing);
    defer slab.deinit();

    const allocator = slab.allocator();

    // 64バイトオブジェクトを高速に割り当て
    var objects: [100][]u8 = undefined;
    var i: usize = 0;
    while (i < 100) : (i += 1) {
        objects[i] = try allocator.alloc(u8, 64);
    }

    // 解放
    for (objects) |obj| {
        allocator.free(obj);
    }
}

---

提出要件

ファイル構成

exercise04/
├── mandatory/
│   ├── task1_memory_pool.zig
│   ├── task2_resource_manager.zig
│   ├── task3_dynamic_array.zig
│   └── task4_task_queue.zig
├── bonus/
│   ├── task5_memory_profiler.zig
│   └── task6_slab_allocator.zig
└── README.md

README.md の内容

以下の情報を含めてください：

• 実装の概要: 各課題で実装した内容の説明
• 実行方法: コンパイルと実行の手順
• テスト結果: 各課題の実行結果（スクリーンショットまたはテキスト）
• 学んだこと: この課題を通じて学んだことや気づき
• 課題点: 実装で苦労した点や改善の余地

コンパイルと実行

# 課題1
zig build-exe mandatory/task1_memory_pool.zig
./task1_memory_pool

# 課題2
zig build-exe mandatory/task2_resource_manager.zig
./task2_resource_manager

# 課題3
zig build-exe mandatory/task3_dynamic_array.zig
./task3_dynamic_array

# 課題4
zig build-exe mandatory/task4_task_queue.zig
./task4_task_queue

# ボーナス課題1
zig build-exe bonus/task5_memory_profiler.zig
./task5_memory_profiler

# ボーナス課題2
zig build-exe bonus/task6_slab_allocator.zig
./task6_slab_allocator

---

評価基準の詳細

課題1（20点）

• 基本機能（10点）: alloc/freeが正しく動作
• 効率性（5点）: フリーリストからの再利用が機能
• 統計表示（5点）: 詳細な統計情報を表示

課題2（20点）

• 基本機能（10点）: リソースの読み込み/解放が動作
• 参照カウント（5点）: 参照カウントの管理が正確
• メモリ管理（5点）: メモリリークがない

課題3（20点）

• 基本機能（10点）: append/insert/removeが動作
• 動的拡張（5点）: 容量が適切に拡張される
• 効率性（5点）: shrinkToFitが正しく動作

課題4（20点）

• 基本機能（10点）: タスクの投入/処理が動作
• スレッドセーフティ（5点）: 競合状態がない
• 正確性（5点）: すべてのタスクが処理される

ボーナス課題1（10点）

• データ収集（5点）: 正確なメモリ使用量を記録
• 可視化（5点）: 分かりやすいグラフを生成

ボーナス課題2（10点）

• 正確性（5点）: アロケータが正しく動作
• 効率性（5点）: GPAよりも高速

---

ヒントとアドバイス

課題1のヒント

• サイズごとに別々のプールを管理することで、フラグメンテーションを削減
• フリーリストは単方向連結リストで十分
• 統計情報は各操作時に更新

課題2のヒント

• AutoHashMapを使用してリソースIDから効率的にアクセス
• deinit時に参照カウントが0でないリソースに警告を出す
• 名前の重複チェックを実装すると良い

課題3のヒント

• 容量が足りなくなったら2倍に拡張（一般的な戦略）
• insertとremoveでは要素のシフトが必要
• @memcpyを使用して効率的にコピー

課題4のヒント

• Mutexで排他制御、Conditionで待機/通知
• shutdownフラグで終了をワーカーに通知
• デッドロックに注意（ロックの順序を統一）

ボーナス課題1のヒント

• タイムスタンプにはstd.time.milliTimestampを使用
• グラフは最大値を基準に正規化
• ブロック文字（▁▂▃▄▅▆▇█）で可視化

ボーナス課題2のヒント

• std.mem.Allocatorインターフェースを実装
• Slabは一度に多くのオブジェクトを確保
• フリーリストで未使用オブジェクトを管理

---

まとめ

このエクササイズを通じて、以下のスキルを習得します：

• GPAの実践的な使用: 様々なシナリオでの適切な使用方法
• メモリ効率: フリーリストを使った効率的なメモリ再利用
• スレッドセーフティ: マルチスレッド環境での安全なメモリ管理
• パフォーマンス最適化: 用途に応じた最適化技法

すべての課題を完了することで、GPAを使いこなせるようになります。頑張ってください！