課題2: Arenaアロケータの実装と最適化

マンダトリー要件 (80点)

Part 1: カスタムArenaアロケータ (30点)

動的に拡張するArenaアロケータを一から実装してください。

要件:

const std = @import("std");

pub const CustomArena = struct {
    const BufferNode = struct {
        next: ?*BufferNode,
        capacity: usize,
        used: usize,

        // バッファデータはノードの直後に配置される
        fn buffer(self: *BufferNode) []u8 {
            // TODO: 実装
            // ヒント: @ptrCast を使ってノードの後ろのメモリを取得
        }
    };

    parent_allocator: std.mem.Allocator,
    first_node: ?*BufferNode,
    current_node: ?*BufferNode,
    total_allocated: usize,
    total_capacity: usize,

    const INITIAL_SIZE = 4096;
    const GROWTH_FACTOR = 2;

    pub fn init(parent_allocator: std.mem.Allocator) CustomArena {
        // TODO: 実装
    }

    pub fn deinit(self: *CustomArena) void {
        // TODO: 実装
        // - 全てのBufferNodeを走査して解放
        // - 統計情報を出力（オプション）
    }

    pub fn allocator(self: *CustomArena) std.mem.Allocator {
        // TODO: 実装
    }

    fn createBuffer(self: *CustomArena, min_size: usize) !*BufferNode {
        // TODO: 実装
        // 1. 適切なバッファサイズを計算（成長戦略）
        // 2. BufferNode + バッファ分のメモリを確保
        // 3. ノードを初期化
        // 4. リンクリストに追加
        // 5. 統計を更新
    }

    fn alloc(
        ctx: *anyopaque,
        len: usize,
        ptr_align: u8,
        ret_addr: usize,
    ) ?[*]u8 {
        // TODO: 実装
        // 1. 現在のノードから割り当てを試みる
        // 2. 失敗したら新しいバッファを作成
        // 3. アライメントを考慮
    }

    fn resize(
        ctx: *anyopaque,
        buf: []u8,
        buf_align: u8,
        new_len: usize,
        ret_addr: usize,
    ) bool {
        // TODO: 実装
        // Arenaはリサイズをサポートしない
        return false;
    }

    fn free(
        ctx: *anyopaque,
        buf: []u8,
        buf_align: u8,
        ret_addr: usize,
    ) void {
        // TODO: 実装
        // Arenaは個別の解放をしない
    }

    /// 統計情報を表示
    pub fn dumpStats(self: *CustomArena) void {
        // TODO: 実装
        // - バッファ数
        // - 総容量
        // - 使用量
        // - 使用率
    }
};

テストコード:

test "CustomArena basic allocation" {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();

    var arena = CustomArena.init(gpa.allocator());
    defer arena.deinit();

    const allocator = arena.allocator();

    // 様々なサイズの割り当て
    const small = try allocator.alloc(u8, 10);
    const medium = try allocator.alloc(i32, 100);
    const large = try allocator.alloc(f64, 1000);

    try std.testing.expect(small.len == 10);
    try std.testing.expect(medium.len == 100);
    try std.testing.expect(large.len == 1000);

    arena.dumpStats();
}

test "CustomArena buffer growth" {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();

    var arena = CustomArena.init(gpa.allocator());
    defer arena.deinit();

    const allocator = arena.allocator();

    // 複数のバッファを必要とする大量の割り当て
    for (0..100) |_| {
        const data = try allocator.alloc(u8, 1024);
        _ = data;
    }

    // 統計を確認
    arena.dumpStats();
    try std.testing.expect(arena.total_allocated > 100 * 1024);
}

Part 2: ダブルバッファリングArena (25点)

ゲームエンジン向けのダブルバッファリングArenaを実装してください。

要件:

pub const DoubleBufferedArena = struct {
    buffers: [2]std.heap.ArenaAllocator,
    current_index: usize,
    frame_count: usize,

    pub fn init(base_allocator: std.mem.Allocator) DoubleBufferedArena {
        // TODO: 実装
    }

    pub fn deinit(self: *DoubleBufferedArena) void {
        // TODO: 実装
    }

    /// 現在のフレームのアロケータ
    pub fn current(self: *DoubleBufferedArena) std.mem.Allocator {
        // TODO: 実装
    }

    /// 前フレームのアロケータ（読み取り専用）
    pub fn previous(self: *DoubleBufferedArena) std.mem.Allocator {
        // TODO: 実装
    }

    /// バッファを切り替え
    pub fn swap(self: *DoubleBufferedArena) void {
        // TODO: 実装
        // 1. フレームカウントを更新
        // 2. 次のバッファをリセット
        // 3. インデックスを切り替え
    }

    /// 現在のフレーム番号
    pub fn currentFrame(self: *DoubleBufferedArena) usize {
        return self.frame_count;
    }
};

シミュレーションコード:

const RenderCommand = struct {
    position: [3]f32,
    color: [4]f32,
    vertex_count: usize,
};

fn simulateGameLoop() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();

    var double_arena = DoubleBufferedArena.init(gpa.allocator());
    defer double_arena.deinit();

    for (0..60) |_| {
        const current_alloc = double_arena.current();
        const previous_alloc = double_arena.previous();

        // 新しいフレームのコマンドを構築
        var commands = std.ArrayList(RenderCommand).init(current_alloc);

        for (0..100) |i| {
            try commands.append(.{
                .position = .{ @floatFromInt(i), 0, 0 },
                .color = .{ 1, 1, 1, 1 },
                .vertex_count = 3,
            });
        }

        // 前フレームのデータはまだ有効（GPUがレンダリング中）
        // ここでprevious_allocのデータを読み取れる
        _ = previous_alloc;

        std.debug.print("Frame {}: {} commands\n", .{
            double_arena.currentFrame(),
            commands.items.len,
        });

        // フレーム切り替え
        double_arena.swap();
    }
}

test "DoubleBufferedArena simulation" {
    try simulateGameLoop();
}

Part 3: 階層的Arenaシステム (25点)

複雑なアプリケーション向けの階層的メモリ管理システムを実装してください。

要件:

pub const HierarchicalArena = struct {
    pub const Lifetime = enum {
        permanent,  // プログラム全体
        level,      // レベル/シーン
        frame,      // フレーム
        temp,       // 一時
    };

    base_allocator: std.mem.Allocator,
    permanent_arena: std.heap.ArenaAllocator,
    level_arena: std.heap.ArenaAllocator,
    frame_arena: std.heap.ArenaAllocator,
    temp_buffer: [64 * 1024]u8,
    temp_fba: std.heap.FixedBufferAllocator,

    // 統計
    stats: struct {
        permanent_bytes: usize,
        level_bytes: usize,
        frame_bytes: usize,
        temp_bytes: usize,
    },

    pub fn init(base_allocator: std.mem.Allocator) HierarchicalArena {
        // TODO: 実装
    }

    pub fn deinit(self: *HierarchicalArena) void {
        // TODO: 実装
    }

    /// ライフタイムに応じたアロケータを取得
    pub fn getAllocator(
        self: *HierarchicalArena,
        lifetime: Lifetime,
    ) std.mem.Allocator {
        // TODO: 実装
    }

    /// レベルロード
    pub fn loadLevel(self: *HierarchicalArena) void {
        // TODO: 実装
        // level_arenaをリセット
    }

    /// フレーム開始
    pub fn beginFrame(self: *HierarchicalArena) void {
        // TODO: 実装
        // frame_arenaとtemp_fbaをリセット
    }

    /// 統計情報を表示
    pub fn dumpStats(self: *HierarchicalArena) void {
        // TODO: 実装
        // 各階層のメモリ使用量を表示
    }

    /// メモリ使用量を更新（内部用）
    fn updateStats(self: *HierarchicalArena) void {
        // TODO: 実装
        // 各Arenaの使用量を統計に反映
    }
};

シミュレーションコード:

const GameEntity = struct {
    name: []const u8,
    position: [3]f32,
    health: f32,
};

fn simulateGame() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();

    var hierarchy = HierarchicalArena.init(gpa.allocator());
    defer hierarchy.deinit();

    // 永続データ（ゲーム設定）
    const config = try hierarchy.getAllocator(.permanent).create(struct {
        title: []const u8 = "My Game",
        version: []const u8 = "1.0.0",
    });
    std.debug.print("Game: {s} v{s}\n", .{ config.title, config.version });

    // レベルロード
    hierarchy.loadLevel();
    const level_alloc = hierarchy.getAllocator(.level);

    var entities = std.ArrayList(GameEntity).init(level_alloc);
    for (0..100) |i| {
        try entities.append(.{
            .name = try std.fmt.allocPrint(
                level_alloc,
                "Entity{}",
                .{i},
            ),
            .position = .{ 0, 0, 0 },
            .health = 100,
        });
    }

    std.debug.print("Loaded level with {} entities\n", .{entities.items.len});

    // ゲームループ
    for (0..10) |frame| {
        hierarchy.beginFrame();

        const frame_alloc = hierarchy.getAllocator(.frame);
        const temp_alloc = hierarchy.getAllocator(.temp);

        // フレーム内の処理
        const render_list = try frame_alloc.alloc(*GameEntity, entities.items.len);
        for (entities.items, 0..) |*entity, i| {
            render_list[i] = entity;
        }

        // 一時バッファ
        const temp_buffer = try temp_alloc.alloc(u8, 1024);
        _ = temp_buffer;

        if (frame % 5 == 0) {
            hierarchy.dumpStats();
        }
    }

    // 最終統計
    std.debug.print("\nFinal Stats:\n", .{});
    hierarchy.dumpStats();
}

test "HierarchicalArena simulation" {
    try simulateGame();
}

ボーナス課題 (20点)

Bonus 1: メモリ使用量の可視化 (10点)

Arenaアロケータのメモリ使用状況をグラフィカルに表示する機能を実装してください。

要件:

pub const ArenaVisualizer = struct {
    arena: *CustomArena,

    pub fn init(arena: *CustomArena) ArenaVisualizer {
        return .{ .arena = arena };
    }

    /// ASCIIアートでメモリレイアウトを表示
    pub fn visualize(self: *ArenaVisualizer) void {
        // TODO: 実装
        // 各バッファの使用状況をバーグラフで表示
        //
        // 例:
        // Buffer 0 [████████░░] 80% (3276/4096 bytes)
        // Buffer 1 [██████░░░░] 60% (4915/8192 bytes)
        // Buffer 2 [███░░░░░░░] 30% (4915/16384 bytes)
    }

    /// メモリマップを表示
    pub fn dumpMemoryMap(self: *ArenaVisualizer) void {
        // TODO: 実装
        // 各割り当てのアドレスとサイズを表示
    }
};

Bonus 2: リセット戦略の実装 (10点)

複数のリセット戦略をサポートするArenaを実装してください。

要件:

pub const ResetStrategy = enum {
    /// 全てのメモリを解放
    free_all,

    /// 容量を保持してリセット
    retain_capacity,

    /// 最初のバッファのみ保持
    retain_first,

    /// 指定サイズまで保持
    retain_size,
};

pub const FlexibleArena = struct {
    arena: CustomArena,

    pub fn init(base_allocator: std.mem.Allocator) FlexibleArena {
        // TODO: 実装
    }

    pub fn deinit(self: *FlexibleArena) void {
        // TODO: 実装
    }

    /// 指定された戦略でリセット
    pub fn reset(
        self: *FlexibleArena,
        strategy: ResetStrategy,
        retain_bytes: ?usize,
    ) void {
        // TODO: 実装
        // 戦略に応じたリセット処理
    }

    pub fn allocator(self: *FlexibleArena) std.mem.Allocator {
        return self.arena.allocator();
    }
};

テストコード:

test "FlexibleArena reset strategies" {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();

    var arena = FlexibleArena.init(gpa.allocator());
    defer arena.deinit();

    const allocator = arena.allocator();

    // 大量の割り当て
    for (0..100) |_| {
        _ = try allocator.alloc(u8, 1024);
    }

    // 戦略1: 全解放
    arena.reset(.free_all, null);

    // 戦略2: 容量保持
    for (0..100) |_| {
        _ = try allocator.alloc(u8, 1024);
    }
    arena.reset(.retain_capacity, null);

    // 戦略3: 指定サイズまで保持
    for (0..100) |_| {
        _ = try allocator.alloc(u8, 1024);
    }
    arena.reset(.retain_size, 8192);
}

評価基準

項目	配点
Part 1: CustomArena実装	30点
Part 2: DoubleBufferedArena	25点
Part 3: HierarchicalArena	25点
マンダトリー合計	80点
Bonus 1: メモリ可視化	10点
Bonus 2: リセット戦略	10点
ボーナス合計	20点

採点詳細

CustomArena (30点):

正しいalloc実装 (10点)
バッファ成長戦略 (8点)
リンクリスト管理 (7点)
統計機能 (5点)

DoubleBufferedArena (25点):

バッファ切り替え (10点)
前フレームアクセス (8点)
メモリリークなし (7点)

HierarchicalArena (25点):

4階層の管理 (10点)
ライフタイム制御 (8点)
統計追跡 (7点)

合格基準

マンダトリー: 64点以上（80%）で合格
ボーナス: 優秀な実装に対する追加評価

提出方法

exercise02/
├── custom_arena.zig
├── double_buffered.zig
├── hierarchical.zig
├── tests.zig
├── bonus1_visualizer.zig   (オプション)
└── bonus2_strategies.zig   (オプション)

テスト実行:

zig test exercise02/tests.zig

ヒント

CustomArena実装

// BufferNodeのメモリレイアウト
// [BufferNode構造体][実際のバッファデータ...]
//  ^ptr            ^ptr + @sizeOf(BufferNode)

fn buffer(self: *BufferNode) []u8 {
    const node_size = @sizeOf(BufferNode);
    const ptr = @as([*]u8, @ptrCast(self)) + node_size;
    return ptr[0..self.capacity];
}

// バッファの確保
fn createBuffer(self: *CustomArena, min_size: usize) !*BufferNode {
    const node_size = @sizeOf(BufferNode);
    const total_size = node_size + min_size;

    const memory = try self.parent_allocator.alloc(u8, total_size);
    const node = @as(*BufferNode, @ptrCast(@alignCast(memory.ptr)));

    node.* = .{
        .next = null,
        .capacity = min_size,
        .used = 0,
    };

    return node;
}

バッファ成長戦略

fn nextBufferSize(current: usize) usize {
    if (current == 0) return INITIAL_SIZE;
    const next = current * GROWTH_FACTOR;
    return @min(next, MAX_BUFFER_SIZE);
}

アライメント処理

const alignment = @as(usize, 1) << @as(u6, @intCast(ptr_align));
const aligned_index = std.mem.alignForward(usize, node.used, alignment);

if (aligned_index + len > node.capacity) {
    return null;  // 容量不足
}

ダブルバッファリング

pub fn swap(self: *DoubleBufferedArena) void {
    self.frame_count += 1;
    const next_index = (self.current_index + 1) % 2;
    _ = self.buffers[next_index].reset(.retain_capacity);
    self.current_index = next_index;
}

デバッグのコツ

メモリリーク検出:

var gpa = std.heap.GeneralPurposeAllocator(.{
    .safety = true,
    .verbose_log = true,
}){};
defer {
    const leaked = gpa.deinit();
    if (leaked == .leak) {
        std.debug.print("MEMORY LEAK DETECTED!\n", .{});
    }
}

バッファ走査のデバッグ:

pub fn debugDumpBuffers(self: *CustomArena) void {
    std.debug.print("=== Arena Buffers ===\n", .{});
    var node = self.first_node;
    var i: usize = 0;
    while (node) |n| : (i += 1) {
        std.debug.print("  Buffer {}: {}KB used / {}KB capacity\n", .{
            i,
            n.used / 1024,
            n.capacity / 1024,
        });
        node = n.next;
    }
}

アライメント検証:

fn verifyAlignment(ptr: [*]u8, alignment: usize) void {
    const addr = @intFromPtr(ptr);
    if (addr % alignment != 0) {
        std.debug.panic("Alignment violation: 0x{x} not aligned to {}\n", .{
            addr,
            alignment,
        });
    }
}

パフォーマンス目標

実装がこれらの基準を満たすことを目指してください:

ベンチマーク: 10,000回の小さい割り当て（100バイト）

目標:
  CustomArena:        < 1ms
  DoubleBuffered:     < 1.2ms
  Hierarchical:       < 1.5ms

メモリ効率:
  オーバーヘッド: < 5%
  フラグメンテーション: < 10%

参考資料

Zig Standard Library - ArenaAllocator: https://github.com/ziglang/zig/blob/master/lib/std/heap/arena_allocator.zig
Memory Allocation Strategies: https://www.gingerbill.org/series/memory-allocation-strategies/
Game Engine Architecture: https://www.gameenginebook.com/
Real-Time Rendering: https://www.realtimerendering.com/