Chapter 3: Poolアロケータの設計と実装

3.1 Poolアロケータとは

オブジェクトプールパターン

Poolアロケータは、固定サイズのオブジェクトを効率的に管理するためのパターンです。

従来のアロケータ:
  create(Player)   → malloc(sizeof(Player))
  destroy(Player)  → free(ptr)
  create(Player)   → malloc(sizeof(Player))  ← 再度システムコール

Poolアロケータ:
  create(Player)   → プールから取得（超高速）
  destroy(Player)  → プールに返却
  create(Player)   → プールから再利用（システムコール不要）

なぜPoolが必要なのか

問題: 同じサイズのオブジェクトの頻繁な作成・削除

例1: ゲームエンジン
  - 敵キャラクター: 毎フレーム数百体生成・破棄
  - パーティクル: 毎フレーム数千個生成・破棄
  - 弾丸: 毎フレーム数十発生成・破棄

例2: ネットワークサーバー
  - パケットバッファ: 毎秒数万パケット処理
  - セッション: 頻繁な接続・切断

例3: データベース
  - ノード: B+ツリーの頻繁な挿入・削除
  - レコード: トランザクション内の一時データ

パフォーマンス比較:

const std = @import("std");

// 従来のアロケータ
fn benchmarkGeneral() !u64 {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var timer = try std.time.Timer.start();

    for (0..10000) |_| {
        const obj = try allocator.create(struct { x: i32, y: i32 });
        allocator.destroy(obj);
    }

    return timer.read();
}

// Poolアロケータ
fn benchmarkPool() !u64 {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();

    var pool = std.heap.MemoryPool(struct { x: i32, y: i32 }).init(gpa.allocator());
    defer pool.deinit();

    var timer = try std.time.Timer.start();

    for (0..10000) |_| {
        const obj = try pool.create();
        pool.destroy(obj);
    }

    return timer.read();
}

// 結果:
// General: 2,500,000 ns
// Pool:      250,000 ns
// Speedup: 10x

3.2 Poolアロケータの内部構造

フリーリストの実装

Poolアロケータの核心はフリーリストです:

初期状態（3つのオブジェクト）:

free_list → [Node1] → [Node2] → [Node3] → null
             ↓         ↓         ↓
           [Data1]   [Data2]   [Data3]

割り当て (create):
  1. free_listの先頭を取得
  2. free_listを次に進める

free_list → [Node2] → [Node3] → null
  返却: [Node1/Data1]

解放 (destroy):
  1. オブジェクトをfree_listの先頭に追加

free_list → [Node1] → [Node2] → [Node3] → null

メモリレイアウト

シンプルな実装:

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

    free_list: ?*Node,
    blocks: [][]Node,
};

メモリレイアウト:
+------------------+
| Node             |
| - next: *Node    | ← フリーリストのリンク
| - data: T        | ← 実際のデータ
+------------------+

最適化版（Intrusive List）:
+------------------+
| T                |  ← データ構造そのもの
| （最初の8バイト） |  ← 未使用時にnextポインタとして使用
+------------------+

利点:
  - メタデータのオーバーヘッドがゼロ
  - キャッシュ効率が良い

3.3 基本的な実装

シンプルなPoolアロケータ

const std = @import("std");

pub fn Pool(comptime T: type) type {
    return struct {
        const Self = @This();

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

        parent_allocator: std.mem.Allocator,
        free_list: ?*Node,
        all_nodes: std.ArrayList(*Node),

        pub fn init(allocator: std.mem.Allocator) Self {
            return .{
                .parent_allocator = allocator,
                .free_list = null,
                .all_nodes = std.ArrayList(*Node).init(allocator),
            };
        }

        pub fn deinit(self: *Self) void {
            // 全てのノードを解放
            for (self.all_nodes.items) |node| {
                self.parent_allocator.destroy(node);
            }
            self.all_nodes.deinit();
        }

        pub fn create(self: *Self) !*T {
            // フリーリストから取得
            if (self.free_list) |node| {
                self.free_list = node.next;
                return &node.data;
            }

            // 新しいノードを確保
            const node = try self.parent_allocator.create(Node);
            try self.all_nodes.append(node);
            return &node.data;
        }

        pub fn destroy(self: *Self, obj: *T) void {
            // ノードのアドレスを計算
            const node = @as(
                *Node,
                @ptrFromInt(@intFromPtr(obj) - @offsetOf(Node, "data")),
            );

            // フリーリストに返却
            node.next = self.free_list;
            self.free_list = node;
        }
    };
}

使用例:

const std = @import("std");

const Enemy = struct {
    x: f32,
    y: f32,
    health: f32,
    type: enum { goblin, orc, dragon },

    pub fn init(x: f32, y: f32, enemy_type: @TypeOf(@as(Enemy, undefined).type)) Enemy {
        return .{
            .x = x,
            .y = y,
            .health = 100.0,
            .type = enemy_type,
        };
    }

    pub fn update(self: *Enemy, dt: f32) void {
        self.x += 10 * dt;
    }
};

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

    var enemy_pool = Pool(Enemy).init(gpa.allocator());
    defer enemy_pool.deinit();

    var enemies = std.ArrayList(*Enemy).init(gpa.allocator());
    defer enemies.deinit();

    // 敵を生成
    for (0..100) |i| {
        const enemy = try enemy_pool.create();
        enemy.* = Enemy.init(
            @floatFromInt(i * 10),
            0,
            .goblin,
        );
        try enemies.append(enemy);
    }

    // ゲームループ
    for (0..60) |frame| {
        // 更新
        for (enemies.items) |enemy| {
            enemy.update(1.0 / 60.0);
        }

        // 敵を破棄
        if (frame % 10 == 0 and enemies.items.len > 0) {
            const enemy = enemies.pop();
            enemy_pool.destroy(enemy);
        }

        // 新しい敵を生成
        if (frame % 5 == 0) {
            const enemy = try enemy_pool.create();
            enemy.* = Enemy.init(@floatFromInt(frame), 0, .orc);
            try enemies.append(enemy);
        }
    }

    // 残りの敵を解放
    for (enemies.items) |enemy| {
        enemy_pool.destroy(enemy);
    }
}

3.4 最適化されたPool実装

ブロックベースの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,
        free_list: ?*Node,
        blocks: std.ArrayList([]Node),

        pub fn init(allocator: std.mem.Allocator) Self {
            return .{
                .parent_allocator = allocator,
                .free_list = null,
                .blocks = std.ArrayList([]Node).init(allocator),
            };
        }

        pub fn deinit(self: *Self) void {
            for (self.blocks.items) |block| {
                self.parent_allocator.free(block);
            }
            self.blocks.deinit();
        }

        fn allocateBlock(self: *Self) !void {
            // block_size個のノードを一度に確保
            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;
            }
        }

        pub fn create(self: *Self) !*T {
            // フリーリストが空なら新しいブロックを確保
            if (self.free_list == null) {
                try self.allocateBlock();
            }

            const node = self.free_list.?;
            self.free_list = node.next;
            return &node.data;
        }

        pub fn destroy(self: *Self, obj: *T) void {
            const node = @as(
                *Node,
                @ptrFromInt(@intFromPtr(obj) - @offsetOf(Node, "data")),
            );

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

        /// 統計情報
        pub fn stats(self: *Self) struct {
            blocks: usize,
            capacity: usize,
            allocated_bytes: usize,
        } {
            return .{
                .blocks = self.blocks.items.len,
                .capacity = self.blocks.items.len * block_size,
                .allocated_bytes = self.blocks.items.len * block_size * @sizeOf(Node),
            };
        }
    };
}

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

    // 64個ずつブロック確保
    var pool = BlockPool(struct { x: i32, y: i32 }, 64).init(gpa.allocator());
    defer pool.deinit();

    // 大量のオブジェクトを作成
    var objects: [1000]*@TypeOf(pool).T = undefined;
    for (&objects) |*obj| {
        obj.* = try pool.create();
        obj.*.* = .{ .x = 10, .y = 20 };
    }

    const info = pool.stats();
    std.debug.print("Blocks: {}\n", .{info.blocks});
    std.debug.print("Capacity: {}\n", .{info.capacity});
    std.debug.print("Memory: {} KB\n", .{info.allocated_bytes / 1024});

    // 解放
    for (objects) |obj| {
        pool.destroy(obj);
    }
}

出力:

Blocks: 16
Capacity: 1024
Memory: 16 KB

Intrusive Pool (メタデータゼロ)

最も効率的な実装:

const std = @import("std");

/// IntrusivePool: データ構造そのものをフリーリストに使用
/// 制約: Tは少なくとも@sizeOf(usize)のサイズが必要
pub fn IntrusivePool(comptime T: type, comptime block_size: usize) type {
    // コンパイル時チェック
    if (@sizeOf(T) < @sizeOf(usize)) {
        @compileError("Type too small for intrusive pool");
    }

    return struct {
        const Self = @This();

        parent_allocator: std.mem.Allocator,
        free_list: ?*T,
        blocks: std.ArrayList([]T),

        pub fn init(allocator: std.mem.Allocator) Self {
            return .{
                .parent_allocator = allocator,
                .free_list = null,
                .blocks = std.ArrayList([]T).init(allocator),
            };
        }

        pub fn deinit(self: *Self) void {
            for (self.blocks.items) |block| {
                self.parent_allocator.free(block);
            }
            self.blocks.deinit();
        }

        fn allocateBlock(self: *Self) !void {
            const block = try self.parent_allocator.alloc(T, block_size);
            try self.blocks.append(block);

            // フリーリストに追加
            // Tの最初の8バイトを*Tとして解釈（intrusive）
            for (block) |*item| {
                const next_ptr = @as(*?*T, @ptrCast(@alignCast(item)));
                next_ptr.* = self.free_list;
                self.free_list = item;
            }
        }

        pub fn create(self: *Self) !*T {
            if (self.free_list == null) {
                try self.allocateBlock();
            }

            const item = self.free_list.?;
            const next_ptr = @as(*?*T, @ptrCast(@alignCast(item)));
            self.free_list = next_ptr.*;

            return item;
        }

        pub fn destroy(self: *Self, item: *T) void {
            const next_ptr = @as(*?*T, @ptrCast(@alignCast(item)));
            next_ptr.* = self.free_list;
            self.free_list = item;
        }
    };
}

3.5 高度なパターン

パターン1: 型消去Pool

複数の型を1つのPoolで管理:

const std = @import("std");

pub const TypeErasedPool = struct {
    const Block = struct {
        data: []u8,
        item_size: usize,
        free_list: ?[*]u8,
    };

    parent_allocator: std.mem.Allocator,
    blocks: std.StringHashMap(Block),

    pub fn init(allocator: std.mem.Allocator) TypeErasedPool {
        return .{
            .parent_allocator = allocator,
            .blocks = std.StringHashMap(Block).init(allocator),
        };
    }

    pub fn deinit(self: *TypeErasedPool) void {
        var it = self.blocks.iterator();
        while (it.next()) |entry| {
            self.parent_allocator.free(entry.value_ptr.data);
        }
        self.blocks.deinit();
    }

    pub fn create(self: *TypeErasedPool, comptime T: type) !*T {
        const type_name = @typeName(T);
        const item_size = @sizeOf(T);

        var block = self.blocks.get(type_name) orelse blk: {
            // 新しいブロックを作成
            const data = try self.parent_allocator.alloc(u8, item_size * 64);
            const new_block = Block{
                .data = data,
                .item_size = item_size,
                .free_list = data.ptr,
            };
            try self.blocks.put(type_name, new_block);
            break :blk new_block;
        };

        // フリーリストから取得
        const ptr = block.free_list orelse {
            return error.OutOfMemory;
        };

        // 次のポインタを取得
        const next_ptr = @as(*?[*]u8, @ptrCast(@alignCast(ptr)));
        block.free_list = next_ptr.*;

        try self.blocks.put(type_name, block);
        return @as(*T, @ptrCast(@alignCast(ptr)));
    }

    pub fn destroy(self: *TypeErasedPool, obj: anytype) void {
        const T = @TypeOf(obj.*);
        const type_name = @typeName(T);

        var block = self.blocks.get(type_name) orelse return;

        const ptr = @as([*]u8, @ptrCast(obj));
        const next_ptr = @as(*?[*]u8, @ptrCast(@alignCast(ptr)));
        next_ptr.* = block.free_list;
        block.free_list = ptr;

        self.blocks.put(type_name, block) catch {};
    }
};

パターン2: スレッドセーフPool

const std = @import("std");

pub fn ThreadSafePool(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,
        free_list: ?*Node,
        blocks: std.ArrayList([]Node),
        mutex: std.Thread.Mutex,

        pub fn init(allocator: std.mem.Allocator) Self {
            return .{
                .parent_allocator = allocator,
                .free_list = null,
                .blocks = std.ArrayList([]Node).init(allocator),
                .mutex = .{},
            };
        }

        pub fn deinit(self: *Self) void {
            self.mutex.lock();
            defer self.mutex.unlock();

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

        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;
            }
        }

        pub fn create(self: *Self) !*T {
            self.mutex.lock();
            defer self.mutex.unlock();

            if (self.free_list == null) {
                try self.allocateBlock();
            }

            const node = self.free_list.?;
            self.free_list = node.next;
            return &node.data;
        }

        pub fn destroy(self: *Self, obj: *T) void {
            self.mutex.lock();
            defer self.mutex.unlock();

            const node = @as(
                *Node,
                @ptrFromInt(@intFromPtr(obj) - @offsetOf(Node, "data")),
            );

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

3.6 実世界の使用例

ゲームエンジン: パーティクルシステム

const std = @import("std");

const Particle = struct {
    position: [3]f32,
    velocity: [3]f32,
    color: [4]f32,
    lifetime: f32,
    age: f32,

    pub fn update(self: *Particle, dt: f32) bool {
        self.age += dt;
        if (self.age >= self.lifetime) {
            return false;  // パーティクル死亡
        }

        self.position[0] += self.velocity[0] * dt;
        self.position[1] += self.velocity[1] * dt;
        self.position[2] += self.velocity[2] * dt;

        return true;
    }
};

const ParticleSystem = struct {
    pool: BlockPool(Particle, 1024),
    active_particles: std.ArrayList(*Particle),

    pub fn init(allocator: std.mem.Allocator) !ParticleSystem {
        return .{
            .pool = BlockPool(Particle, 1024).init(allocator),
            .active_particles = std.ArrayList(*Particle).init(allocator),
        };
    }

    pub fn deinit(self: *ParticleSystem) void {
        self.active_particles.deinit();
        self.pool.deinit();
    }

    pub fn emit(self: *ParticleSystem, position: [3]f32) !void {
        const particle = try self.pool.create();
        particle.* = .{
            .position = position,
            .velocity = .{ 0, 10, 0 },
            .color = .{ 1, 1, 1, 1 },
            .lifetime = 2.0,
            .age = 0,
        };
        try self.active_particles.append(particle);
    }

    pub fn update(self: *ParticleSystem, dt: f32) !void {
        var i: usize = 0;
        while (i < self.active_particles.items.len) {
            const particle = self.active_particles.items[i];
            if (!particle.update(dt)) {
                // パーティクル死亡
                self.pool.destroy(particle);
                _ = self.active_particles.swapRemove(i);
            } else {
                i += 1;
            }
        }
    }
};

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

    var system = try ParticleSystem.init(gpa.allocator());
    defer system.deinit();

    // シミュレーション
    for (0..600) |frame| {
        // 毎フレーム10個のパーティクルを放出
        for (0..10) |_| {
            try system.emit(.{ 0, 0, 0 });
        }

        // 更新
        try system.update(1.0 / 60.0);

        if (frame % 60 == 0) {
            std.debug.print("Frame {}: {} active particles\n", .{
                frame,
                system.active_particles.items.len,
            });
        }
    }
}

ネットワークサーバー: パケットバッファ

const std = @import("std");

const PacketBuffer = struct {
    data: [1500]u8,  // MTUサイズ
    size: usize,
};

const NetworkServer = struct {
    packet_pool: BlockPool(PacketBuffer, 256),
    active_packets: std.ArrayList(*PacketBuffer),

    pub fn init(allocator: std.mem.Allocator) !NetworkServer {
        return .{
            .packet_pool = BlockPool(PacketBuffer, 256).init(allocator),
            .active_packets = std.ArrayList(*PacketBuffer).init(allocator),
        };
    }

    pub fn deinit(self: *NetworkServer) void {
        self.active_packets.deinit();
        self.packet_pool.deinit();
    }

    pub fn receivePacket(self: *NetworkServer, data: []const u8) !void {
        const packet = try self.packet_pool.create();
        packet.size = data.len;
        @memcpy(packet.data[0..data.len], data);
        try self.active_packets.append(packet);
    }

    pub fn processPackets(self: *NetworkServer) !void {
        for (self.active_packets.items) |packet| {
            // パケット処理
            _ = packet;
        }

        // 全てのパケットを解放
        for (self.active_packets.items) |packet| {
            self.packet_pool.destroy(packet);
        }
        self.active_packets.clearRetainingCapacity();
    }
};

3.7 まとめ

Poolアロケータの特性:

利点:
  ✓ 固定サイズの割り当てが超高速
  ✓ フラグメンテーションなし
  ✓ キャッシュ効率が良い
  ✓ メモリ使用量が予測可能
  ✓ オブジェクトの再利用

欠点:
  ✗ 固定サイズのみ対応
  ✗ 未使用メモリの保持
  ✗ 型ごとにPoolが必要

適用例:
  ✓ ゲームオブジェクト（敵、弾丸、パーティクル）
  ✓ ネットワークパケット
  ✓ データ構造のノード（リスト、ツリー）
  ✓ 一時オブジェクト

次の章では、これまで学んだアロケータパターンを組み合わせた高度なメモリ管理戦略について学びます。

参考資料

• Zig Standard Library - MemoryPool: https://ziglang.org/documentation/master/std/#A;std:heap.MemoryPool
• Object Pool Pattern: https://gameprogrammingpatterns.com/object-pool.html
• Slab Allocation: https://en.wikipedia.org/wiki/Slab_allocation
• Fast Efficient Fixed-Size Memory Pool: https://www.codeproject.com/Articles/27487/Why-to-use-memory-pool-and-how-to-implement-it