Chapter 1: アロケータの概念と設計
1.1 メモリアロケータの歴史
初期のメモリ管理
プログラミング言語におけるメモリ管理は、コンピュータサイエンスの歴史とともに進化してきました:
1950年代: 静的メモリ割り当て
- すべてのメモリがコンパイル時に決定
- 柔軟性なし
1960年代: malloc/free の登場 (FORTRAN, LISP)
- 動的メモリ割り当て
- 手動管理
1970年代: C言語のmalloc/free
- ヒープメモリの標準化
- バグの温床 (リーク、二重解放)
1980年代: ガベージコレクション
- Java, Smalltalk
- 自動メモリ管理
2000年代: 所有権システム
- Rust
- コンパイル時検証
2020年代: アロケータパターン
- Zig, Odin
- 明示的かつ柔軟
なぜアロケータパターンか
Zigは、アロケータを第一級オブジェクトとして扱います:
const std = @import("std");
pub fn main() !void {
// アロケータを選択
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
// 使用
const buffer = try allocator.alloc(u8, 1024);
defer allocator.free(buffer);
}
利点:
1. 柔軟性: 用途に応じてアロケータを選択
2. 明示性: メモリ割り当てが明確
3. 制御: 割り当て戦略をカスタマイズ可能
4. テスト: モックアロケータでテスト容易
1.2 Allocatorインターフェース
std.mem.Allocatorの構造
const std = @import("std");
// Allocatorインターフェース
pub const Allocator = struct {
ptr: *anyopaque,
vtable: *const VTable,
pub const VTable = struct {
alloc: *const fn(
ptr: *anyopaque,
len: usize,
ptr_align: u8,
ret_addr: usize,
) ?[*]u8,
resize: *const fn(
ptr: *anyopaque,
buf: []u8,
buf_align: u8,
new_len: usize,
ret_addr: usize,
) bool,
free: *const fn(
ptr: *anyopaque,
buf: []u8,
buf_align: u8,
ret_addr: usize,
) void,
};
// 便利なラッパー
pub fn alloc(self: Allocator, comptime T: type, n: usize) ![]T {
// ...
}
pub fn create(self: Allocator, comptime T: type) !*T {
// ...
}
pub fn free(self: Allocator, memory: anytype) void {
// ...
}
};
VTableパターン
Zigのアロケータは、VTableパターンで多態性を実現します:
+-------------------+
| Allocator |
+-------------------+
| ptr: *anyopaque | -----> 実際のアロケータインスタンス
| vtable: *VTable | -----> 関数ポインタテーブル
+-------------------+
VTable:
+-------------------+
| alloc: *fn | -----> 割り当て関数
| resize: *fn | -----> リサイズ関数
| free: *fn | -----> 解放関数
+-------------------+
1.3 基本的なアロケータの実装
シンプルなBumpAllocator
const std = @import("std");
/// Bump Allocator (線形アロケータ)
/// メモリを順番に割り当て、個別の解放はサポートしない
pub const BumpAllocator = struct {
buffer: []u8,
offset: usize,
pub fn init(buffer: []u8) BumpAllocator {
return .{
.buffer = buffer,
.offset = 0,
};
}
pub fn allocator(self: *BumpAllocator) std.mem.Allocator {
return .{
.ptr = self,
.vtable = &.{
.alloc = alloc,
.resize = resize,
.free = free,
},
};
}
fn alloc(
ctx: *anyopaque,
len: usize,
ptr_align: u8,
ret_addr: usize,
) ?[*]u8 {
_ = ret_addr;
const self: *BumpAllocator = @ptrCast(@alignCast(ctx));
// アライメント調整
const alignment = @as(usize, 1) << @as(std.math.Log2Int(usize), @intCast(ptr_align));
const aligned_offset = std.mem.alignForward(usize, self.offset, alignment);
// 容量チェック
const end = aligned_offset + len;
if (end > self.buffer.len) {
return null; // Out of memory
}
self.offset = end;
return self.buffer[aligned_offset..end].ptr;
}
fn resize(
ctx: *anyopaque,
buf: []u8,
buf_align: u8,
new_len: usize,
ret_addr: usize,
) bool {
_ = ctx;
_ = buf;
_ = buf_align;
_ = new_len;
_ = ret_addr;
return false; // リサイズ非サポート
}
fn free(
ctx: *anyopaque,
buf: []u8,
buf_align: u8,
ret_addr: usize,
) void {
_ = ctx;
_ = buf;
_ = buf_align;
_ = ret_addr;
// 個別解放は何もしない
}
pub fn reset(self: *BumpAllocator) void {
self.offset = 0;
}
};
使用例:
const std = @import("std");
pub fn main() !void {
var buffer: [1024]u8 = undefined;
var bump = BumpAllocator.init(&buffer);
const allocator = bump.allocator();
const arr1 = try allocator.alloc(i32, 10);
std.debug.print("Allocated {} bytes\n", .{bump.offset});
const arr2 = try allocator.alloc(u8, 20);
std.debug.print("Allocated {} bytes\n", .{bump.offset});
// 個別解放は何もしない
allocator.free(arr1);
std.debug.print("After free: {} bytes\n", .{bump.offset});
// リセット
bump.reset();
std.debug.print("After reset: {} bytes\n", .{bump.offset});
_ = arr2;
}
出力:
Allocated 40 bytes
Allocated 60 bytes
After free: 60 bytes
After reset: 0 bytes
1.4 アライメントの理解
メモリアライメントとは
CPUは、特定のアライメントでメモリアクセスすることで最高のパフォーマンスを発揮します:
アライメントの例 (x86_64):
アドレス: 0 1 2 3 4 5 6 7 8 9 A B C D E F
u8: [x]
u16: [x][x]
u32: [x][x][x][x]
u64: [x][x][x][x][x][x][x][x]
良いアライメント (u32):
0: [x][x][x][x] OK
4: [x][x][x][x] OK
8: [x][x][x][x] OK
悪いアライメント (u32):
1: [x][x][x][x] 遅い or クラッシュ
2: [x][x][x][x] 遅い or クラッシュ
3: [x][x][x][x] 遅い or クラッシュ
アライメント計算
const std = @import("std");
pub fn main() void {
// 型のアライメント
std.debug.print("u8 align: {}\n", .{@alignOf(u8)}); // 1
std.debug.print("u16 align: {}\n", .{@alignOf(u16)}); // 2
std.debug.print("u32 align: {}\n", .{@alignOf(u32)}); // 4
std.debug.print("u64 align: {}\n", .{@alignOf(u64)}); // 8
// アライメント調整
var offset: usize = 5;
const alignment: usize = 8;
// 次のアライメント済みオフセット
const aligned = std.mem.alignForward(usize, offset, alignment);
std.debug.print("5 aligned to 8: {}\n", .{aligned}); // 8
}
構造体のアライメント
const std = @import("std");
// パディングあり
const UnalignedStruct = struct {
a: u8, // 1バイト
// 3バイトパディング
b: u32, // 4バイト
c: u8, // 1バイト
// 3バイトパディング
};
// パディング最適化
const AlignedStruct = struct {
b: u32, // 4バイト
a: u8, // 1バイト
c: u8, // 1バイト
// 2バイトパディング
};
// パックされた構造体 (パディングなし)
const PackedStruct = packed struct {
a: u8,
b: u32,
c: u8,
};
pub fn main() void {
std.debug.print("Unaligned: {}\n", .{@sizeOf(UnalignedStruct)}); // 12
std.debug.print("Aligned: {}\n", .{@sizeOf(AlignedStruct)}); // 8
std.debug.print("Packed: {}\n", .{@sizeOf(PackedStruct)}); // 6
}
1.5 メモリプール
FixedBufferAllocatorの実装
const std = @import("std");
/// 固定サイズバッファのアロケータ
pub const FixedBufferAllocator = struct {
buffer: []u8,
end_index: usize,
pub fn init(buffer: []u8) FixedBufferAllocator {
return .{
.buffer = buffer,
.end_index = 0,
};
}
pub fn allocator(self: *FixedBufferAllocator) std.mem.Allocator {
return .{
.ptr = self,
.vtable = &.{
.alloc = alloc,
.resize = resize,
.free = free,
},
};
}
fn alloc(
ctx: *anyopaque,
len: usize,
ptr_align: u8,
ret_addr: usize,
) ?[*]u8 {
_ = ret_addr;
const self: *FixedBufferAllocator = @ptrCast(@alignCast(ctx));
const alignment = @as(usize, 1) << @as(std.math.Log2Int(usize), @intCast(ptr_align));
const start = std.mem.alignForward(usize, self.end_index, alignment);
const end = start + len;
if (end > self.buffer.len) {
return null;
}
self.end_index = end;
return self.buffer[start..end].ptr;
}
fn resize(
ctx: *anyopaque,
buf: []u8,
buf_align: u8,
new_len: usize,
ret_addr: usize,
) bool {
const self: *FixedBufferAllocator = @ptrCast(@alignCast(ctx));
_ = buf_align;
_ = ret_addr;
const buf_end = @intFromPtr(buf.ptr) + buf.len;
const self_end = @intFromPtr(self.buffer.ptr) + self.end_index;
// 最後の割り当てのみリサイズ可能
if (buf_end == self_end) {
const new_end = @intFromPtr(buf.ptr) + new_len;
const buffer_end = @intFromPtr(self.buffer.ptr) + self.buffer.len;
if (new_end <= buffer_end) {
self.end_index = new_end - @intFromPtr(self.buffer.ptr);
return true;
}
}
return false;
}
fn free(
ctx: *anyopaque,
buf: []u8,
buf_align: u8,
ret_addr: usize,
) void {
_ = ctx;
_ = buf;
_ = buf_align;
_ = ret_addr;
// 何もしない
}
pub fn reset(self: *FixedBufferAllocator) void {
self.end_index = 0;
}
};
1.6 練習問題
問題1: Bump Allocatorの拡張
BumpAllocatorに以下の機能を追加してください:
pub const ImprovedBumpAllocator = struct {
// TODO: 実装
// 1. 使用量統計の追跡
// 2. アロケーションログ
// 3. メモリ使用量のレポート
};
問題2: スタックアロケータ
スタックのようにLIFO順序で解放できるアロケータを実装してください:
pub const StackAllocator = struct {
// TODO: 実装
// 最後に割り当てたメモリのみ解放可能
};
問題3: アライメントテスト
様々なアライメントで正しく動作することを確認するテストを作成してください。
1.7 まとめ
この章では、アロケータの概念について学びました:
- 歴史: メモリ管理の進化
- インターフェース: std.mem.Allocator
- 実装: Bump Allocator
- アライメント: CPU最適化
- メモリプール: 固定サイズバッファ
- Zig Allocator: https://ziglang.org/documentation/master/std/#std.mem.Allocator
- Memory Alignment: https://en.wikipedia.org/wiki/Data_structure_alignment
次の章では、ArenaAllocatorについて詳しく学びます。