Allocator Customizado em Zig — Tutorial Passo a Passo
Neste tutorial, vamos construir dois allocators de memória customizados em Zig: um bump allocator (ultra-rápido, sem liberação individual) e um free-list allocator (uso geral com alocação e liberação). Ambos implementam a interface std.mem.Allocator.
O Que Vamos Construir
Nossos allocators vão:
- Bump Allocator: alocação O(1) por incremento de ponteiro, reset em massa
- Free-List Allocator: alocação com busca first-fit, liberação individual, coalescência de blocos livres
- Implementar a interface
std.mem.Allocatorda stdlib - Incluir métricas de uso (bytes alocados, fragmentação)
- Funcionar com qualquer estrutura de dados da stdlib
Por Que Este Projeto?
Allocators customizados são uma das features mais poderosas de Zig. Entender como a memória é gerenciada nos torna programadores melhores e nos permite otimizar para casos específicos. O bump allocator é ideal para compiladores e parsers; o free-list é a base de malloc.
Pré-requisitos
- Zig 0.13+ instalado (guia de instalação)
- Entendimento de allocators da stdlib
- Conhecimento de ponteiros e slices
Passo 1: Estrutura do Projeto
mkdir allocator-customizado
cd allocator-customizado
zig init
Passo 2: Bump Allocator
O bump allocator é o mais simples possível: mantém um ponteiro que “avança” a cada alocação. Não permite liberação individual — apenas reset total.
const std = @import("std");
const mem = std.mem;
const io = std.io;
const fmt = std.fmt;
const math = std.math;
/// Bump Allocator: alocação O(1) por incremento de ponteiro.
///
/// Ideal para: compiladores, parsers, frames de jogo, qualquer
/// situação onde todas as alocações são liberadas juntas.
///
/// Trade-off: impossível liberar memória individualmente.
const BumpAllocator = struct {
buffer: []u8,
offset: usize,
total_alocacoes: u64,
pico_uso: usize,
const Self = @This();
/// Cria um bump allocator sobre um buffer existente.
pub fn init(buffer: []u8) Self {
return .{
.buffer = buffer,
.offset = 0,
.total_alocacoes = 0,
.pico_uso = 0,
};
}
/// Retorna a interface std.mem.Allocator.
pub fn allocator(self: *Self) mem.Allocator {
return .{
.ptr = self,
.vtable = &.{
.alloc = alloc,
.resize = resize,
.free = free,
},
};
}
fn alloc(ctx: *anyopaque, len: usize, ptr_align: u8, _: usize) ?[*]u8 {
const self: *Self = @ptrCast(@alignCast(ctx));
const alignment = @as(usize, 1) << @intCast(ptr_align);
// Alinhar o offset
const aligned_offset = mem.alignForward(usize, self.offset, alignment);
if (aligned_offset + len > self.buffer.len) {
return null; // sem espaço
}
const resultado = self.buffer[aligned_offset..].ptr;
self.offset = aligned_offset + len;
self.total_alocacoes += 1;
self.pico_uso = @max(self.pico_uso, self.offset);
return resultado;
}
fn resize(_: *anyopaque, _: []u8, _: u8, _: usize, _: usize) bool {
// Bump allocator não suporta resize
return false;
}
fn free(_: *anyopaque, _: []u8, _: u8, _: usize) void {
// Bump allocator não faz nada no free individual
// Memória só é liberada com reset()
}
/// Libera toda a memória de uma vez. O(1).
pub fn reset(self: *Self) void {
self.offset = 0;
}
/// Retorna bytes livres disponíveis.
pub fn bytesDisponiveis(self: *const Self) usize {
return self.buffer.len - self.offset;
}
/// Retorna bytes em uso.
pub fn bytesEmUso(self: *const Self) usize {
return self.offset;
}
};
Decisão de design: O bump allocator é absurdamente rápido porque cada alocação é apenas incrementar um ponteiro. O preço é que não podemos liberar memória individualmente. O padrão de uso é: alocar tudo, usar, resetar tudo.
Passo 3: Free-List Allocator
O free-list allocator mantém uma lista encadeada de blocos livres. É mais complexo mas permite alocação e liberação individual.
/// Header de um bloco no free-list allocator.
/// Cada bloco (livre ou em uso) tem este header no início.
const BlocoHeader = struct {
tamanho: usize, // tamanho do bloco (sem incluir o header)
livre: bool,
proximo: ?*BlocoHeader, // próximo bloco livre (se livre)
};
const HEADER_SIZE = @sizeOf(BlocoHeader);
/// Free-List Allocator: alocação com busca first-fit.
///
/// Mantém uma lista encadeada de blocos livres. Quando um bloco
/// é liberado, tenta coalescer com blocos adjacentes para reduzir
/// fragmentação.
const FreeListAllocator = struct {
buffer: []u8,
primeiro_livre: ?*BlocoHeader,
total_alocacoes: u64,
total_liberacoes: u64,
bytes_em_uso: usize,
const Self = @This();
/// Cria um free-list allocator sobre um buffer existente.
pub fn init(buffer: []u8) Self {
// Inicializar com um único bloco livre cobrindo todo o buffer
const header: *BlocoHeader = @ptrCast(@alignCast(buffer.ptr));
header.* = .{
.tamanho = buffer.len - HEADER_SIZE,
.livre = true,
.proximo = null,
};
return .{
.buffer = buffer,
.primeiro_livre = header,
.total_alocacoes = 0,
.total_liberacoes = 0,
.bytes_em_uso = 0,
};
}
/// Retorna a interface std.mem.Allocator.
pub fn allocator(self: *Self) mem.Allocator {
return .{
.ptr = self,
.vtable = &.{
.alloc = alloc,
.resize = resize,
.free = freeFn,
},
};
}
fn alloc(ctx: *anyopaque, len: usize, ptr_align: u8, _: usize) ?[*]u8 {
const self: *Self = @ptrCast(@alignCast(ctx));
const tamanho_necessario = @max(len, @sizeOf(BlocoHeader)); // mínimo para header
// Busca first-fit na lista de blocos livres
var anterior: ?*BlocoHeader = null;
var atual = self.primeiro_livre;
while (atual) |bloco| {
if (bloco.livre and bloco.tamanho >= tamanho_necessario) {
// Encontramos um bloco que cabe!
// Tentar dividir o bloco se sobra espaço suficiente
if (bloco.tamanho >= tamanho_necessario + HEADER_SIZE + 16) {
// Dividir: criar novo bloco livre com o espaço restante
const novo_bloco_ptr = @as([*]u8, @ptrCast(bloco)) + HEADER_SIZE + tamanho_necessario;
const novo_bloco: *BlocoHeader = @ptrCast(@alignCast(novo_bloco_ptr));
novo_bloco.* = .{
.tamanho = bloco.tamanho - tamanho_necessario - HEADER_SIZE,
.livre = true,
.proximo = bloco.proximo,
};
bloco.tamanho = tamanho_necessario;
bloco.proximo = novo_bloco;
}
bloco.livre = false;
// Remover da lista de livres
if (anterior) |ant| {
ant.proximo = bloco.proximo;
} else {
self.primeiro_livre = bloco.proximo;
}
self.total_alocacoes += 1;
self.bytes_em_uso += bloco.tamanho;
_ = ptr_align;
const data_ptr = @as([*]u8, @ptrCast(bloco)) + HEADER_SIZE;
return data_ptr;
}
anterior = bloco;
atual = bloco.proximo;
}
return null; // sem espaço
}
fn resize(_: *anyopaque, _: []u8, _: u8, _: usize, _: usize) bool {
return false;
}
fn freeFn(ctx: *anyopaque, buf: []u8, _: u8, _: usize) void {
const self: *Self = @ptrCast(@alignCast(ctx));
// Encontrar o header do bloco (está logo antes dos dados)
const header_ptr = @as([*]u8, @ptrCast(buf.ptr)) - HEADER_SIZE;
const header: *BlocoHeader = @ptrCast(@alignCast(header_ptr));
header.livre = true;
self.total_liberacoes += 1;
self.bytes_em_uso -= @min(self.bytes_em_uso, header.tamanho);
// Adicionar de volta à lista de livres (no início, O(1))
header.proximo = self.primeiro_livre;
self.primeiro_livre = header;
// Tentar coalescer com blocos adjacentes
self.coalescer();
}
/// Coalesce blocos livres adjacentes para reduzir fragmentação.
fn coalescer(self: *Self) void {
// Percorrer o buffer sequencialmente e juntar blocos livres adjacentes
var pos: usize = 0;
while (pos + HEADER_SIZE < self.buffer.len) {
const header: *BlocoHeader = @ptrCast(@alignCast(self.buffer[pos..].ptr));
if (header.livre) {
const proximo_pos = pos + HEADER_SIZE + header.tamanho;
if (proximo_pos + HEADER_SIZE <= self.buffer.len) {
const proximo: *BlocoHeader = @ptrCast(@alignCast(self.buffer[proximo_pos..].ptr));
if (proximo.livre) {
// Coalescer: absorver o próximo bloco
header.tamanho += HEADER_SIZE + proximo.tamanho;
continue; // verificar novamente (pode ter mais blocos)
}
}
}
pos += HEADER_SIZE + header.tamanho;
}
// Reconstruir a lista de livres
self.primeiro_livre = null;
pos = 0;
while (pos + HEADER_SIZE < self.buffer.len) {
const header: *BlocoHeader = @ptrCast(@alignCast(self.buffer[pos..].ptr));
if (header.livre) {
header.proximo = self.primeiro_livre;
self.primeiro_livre = header;
}
pos += HEADER_SIZE + header.tamanho;
}
}
/// Retorna estatísticas de uso.
pub fn estatisticas(self: *const Self) struct { em_uso: usize, livre: usize, alocacoes: u64, liberacoes: u64 } {
var total_livre: usize = 0;
var atual = self.primeiro_livre;
while (atual) |bloco| {
total_livre += bloco.tamanho;
atual = bloco.proximo;
}
return .{
.em_uso = self.bytes_em_uso,
.livre = total_livre,
.alocacoes = self.total_alocacoes,
.liberacoes = self.total_liberacoes,
};
}
};
Passo 4: Demonstração e Benchmarks
pub fn main() !void {
const stdout = io.getStdOut().writer();
try stdout.print(
\\
\\ ==========================================
\\ ALLOCATORS CUSTOMIZADOS - Zig
\\ ==========================================
\\
\\
, .{});
// === DEMONSTRAÇÃO BUMP ALLOCATOR ===
try stdout.print(" --- Bump Allocator ---\n", .{});
var bump_buffer: [4096]u8 = undefined;
var bump = BumpAllocator.init(&bump_buffer);
const bump_alloc = bump.allocator();
// Usar com ArrayList da stdlib!
var lista = std.ArrayList(u32).init(bump_alloc);
for (0..100) |i| {
lista.append(@intCast(i)) catch break;
}
try stdout.print(" ArrayList com {d} elementos criada\n", .{lista.items.len});
try stdout.print(" Bytes em uso: {d}/{d}\n", .{ bump.bytesEmUso(), bump_buffer.len });
try stdout.print(" Total alocacoes: {d}\n", .{bump.total_alocacoes});
try stdout.print(" Pico de uso: {d} bytes\n\n", .{bump.pico_uso});
// Reset: libera TUDO de uma vez
bump.reset();
try stdout.print(" Apos reset: {d} bytes em uso\n\n", .{bump.bytesEmUso()});
// === DEMONSTRAÇÃO FREE-LIST ALLOCATOR ===
try stdout.print(" --- Free-List Allocator ---\n", .{});
var fl_buffer: [8192]u8 align(@alignOf(BlocoHeader)) = undefined;
var fl = FreeListAllocator.init(&fl_buffer);
const fl_alloc = fl.allocator();
// Alocar vários blocos
const bloco1 = fl_alloc.alloc(u8, 100) catch null;
const bloco2 = fl_alloc.alloc(u8, 200) catch null;
const bloco3 = fl_alloc.alloc(u8, 150) catch null;
var stats = fl.estatisticas();
try stdout.print(" Apos 3 alocacoes:\n", .{});
try stdout.print(" Em uso: {d} bytes\n", .{stats.em_uso});
try stdout.print(" Livre: {d} bytes\n", .{stats.livre});
try stdout.print(" Alocacoes: {d}\n\n", .{stats.alocacoes});
// Liberar o bloco do meio (cria fragmentação)
if (bloco2) |b| fl_alloc.free(b);
stats = fl.estatisticas();
try stdout.print(" Apos liberar bloco do meio:\n", .{});
try stdout.print(" Em uso: {d} bytes\n", .{stats.em_uso});
try stdout.print(" Livre: {d} bytes\n", .{stats.livre});
try stdout.print(" Liberacoes: {d}\n\n", .{stats.liberacoes});
// Liberar os outros blocos
if (bloco1) |b| fl_alloc.free(b);
if (bloco3) |b| fl_alloc.free(b);
stats = fl.estatisticas();
try stdout.print(" Apos liberar tudo (com coalescencia):\n", .{});
try stdout.print(" Em uso: {d} bytes\n", .{stats.em_uso});
try stdout.print(" Livre: {d} bytes\n", .{stats.livre});
// === BENCHMARK SIMPLES ===
try stdout.print("\n --- Benchmark ---\n", .{});
const ITERACOES = 1000;
// Benchmark bump
bump.reset();
const inicio_bump = std.time.nanoTimestamp();
for (0..ITERACOES) |_| {
_ = bump_alloc.alloc(u8, 32) catch {};
if (bump.bytesDisponiveis() < 64) bump.reset();
}
const tempo_bump: u64 = @intCast(std.time.nanoTimestamp() - inicio_bump);
try stdout.print(" Bump: {d} alocacoes em {d}ns ({d}ns/alloc)\n", .{
ITERACOES, tempo_bump, tempo_bump / ITERACOES,
});
try stdout.print("\n Conclusao: Bump allocator e ideal para cenarios\n", .{});
try stdout.print(" de alocacao em massa com liberacao coletiva.\n", .{});
try stdout.print(" Free-list e mais versatil mas mais lento.\n", .{});
}
Testes
test "bump - alocacao basica" {
var buffer: [1024]u8 = undefined;
var bump = BumpAllocator.init(&buffer);
const alloc = bump.allocator();
const slice = try alloc.alloc(u8, 100);
try std.testing.expectEqual(@as(usize, 100), slice.len);
try std.testing.expect(bump.bytesEmUso() >= 100);
}
test "bump - reset libera tudo" {
var buffer: [1024]u8 = undefined;
var bump = BumpAllocator.init(&buffer);
const alloc = bump.allocator();
_ = try alloc.alloc(u8, 500);
try std.testing.expect(bump.bytesEmUso() >= 500);
bump.reset();
try std.testing.expectEqual(@as(usize, 0), bump.bytesEmUso());
}
test "bump - overflow retorna erro" {
var buffer: [64]u8 = undefined;
var bump = BumpAllocator.init(&buffer);
const alloc = bump.allocator();
const resultado = alloc.alloc(u8, 1000);
try std.testing.expectError(error.OutOfMemory, resultado);
}
test "free-list - alocar e liberar" {
var buffer: [4096]u8 align(@alignOf(BlocoHeader)) = undefined;
var fl = FreeListAllocator.init(&buffer);
const alloc = fl.allocator();
const slice = try alloc.alloc(u8, 100);
try std.testing.expectEqual(@as(usize, 100), slice.len);
alloc.free(slice);
}
test "free-list - multiplas alocacoes" {
var buffer: [4096]u8 align(@alignOf(BlocoHeader)) = undefined;
var fl = FreeListAllocator.init(&buffer);
const alloc = fl.allocator();
const a = try alloc.alloc(u8, 100);
const b = try alloc.alloc(u8, 200);
_ = try alloc.alloc(u8, 150);
alloc.free(b);
alloc.free(a);
const stats = fl.estatisticas();
try std.testing.expectEqual(@as(u64, 2), stats.liberacoes);
}
Compilando e Executando
zig build run
zig build test
Conceitos Aprendidos
- Interface
std.mem.Allocatore vtable - Bump allocation com incremento de ponteiro
- Free-list com busca first-fit
- Coalescência de blocos livres
- Alinhamento de memória com
@alignOfemem.alignForward
Próximos Passos
- Explore allocators da stdlib (GPA, Arena, FixedBuffer)
- Veja gerenciamento de memória na documentação
- Construa o Ring Buffer para outra estrutura
- Consulte a stdlib de memória para utilitários