課題3: Poolアロケータの実装と最適化

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

Part 1: ブロックベースPool実装 (30点)

効率的なブロック管理を行うPoolアロケータを実装してください。

要件:

const std = @import("std");

pub fn BlockPool(comptime T: type, comptime block_size: usize) type {
    return struct {
        const Self = @This();

        const Node = struct {
            next: ?*Node,
            data: T,
        };

        parent_allocator: std.mem.Allocator,
        blocks: std.ArrayList([]Node),
        free_list: ?*Node,
        total_capacity: usize,
        allocated_count: usize,

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

        pub fn deinit(self: *Self) void {
            // TODO: 実装
            // - 全てのブロックを解放
            // - blocksリストを解放
        }

        fn allocateBlock(self: *Self) !void {
            // TODO: 実装
            // 1. block_size個のNodeを確保
            // 2. blocksリストに追加
            // 3. 各Nodeをfree_listに追加
            // 4. 統計を更新
        }

        pub fn create(self: *Self) !*T {
            // TODO: 実装
            // 1. free_listが空なら新しいブロックを確保
            // 2. free_listから1つ取得
            // 3. allocated_countを更新
            // 4. dataのポインタを返す
        }

        pub fn destroy(self: *Self, obj: *T) void {
            // TODO: 実装
            // 1. objからNodeのポインタを計算
            // 2. free_listに返却
            // 3. allocated_countを更新
        }

        /// 統計情報
        pub fn stats(self: *Self) Stats {
            return .{
                .blocks = self.blocks.items.len,
                .capacity = self.total_capacity,
                .allocated = self.allocated_count,
                .utilization = if (self.total_capacity > 0)
                    @as(f32, @floatFromInt(self.allocated_count)) /
                    @as(f32, @floatFromInt(self.total_capacity))
                else
                    0.0,
            };
        }

        pub const Stats = struct {
            blocks: usize,
            capacity: usize,
            allocated: usize,
            utilization: f32,
        };
    };
}

テストコード:

test "BlockPool basic operations" {
    const Point = struct { x: f32, y: f32, z: f32 };

    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();

    var pool = BlockPool(Point, 64).init(gpa.allocator());
    defer pool.deinit();

    // 大量の割り当て
    var points: [1000]*Point = undefined;
    for (&points) |*ptr| {
        ptr.* = try pool.create();
        ptr.*.* = .{ .x = 1.0, .y = 2.0, .z = 3.0 };
    }

    const info = pool.stats();
    try std.testing.expect(info.allocated == 1000);
    try std.testing.expect(info.blocks >= 16);  // 1000 / 64 = 16

    // 解放
    for (points) |ptr| {
        pool.destroy(ptr);
    }

    const info2 = pool.stats();
    try std.testing.expect(info2.allocated == 0);
}

test "BlockPool stress test" {
    const Data = struct { value: i32 };

    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();

    var pool = BlockPool(Data, 32).init(gpa.allocator());
    defer pool.deinit();

    // ランダムな割り当てと解放
    var prng = std.rand.DefaultPrng.init(0);
    const random = prng.random();

    var active = std.ArrayList(*Data).init(gpa.allocator());
    defer active.deinit();

    for (0..10000) |_| {
        if (random.boolean() or active.items.len == 0) {
            // 割り当て
            const data = try pool.create();
            data.value = random.int(i32);
            try active.append(data);
        } else {
            // 解放
            const idx = random.intRangeLessThan(usize, 0, active.items.len);
            pool.destroy(active.items[idx]);
            _ = active.swapRemove(idx);
        }
    }

    // クリーンアップ
    for (active.items) |data| {
        pool.destroy(data);
    }
}

Part 2: 固定容量Pool（組み込み向け） (25点)

ヒープ割り当てなしで動作する固定容量Poolを実装してください。

要件:

pub fn FixedCapacityPool(comptime T: type, comptime capacity: usize) type {
    return struct {
        const Self = @This();

        const Slot = struct {
            occupied: bool,
            data: T,
        };

        slots: [capacity]Slot,
        free_indices: [capacity]u32,
        free_count: usize,
        high_water_mark: usize,

        pub fn init() Self {
            var self: Self = .{
                .slots = undefined,
                .free_indices = undefined,
                .free_count = capacity,
                .high_water_mark = 0,
            };

            // TODO: 実装
            // - 全てのスロットをunoccupiedに設定
            // - free_indicesを0..capacityで初期化

            return self;
        }

        pub fn create(self: *Self) ?*T {
            // TODO: 実装
            // 1. free_countが0ならnullを返す
            // 2. free_indicesから1つ取得
            // 3. スロットをoccupiedに設定
            // 4. high_water_markを更新
            // 5. dataのポインタを返す
        }

        pub fn destroy(self: *Self, obj: *T) void {
            // TODO: 実装
            // 1. objからスロットインデックスを計算
            // 2. スロットをunoccupiedに設定
            // 3. free_indicesに返却
        }

        /// 使用可能な容量
        pub fn available(self: *Self) usize {
            return self.free_count;
        }

        /// ピーク使用量
        pub fn peakUsage(self: *Self) usize {
            return self.high_water_mark;
        }

        /// 使用率
        pub fn utilization(self: *Self) f32 {
            return @as(f32, @floatFromInt(capacity - self.free_count)) /
                   @as(f32, @floatFromInt(capacity));
        }
    };
}

テストコード:

test "FixedCapacityPool no heap allocation" {
    const Entity = struct {
        id: u32,
        position: [3]f32,
        health: f32,
    };

    // スタック上に配置（ヒープ不使用）
    var pool = FixedCapacityPool(Entity, 100).init();

    // 割り当て
    var entities: [50]*Entity = undefined;
    for (&entities, 0..) |*ptr, i| {
        ptr.* = pool.create() orelse return error.OutOfMemory;
        ptr.*.* = .{
            .id = @intCast(i),
            .position = .{ 0, 0, 0 },
            .health = 100,
        };
    }

    try std.testing.expect(pool.available() == 50);
    try std.testing.expect(pool.peakUsage() == 50);

    // 解放
    for (entities) |entity| {
        pool.destroy(entity);
    }

    try std.testing.expect(pool.available() == 100);
}

test "FixedCapacityPool capacity limit" {
    const Data = struct { value: i32 };
    var pool = FixedCapacityPool(Data, 10).init();

    // 容量いっぱいまで割り当て
    var items: [10]*Data = undefined;
    for (&items) |*item| {
        item.* = pool.create() orelse return error.OutOfMemory;
    }

    // 11個目はnull
    const overflow = pool.create();
    try std.testing.expect(overflow == null);

    // 1つ解放してから再割り当て
    pool.destroy(items[0]);
    const new_item = pool.create();
    try std.testing.expect(new_item != null);
}

Part 3: Slabアロケータ実装 (25点)

複数のサイズクラスをサポートするSlabアロケータを実装してください。

要件:

pub const SlabAllocator = struct {
    const SIZE_CLASSES = [_]usize{
        16, 32, 64, 128, 256, 512, 1024, 2048,
    };

    const Slab = struct {
        const Node = struct {
            next: ?*Node,
        };

        block: []u8,
        item_size: usize,
        capacity: usize,
        free_list: ?*Node,
        allocated: usize,

        fn init(allocator: std.mem.Allocator, item_size: usize, capacity: usize) !Slab {
            // TODO: 実装
            // 1. block = item_size * capacity のメモリを確保
            // 2. フリーリストを構築
        }

        fn deinit(self: *Slab, allocator: std.mem.Allocator) void {
            // TODO: 実装
        }

        fn alloc(self: *Slab) ?[*]u8 {
            // TODO: 実装
        }

        fn free(self: *Slab, ptr: [*]u8) void {
            // TODO: 実装
        }
    };

    parent_allocator: std.mem.Allocator,
    slabs: [SIZE_CLASSES.len]std.ArrayList(Slab),

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

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

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

    fn sizeClassIndex(size: usize) ?usize {
        // TODO: 実装
        // サイズに適したクラスのインデックスを返す
    }

    fn alloc(
        ctx: *anyopaque,
        len: usize,
        ptr_align: u8,
        ret_addr: usize,
    ) ?[*]u8 {
        // TODO: 実装
        // 1. サイズクラスを決定
        // 2. 既存のスラブから割り当てを試みる
        // 3. 失敗したら新しいスラブを作成
        // 4. 大きすぎる場合は親アロケータに委譲
    }

    fn resize(
        ctx: *anyopaque,
        buf: []u8,
        buf_align: u8,
        new_len: usize,
        ret_addr: usize,
    ) bool {
        return false;
    }

    fn free(
        ctx: *anyopaque,
        buf: []u8,
        buf_align: u8,
        ret_addr: usize,
    ) void {
        // TODO: 実装
        // 1. サイズクラスを決定
        // 2. 該当するスラブを検索
        // 3. スラブのfreeを呼び出す
    }

    /// 統計情報を表示
    pub fn dumpStats(self: *SlabAllocator) void {
        // TODO: 実装
        // 各サイズクラスの使用状況を表示
    }
};

テストコード:

test "SlabAllocator multiple sizes" {
    var slab = SlabAllocator.init(std.testing.allocator);
    defer slab.deinit();

    const allocator = slab.allocator();

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

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

    allocator.free(small);
    allocator.free(medium);
    allocator.free(large);
}

test "SlabAllocator stress test" {
    var slab = SlabAllocator.init(std.testing.allocator);
    defer slab.deinit();

    const allocator = slab.allocator();

    var allocations = std.ArrayList([]u8).init(std.testing.allocator);
    defer allocations.deinit();

    // 大量の割り当て
    for (0..1000) |i| {
        const size = (i % 500) + 10;  // 10-509バイト
        const buf = try allocator.alloc(u8, size);
        try allocations.append(buf);
    }

    // 統計表示
    slab.dumpStats();

    // 解放
    for (allocations.items) |buf| {
        allocator.free(buf);
    }
}

ボーナス課題 (20点)

Bonus 1: 世代別Pool（Use-After-Free検出） (10点)

世代管理によりuse-after-freeを検出するPoolを実装してください。

要件:

pub fn GenerationalPool(comptime T: type, comptime capacity: usize) type {
    return struct {
        const Self = @This();

        pub const Handle = struct {
            index: u32,
            generation: u32,

            pub fn isValid(self: Handle) bool {
                return self.index < capacity;
            }
        };

        const Slot = struct {
            generation: u32,
            data: T,
            occupied: bool,
        };

        slots: [capacity]Slot,
        free_list: std.ArrayList(u32),
        allocator: std.mem.Allocator,

        pub fn init(allocator: std.mem.Allocator) !Self {
            // TODO: 実装
            // - 全てのスロットを初期化
            // - free_listを0..capacityで初期化
        }

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

        pub fn create(self: *Self) !Handle {
            // TODO: 実装
            // 1. free_listから取得
            // 2. スロットをoccupiedに設定
            // 3. ハンドルを返す（インデックス + 世代）
        }

        pub fn get(self: *Self, handle: Handle) ?*T {
            // TODO: 実装
            // 1. インデックスの範囲チェック
            // 2. 世代の一致チェック
            // 3. occupiedチェック
            // 4. 全てOKならdataのポインタを返す
        }

        pub fn destroy(self: *Self, handle: Handle) !void {
            // TODO: 実装
            // 1. インデックスと世代をチェック
            // 2. スロットをunoccupiedに設定
            // 3. 世代を進める
            // 4. free_listに返却
        }
    };
}

テストコード:

test "GenerationalPool use-after-free detection" {
    const Entity = struct {
        name: []const u8,
        health: f32,
    };

    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();

    var pool = try GenerationalPool(Entity, 100).init(gpa.allocator());
    defer pool.deinit();

    // エンティティ作成
    const handle = try pool.create();
    const entity = pool.get(handle).?;
    entity.* = .{ .name = "Player", .health = 100 };

    // 削除
    try pool.destroy(handle);

    // 古いハンドルでアクセス（検出される）
    const invalid = pool.get(handle);
    try std.testing.expect(invalid == null);

    // 新しいハンドルでアクセス（OK）
    const handle2 = try pool.create();
    const entity2 = pool.get(handle2).?;
    entity2.* = .{ .name = "Enemy", .health = 50 };
}

Bonus 2: データ指向Pool（SoA） (10点)

Structure of Arrays方式でキャッシュ効率を最大化するPoolを実装してください。

要件:

pub const EntityPool = struct {
    const MAX_ENTITIES = 10000;

    // SoA (Structure of Arrays)
    ids: [MAX_ENTITIES]u32,
    positions: [MAX_ENTITIES][3]f32,
    velocities: [MAX_ENTITIES][3]f32,
    healths: [MAX_ENTITIES]f32,
    free_indices: std.ArrayList(u32),
    count: usize,
    allocator: std.mem.Allocator,

    pub fn init(allocator: std.mem.Allocator) !EntityPool {
        // TODO: 実装
    }

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

    pub fn create(
        self: *EntityPool,
        position: [3]f32,
        velocity: [3]f32,
        health: f32,
    ) !u32 {
        // TODO: 実装
        // 1. free_indicesまたはcountから新しいインデックスを取得
        // 2. 各配列に値を設定
        // 3. インデックスを返す
    }

    pub fn destroy(self: *EntityPool, index: u32) void {
        // TODO: 実装
        // free_indicesに返却
    }

    /// 位置更新（SIMD最適化可能）
    pub fn updatePositions(self: *EntityPool, dt: f32) void {
        // TODO: 実装
        // 全エンティティの位置を速度で更新
        // 連続メモリアクセスによりキャッシュ効率最大化
    }

    /// 距離計算（ベクトル化可能）
    pub fn distanceFrom(
        self: *EntityPool,
        index: u32,
        point: [3]f32,
    ) f32 {
        // TODO: 実装
    }
};

ベンチマーク:

test "EntityPool cache efficiency benchmark" {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();

    var pool = try EntityPool.init(gpa.allocator());
    defer pool.deinit();

    // 10,000エンティティを作成
    for (0..10000) |i| {
        _ = try pool.create(
            .{ @floatFromInt(i), 0, 0 },
            .{ 1, 1, 1 },
            100,
        );
    }

    // ベンチマーク
    var timer = try std.time.Timer.start();

    for (0..1000) |_| {
        pool.updatePositions(0.016);
    }

    const elapsed = timer.read();
    std.debug.print("EntityPool update: {} ns\n", .{elapsed});
    std.debug.print("Per entity: {} ns\n", .{elapsed / 10000000});
}

評価基準

採点詳細

BlockPool (30点):

• 正しいalloc/free実装 (12点)
• ブロック管理 (10点)
• 統計機能 (5点)
• メモリリークなし (3点)

FixedCapacityPool (25点):

• ヒープ不使用 (10点)
• 正しい容量管理 (8点)
• 統計機能 (7点)

SlabAllocator (25点):

• サイズクラス管理 (10点)
• Allocatorインターフェース (8点)
• パフォーマンス (7点)

合格基準

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

提出方法

exercise03/
├── block_pool.zig
├── fixed_pool.zig
├── slab_allocator.zig
├── tests.zig
├── bonus1_generational.zig  (オプション)
└── bonus2_soa.zig           (オプション)

テスト実行:

zig test exercise03/tests.zig

ヒント

BlockPoolの実装

// Nodeからdataポインタへの変換
fn nodeToData(node: *Node) *T {
    return &node.data;
}

// dataポインタからNodeへの変換
fn dataToNode(data: *T) *Node {
    return @as(*Node, @ptrFromInt(
        @intFromPtr(data) - @offsetOf(Node, "data")
    ));
}

// ブロック確保
fn allocateBlock(self: *Self) !void {
    const block = try self.parent_allocator.alloc(Node, block_size);
    try self.blocks.append(block);

    // フリーリストに追加（逆順で追加するとキャッシュ効率が良い）
    for (block) |*node| {
        node.next = self.free_list;
        self.free_list = node;
    }

    self.total_capacity += block_size;
}

FixedCapacityPoolの実装

// スロットインデックスの計算
fn getSlotIndex(self: *Self, data: *T) usize {
    const base = @intFromPtr(&self.slots[0].data);
    const ptr = @intFromPtr(data);
    const offset = ptr - base;
    const slot_size = @sizeOf(Slot);
    return offset / slot_size;
}

// 初期化
pub fn init() Self {
    var self: Self = undefined;
    self.free_count = capacity;
    self.high_water_mark = 0;

    for (&self.slots) |*slot| {
        slot.occupied = false;
    }

    for (&self.free_indices, 0..) |*idx, i| {
        idx.* = @intCast(i);
    }

    return self;
}

Slabアロケータの実装

// サイズクラスの検索
fn sizeClassIndex(size: usize) ?usize {
    for (SIZE_CLASSES, 0..) |class_size, i| {
        if (size <= class_size) return i;
    }
    return null;
}

// スラブの検索
fn findSlab(self: *SlabAllocator, ptr: [*]u8, size_class: usize) ?*Slab {
    const slab_list = &self.slabs[size_class];
    const addr = @intFromPtr(ptr);

    for (slab_list.items) |*slab| {
        const block_start = @intFromPtr(slab.block.ptr);
        const block_end = block_start + slab.block.len;

        if (addr >= block_start and addr < block_end) {
            return slab;
        }
    }

    return null;
}

世代別Poolの実装

pub fn destroy(self: *Self, handle: Handle) !void {
    if (handle.index >= capacity) return error.InvalidHandle;

    const slot = &self.slots[handle.index];

    // 世代チェック
    if (slot.generation != handle.generation) {
        return error.InvalidGeneration;
    }

    if (!slot.occupied) {
        return error.DoubleFree;
    }

    // 世代を進める（オーバーフロー対応）
    slot.generation +%= 1;
    slot.occupied = false;

    try self.free_list.append(handle.index);
}

デバッグのコツ

• ダブルフリー検出:

fn destroy(self: *Self, obj: *T) void {
    const node = dataToNode(obj);

    // デバッグビルドでダブルフリーをチェック
    if (std.debug.runtime_safety) {
        var current = self.free_list;
        while (current) |n| : (current = n.next) {
            if (n == node) {
                @panic("Double free detected!");
            }
        }
    }

    node.next = self.free_list;
    self.free_list = node;
}

• 統計のダンプ:

pub fn debugDump(self: *BlockPool(T, block_size)) void {
    std.debug.print("=== BlockPool Debug Info ===\n", .{});
    std.debug.print("Type: {s}\n", .{@typeName(T)});
    std.debug.print("Block size: {}\n", .{block_size});
    std.debug.print("Blocks: {}\n", .{self.blocks.items.len});
    std.debug.print("Capacity: {}\n", .{self.total_capacity});
    std.debug.print("Allocated: {}\n", .{self.allocated_count});
    std.debug.print("Utilization: {d:.1}%\n", .{
        @as(f32, @floatFromInt(self.allocated_count)) /
        @as(f32, @floatFromInt(self.total_capacity)) * 100.0,
    });
}

• メモリリーク検出:

pub fn deinit(self: *Self) void {
    if (self.allocated_count > 0) {
        std.debug.print("WARNING: {} objects still allocated\n", .{
            self.allocated_count,
        });
    }

    for (self.blocks.items) |block| {
        self.parent_allocator.free(block);
    }
    self.blocks.deinit();
}

パフォーマンス目標

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

ベンチマーク: 10,000回の割り当て・解放

目標:
  BlockPool:           < 500μs
  FixedCapacityPool:   < 300μs
  SlabAllocator:       < 800μs

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

参考資料

• Zig Standard Library - MemoryPool: https://github.com/ziglang/zig/blob/master/lib/std/heap/memory_pool.zig
• Linux Kernel - Slab Allocator: https://www.kernel.org/doc/gorman/html/understand/understand011.html
• Object Pool Pattern: https://gameprogrammingpatterns.com/object-pool.html
• Data-Oriented Design: https://www.dataorienteddesign.com/dodbook/
• Fast Memory Allocation: https://www.codeproject.com/Articles/27487/