Arena Allocator em Rust: Alocação por Região, typed-arena e Grafos sem Dor

Introdução

O Arena Allocator (alocador por arena, ou alocação por região) é uma estratégia de gerenciamento de memória onde todas as alocações são feitas dentro de uma região contígua de memória (a “arena”) e a desalocação acontece toda de uma vez quando a arena é descartada. Não há free individual — tudo é liberado junto.

Em Rust, arenas resolvem um dos problemas mais dolorosos da linguagem: estruturas auto-referenciais e grafos. Quando nós de uma árvore ou grafo precisam apontar uns para os outros, o sistema de ownership do Rust torna a implementação com Box e referências extremamente difícil. Arenas oferecem uma solução elegante: todos os nós são alocados na arena e referenciados por tempo de vida 'arena, permitindo referências cruzadas sem Rc, RefCell ou ponteiros brutos.

Compiladores são o caso de uso clássico: a AST (Abstract Syntax Tree) é um grafo de nós alocados durante o parsing e descartados todos de uma vez ao final da compilação. O compilador rustc usa arenas extensivamente, assim como compiladores de JavaScript (V8), jogos (ECS) e parsers em geral.

Nesta página, entenderemos o conceito de bump allocation, usaremos a crate typed-arena e construiremos um exemplo prático de alocação de AST para um compilador.

Conceito e Teoria

Como Funciona uma Arena

Ao contrário do alocador global (malloc/free), que gerencia blocos individuais e precisa lidar com fragmentação, a arena simplesmente mantém um ponteiro que avança a cada alocação (bump allocation). Não há overhead de gerenciamento por bloco.

Bump Allocation — Como a Arena Aloca:
========================================

Estado inicial da arena (1 KB alocado):
  +-------------------------------------------------------+
  |                     Memória Livre                      |
  +-------------------------------------------------------+
  ^
  ponteiro (início)

Após alocar A (64 bytes):
  +------+------------------------------------------------+
  |  A   |                 Memória Livre                   |
  +------+------------------------------------------------+
         ^
         ponteiro

Após alocar B (128 bytes):
  +------+----------+-------------------------------------+
  |  A   |    B     |           Memória Livre              |
  +------+----------+-------------------------------------+
                    ^
                    ponteiro

Após alocar C (32 bytes):
  +------+----------+----+--------------------------------+
  |  A   |    B     | C  |        Memória Livre            |
  +------+----------+----+--------------------------------+
                         ^
                         ponteiro

Desalocação: tudo de uma vez!
  +-------------------------------------------------------+
  |                     Memória Livre                      |
  +-------------------------------------------------------+
  ^
  ponteiro (resetado)

  Custo de alocação: incrementar um ponteiro = O(1)
  Custo de desalocação: resetar o ponteiro = O(1)
  Sem fragmentação!

Por Que Arenas São Importantes em Rust

O sistema de ownership do Rust dificulta certos padrões comuns:

O Problema: Estruturas Auto-Referenciais em Rust
===================================================

Tentativa com Box (NÃO COMPILA):

  struct No {
      valor: i32,
      filhos: Vec<Box<No>>,     // OK até aqui
      pai: &No,                  // ERRO: tempo de vida?
  }

  // O pai não pode referenciar o filho e vice-versa!
  // Ownership é uma árvore, não um grafo.


Tentativa com Rc (funciona, mas tem custo):

  struct No {
      valor: i32,
      filhos: Vec<Rc<RefCell<No>>>,
      pai: Weak<RefCell<No>>,     // Referência fraca ao pai
  }

  // Funciona, mas:
  // - Overhead de contagem de referências
  // - RefCell com verificação em runtime
  // - Código verboso e propenso a erros


Solução com Arena (elegante e eficiente):

  struct No<'arena> {
      valor: i32,
      filhos: Vec<&'arena No<'arena>>,
      pai: Option<&'arena No<'arena>>,
  }

  // Todos os nós vivem na arena.
  // Referências são simples & com lifetime 'arena.
  // Sem overhead de Rc/RefCell!
  // Desalocação: destruir a arena libera tudo.

Comparação de Estratégias de Alocação

Estratégias de Alocação Comparadas:
=====================================

  Alocador Global (malloc/free):
  +--+----+--+------+--+---+--+
  |A |livre|B |livre |C |D  |? |   Fragmentação!
  +--+----+--+------+--+---+--+
  Custo: alocação O(1)~O(n), free O(1), fragmentação

  Arena (bump allocator):
  +--+----+---+--+-------------+
  |A | B  | C |D |   livre     |   Sem fragmentação!
  +--+----+---+--+-------------+
  ^                ^
  início           ponteiro
  Custo: alocação O(1), desalocação O(1) (tudo junto)

  Pool (object pool):
  +--+--+--+--+--+--+--+--+
  |A |? |B |? |C |? |D |? |   Slots fixos, sem fragmentação
  +--+--+--+--+--+--+--+--+
  Custo: alocação O(1), free O(1), mas tamanho fixo por objeto

Complexidade

Operação	Arena	malloc/free	Rc/Box
Alocação	O(1)*	O(1)~O(n)	O(1)~O(n)
Desalocação individual	N/A**	O(1)	O(1)
Desalocação total	O(1)	O(n)	O(n)
Overhead por objeto	0 bytes	8-16 bytes	8-24 bytes
Fragmentação	Nenhuma	Possível	Possível

* Amortizado. Quando a arena precisa alocar um novo bloco, é O(n). ** Arenas não suportam desalocação individual — esse é o trade-off.

Quando Usar Arenas

Cenário	Arena?	Motivo
AST de compilador	Sim	Criada de uma vez, descartada de uma vez
Nós de grafo com referências cruzadas	Sim	Resolve auto-referência elegantemente
ECS em game engines	Sim	Componentes alocados por frame/fase
Cache de objetos de longa duração	Talvez	Se desalocação individual for necessária, não
Estruturas pequenas e efêmeras	Sim	Overhead mínimo
Objetos com tempos de vida variados	Não	Arena libera tudo junto

Implementação em Rust

Arena Simples (Manual)

use std::cell::Cell;
use std::mem;

/// Arena simples com bump allocation.
/// Aloca objetos do mesmo tipo T em blocos contíguos.
pub struct ArenaSimples<T> {
    /// Blocos de memória já preenchidos.
    blocos_cheios: Vec<Vec<T>>,
    /// Bloco atual onde novas alocações acontecem.
    bloco_atual: Vec<T>,
    /// Capacidade de cada bloco.
    capacidade_bloco: usize,
}

impl<T> ArenaSimples<T> {
    /// Cria uma nova arena com a capacidade de bloco especificada.
    pub fn nova(capacidade_bloco: usize) -> Self {
        ArenaSimples {
            blocos_cheios: Vec::new(),
            bloco_atual: Vec::with_capacity(capacidade_bloco),
            capacidade_bloco,
        }
    }

    /// Aloca um novo objeto na arena e retorna uma referência.
    /// A referência é válida enquanto a arena existir.
    pub fn alocar(&mut self, valor: T) -> &T {
        // Se o bloco atual está cheio, cria um novo
        if self.bloco_atual.len() == self.capacidade_bloco {
            let bloco_cheio = std::mem::replace(
                &mut self.bloco_atual,
                Vec::with_capacity(self.capacidade_bloco),
            );
            self.blocos_cheios.push(bloco_cheio);
        }

        self.bloco_atual.push(valor);
        // SEGURANÇA: a referência é válida enquanto a arena existir,
        // pois os Vec nunca são realocados após serem movidos para blocos_cheios.
        // O bloco_atual pode realocar, mas usamos o último elemento.
        let referencia = &self.bloco_atual[self.bloco_atual.len() - 1];

        // Precisamos de unsafe para estender o lifetime.
        // Em produção, use typed-arena que faz isso corretamente.
        unsafe { &*(referencia as *const T) }
    }

    /// Retorna o total de objetos alocados.
    pub fn total_alocados(&self) -> usize {
        self.blocos_cheios.iter().map(|b| b.len()).sum::<usize>()
            + self.bloco_atual.len()
    }

    /// Retorna o total de memória usada (em bytes, aproximado).
    pub fn memoria_usada(&self) -> usize {
        let por_bloco = self.capacidade_bloco * mem::size_of::<T>();
        (self.blocos_cheios.len() + 1) * por_bloco
    }
}

fn main() {
    let mut arena = ArenaSimples::nova(1024);

    // Aloca vários inteiros
    let a = arena.alocar(42);
    let b = arena.alocar(99);
    let c = arena.alocar(7);

    println!("Valores: {}, {}, {}", a, b, c);
    println!("Total alocados: {}", arena.total_alocados());
    println!("Memória usada: {} bytes", arena.memoria_usada());

    // Quando arena sai de escopo, TUDO é liberado de uma vez.
}

Usando a Crate `typed-arena`

A crate typed-arena é a solução idiomática em Rust para arenas. Ela fornece uma API segura (sem unsafe no código do usuário) e é usada internamente pelo compilador rustc.

// Adicione ao Cargo.toml: typed-arena = "2.0"

use typed_arena::Arena;

/// Nó de uma árvore alocado na arena.
/// O lifetime 'a vincula o nó à arena.
#[derive(Debug)]
struct NoArvore<'a> {
    valor: i32,
    filhos: Vec<&'a NoArvore<'a>>,
}

/// Constrói uma árvore usando arena allocation.
fn construir_arvore<'a>(arena: &'a Arena<NoArvore<'a>>) -> &'a NoArvore<'a> {
    // Aloca folhas
    let folha1 = arena.alloc(NoArvore {
        valor: 1,
        filhos: vec![],
    });
    let folha2 = arena.alloc(NoArvore {
        valor: 2,
        filhos: vec![],
    });
    let folha3 = arena.alloc(NoArvore {
        valor: 3,
        filhos: vec![],
    });

    // Aloca nós intermediários (referenciam as folhas)
    let interno1 = arena.alloc(NoArvore {
        valor: 10,
        filhos: vec![folha1, folha2],
    });
    let interno2 = arena.alloc(NoArvore {
        valor: 20,
        filhos: vec![folha3],
    });

    // Aloca a raiz (referencia os nós intermediários)
    let raiz = arena.alloc(NoArvore {
        valor: 100,
        filhos: vec![interno1, interno2],
    });

    raiz
}

/// Percorre a árvore em pré-ordem.
fn percorrer_pre_ordem(no: &NoArvore, profundidade: usize) {
    let indentacao = "  ".repeat(profundidade);
    println!("{}[{}]", indentacao, no.valor);
    for filho in &no.filhos {
        percorrer_pre_ordem(filho, profundidade + 1);
    }
}

fn main() {
    // A arena gerencia toda a memória da árvore
    let arena = Arena::new();

    let raiz = construir_arvore(&arena);

    println!("Árvore construída com arena allocation:");
    percorrer_pre_ordem(raiz, 0);

    // Quando `arena` sai de escopo, TODOS os nós são liberados.
    // Sem memory leaks, sem contagem de referência.
}

Grafo com Arena (Resolvendo o Problema de Auto-Referência)

use typed_arena::Arena;
use std::cell::RefCell;

/// Nó de um grafo direcionado alocado na arena.
/// Usa RefCell para permitir adição de vizinhos após criação.
#[derive(Debug)]
struct NoGrafo<'a> {
    id: usize,
    nome: &'static str,
    vizinhos: RefCell<Vec<&'a NoGrafo<'a>>>,
}

impl<'a> NoGrafo<'a> {
    fn novo(id: usize, nome: &'static str) -> Self {
        NoGrafo {
            id,
            nome,
            vizinhos: RefCell::new(vec![]),
        }
    }

    /// Adiciona uma aresta para outro nó.
    fn conectar(&self, outro: &'a NoGrafo<'a>) {
        self.vizinhos.borrow_mut().push(outro);
    }
}

/// Realiza busca em largura (BFS) no grafo.
fn bfs<'a>(inicio: &'a NoGrafo<'a>) -> Vec<&'a NoGrafo<'a>> {
    use std::collections::{HashSet, VecDeque};

    let mut visitados = HashSet::new();
    let mut fila = VecDeque::new();
    let mut ordem = Vec::new();

    visitados.insert(inicio.id);
    fila.push_back(inicio);

    while let Some(no) = fila.pop_front() {
        ordem.push(no);

        for vizinho in no.vizinhos.borrow().iter() {
            if !visitados.contains(&vizinho.id) {
                visitados.insert(vizinho.id);
                fila.push_back(vizinho);
            }
        }
    }

    ordem
}

fn main() {
    let arena = Arena::new();

    // Cria nós do grafo na arena
    let sp = arena.alloc(NoGrafo::novo(0, "São Paulo"));
    let rj = arena.alloc(NoGrafo::novo(1, "Rio de Janeiro"));
    let bh = arena.alloc(NoGrafo::novo(2, "Belo Horizonte"));
    let ctb = arena.alloc(NoGrafo::novo(3, "Curitiba"));
    let poa = arena.alloc(NoGrafo::novo(4, "Porto Alegre"));

    // Cria arestas (referências cruzadas — impossível sem arena!)
    sp.conectar(rj);
    sp.conectar(bh);
    sp.conectar(ctb);
    rj.conectar(bh);
    ctb.conectar(poa);
    poa.conectar(sp); // Ciclo! SP -> CTB -> POA -> SP

    println!("Grafo de cidades brasileiras:");
    for no in [sp, rj, bh, ctb, poa] {
        let vizinhos: Vec<_> = no
            .vizinhos
            .borrow()
            .iter()
            .map(|v| v.nome)
            .collect();
        println!("  {} -> {:?}", no.nome, vizinhos);
    }

    println!("\nBFS a partir de São Paulo:");
    for no in bfs(sp) {
        println!("  -> {}", no.nome);
    }

    // Arena libera TUDO ao sair de escopo — sem vazamento!
}

Exemplo Prático

Alocação de AST para Compilador de Expressões

Um compilador transforma código-fonte em uma AST (Abstract Syntax Tree). Cada nó referencia outros nós, formando um grafo. Com arenas, toda a AST vive em uma região de memória eficiente.

use typed_arena::Arena;
use std::fmt;

/// Tokens produzidos pelo lexer.
#[derive(Debug, Clone, PartialEq)]
enum Token {
    Numero(f64),
    Mais,
    Menos,
    Vezes,
    Dividir,
    AbreParentese,
    FechaParentese,
    Fim,
}

/// Nó da AST — alocado na arena.
#[derive(Debug)]
enum Expr<'a> {
    /// Literal numérico.
    Numero(f64),
    /// Operação binária: esquerda op direita.
    Binaria {
        esquerda: &'a Expr<'a>,
        operador: Operador,
        direita: &'a Expr<'a>,
    },
    /// Negação unária: -expr.
    Negacao(&'a Expr<'a>),
}

#[derive(Debug, Clone, Copy)]
enum Operador {
    Soma,
    Subtracao,
    Multiplicacao,
    Divisao,
}

impl fmt::Display for Operador {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
            Operador::Soma => write!(f, "+"),
            Operador::Subtracao => write!(f, "-"),
            Operador::Multiplicacao => write!(f, "*"),
            Operador::Divisao => write!(f, "/"),
        }
    }
}

/// Parser que constrói a AST na arena.
struct Parser<'a> {
    tokens: Vec<Token>,
    posicao: usize,
    arena: &'a Arena<Expr<'a>>,
}

impl<'a> Parser<'a> {
    fn novo(tokens: Vec<Token>, arena: &'a Arena<Expr<'a>>) -> Self {
        Parser {
            tokens,
            posicao: 0,
            arena,
        }
    }

    fn token_atual(&self) -> &Token {
        &self.tokens[self.posicao]
    }

    fn avancar(&mut self) {
        self.posicao += 1;
    }

    /// Ponto de entrada: expressão = termo ((+|-) termo)*
    fn expressao(&mut self) -> &'a Expr<'a> {
        let mut esquerda = self.termo();

        loop {
            let op = match self.token_atual() {
                Token::Mais => Operador::Soma,
                Token::Menos => Operador::Subtracao,
                _ => break,
            };
            self.avancar();
            let direita = self.termo();

            // Aloca o nó binário NA ARENA
            esquerda = self.arena.alloc(Expr::Binaria {
                esquerda,
                operador: op,
                direita,
            });
        }

        esquerda
    }

    /// Termo = fator ((*|/) fator)*
    fn termo(&mut self) -> &'a Expr<'a> {
        let mut esquerda = self.fator();

        loop {
            let op = match self.token_atual() {
                Token::Vezes => Operador::Multiplicacao,
                Token::Dividir => Operador::Divisao,
                _ => break,
            };
            self.avancar();
            let direita = self.fator();

            esquerda = self.arena.alloc(Expr::Binaria {
                esquerda,
                operador: op,
                direita,
            });
        }

        esquerda
    }

    /// Fator = numero | '(' expressao ')' | '-' fator
    fn fator(&mut self) -> &'a Expr<'a> {
        match self.token_atual().clone() {
            Token::Numero(n) => {
                self.avancar();
                self.arena.alloc(Expr::Numero(n))
            }
            Token::AbreParentese => {
                self.avancar();
                let expr = self.expressao();
                // Consome ')'
                assert_eq!(*self.token_atual(), Token::FechaParentese);
                self.avancar();
                expr
            }
            Token::Menos => {
                self.avancar();
                let expr = self.fator();
                self.arena.alloc(Expr::Negacao(expr))
            }
            outro => panic!("Token inesperado: {:?}", outro),
        }
    }
}

/// Avalia a AST recursivamente.
fn avaliar(expr: &Expr) -> f64 {
    match expr {
        Expr::Numero(n) => *n,
        Expr::Binaria {
            esquerda,
            operador,
            direita,
        } => {
            let e = avaliar(esquerda);
            let d = avaliar(direita);
            match operador {
                Operador::Soma => e + d,
                Operador::Subtracao => e - d,
                Operador::Multiplicacao => e * d,
                Operador::Divisao => e / d,
            }
        }
        Expr::Negacao(expr) => -avaliar(expr),
    }
}

/// Exibe a AST como árvore indentada.
fn exibir_ast(expr: &Expr, profundidade: usize) {
    let indent = "  ".repeat(profundidade);
    match expr {
        Expr::Numero(n) => println!("{}{}", indent, n),
        Expr::Binaria {
            esquerda,
            operador,
            direita,
        } => {
            println!("{}({})", indent, operador);
            exibir_ast(esquerda, profundidade + 1);
            exibir_ast(direita, profundidade + 1);
        }
        Expr::Negacao(expr) => {
            println!("{}(-)", indent);
            exibir_ast(expr, profundidade + 1);
        }
    }
}

/// Tokeniza uma expressão simples.
fn tokenizar(entrada: &str) -> Vec<Token> {
    let mut tokens = Vec::new();
    let mut chars = entrada.chars().peekable();

    while let Some(&c) = chars.peek() {
        match c {
            ' ' | '\t' => {
                chars.next();
            }
            '0'..='9' | '.' => {
                let mut num = String::new();
                while let Some(&d) = chars.peek() {
                    if d.is_ascii_digit() || d == '.' {
                        num.push(d);
                        chars.next();
                    } else {
                        break;
                    }
                }
                tokens.push(Token::Numero(num.parse().unwrap()));
            }
            '+' => {
                tokens.push(Token::Mais);
                chars.next();
            }
            '-' => {
                tokens.push(Token::Menos);
                chars.next();
            }
            '*' => {
                tokens.push(Token::Vezes);
                chars.next();
            }
            '/' => {
                tokens.push(Token::Dividir);
                chars.next();
            }
            '(' => {
                tokens.push(Token::AbreParentese);
                chars.next();
            }
            ')' => {
                tokens.push(Token::FechaParentese);
                chars.next();
            }
            _ => panic!("Caractere inesperado: {}", c),
        }
    }

    tokens.push(Token::Fim);
    tokens
}

fn main() {
    println!("=== Compilador de Expressões com Arena Allocation ===\n");

    let expressoes = vec![
        "3 + 4 * 2",
        "(3 + 4) * 2",
        "10 / 2 - 3 + 1",
        "-5 + 3 * (2 + 1)",
    ];

    for expr_str in expressoes {
        println!("Expressão: {}", expr_str);

        // A arena gerencia toda a memória da AST
        let arena = Arena::new();

        let tokens = tokenizar(expr_str);
        let mut parser = Parser::novo(tokens, &arena);
        let ast = parser.expressao();

        println!("AST:");
        exibir_ast(ast, 1);

        let resultado = avaliar(ast);
        println!("Resultado: {}\n", resultado);

        // Quando `arena` sai de escopo aqui, toda a AST é liberada.
        // Zero vazamentos, zero overhead de Rc/Box.
    }

    println!("--- Comparação de Memória ---");
    println!("Com Box<Expr>:      ~24 bytes de overhead por nó (Box + vtable)");
    println!("Com Rc<Expr>:       ~32 bytes de overhead por nó (Rc + RefCell)");
    println!("Com Arena<Expr>:    ~0 bytes de overhead por nó (contíguo)");
    println!("\nAlém disso, arena = uma única desalocação vs. N desalocações.");
}

Exercícios

Exercício 1 — Arena com Contagem e Estatísticas

Estenda a ArenaSimples para rastrear estatísticas de uso: total de bytes alocados, número de objetos, número de blocos, e fragmentação interna (bytes desperdiçados no final de blocos cheios que não cabem outro objeto). Implemente um método relatorio() que exibe essas métricas.

Dica: Mantenha contadores incrementais em cada chamada de alocar(). Calcule a fragmentação como capacidade_bloco - len do último bloco quando um novo bloco é criado.

Exercício 2 — Grafo com Detecção de Ciclos

Usando a arena de grafos que implementamos, adicione um método tem_ciclo() que detecta se o grafo possui ciclos usando DFS com três estados (não visitado, em progresso, finalizado). Teste com grafos que contenham ciclos e grafos acíclicos (DAGs).

Dica: Use um HashMap<usize, Estado> para rastrear o estado de cada nó durante a DFS. Um ciclo é detectado quando visitamos um nó no estado “em progresso”.

Exercício 3 — Otimização de AST na Arena

Implemente um passo de otimização (constant folding) para a AST do compilador de expressões. Crie uma função otimizar<'a>(arena: &'a Arena<Expr<'a>>, expr: &'a Expr<'a>) -> &'a Expr<'a> que:

Avalia sub-expressões com ambos os lados constantes (ex: 3 + 4 vira 7)
Simplifica multiplicação por 0 e 1
Simplifica soma com 0

A função aloca os nós otimizados na mesma arena que a AST original. Os nós antigos não precisam ser liberados (a arena cuida disso).

Conclusão

O Arena Allocator é uma das ferramentas mais poderosas no arsenal do programador Rust, resolvendo problemas que vão além de pura eficiência de memória. Os pontos fundamentais são:

Alocação O(1): Bump allocation é a forma mais rápida de alocar memória — apenas incrementar um ponteiro.
Desalocação em massa: Toda a memória é liberada de uma vez, sem overhead de gerenciamento individual.
Resolve auto-referência: O maior benefício em Rust — arenas permitem grafos e árvores com referências cruzadas usando simples &'arena T, sem Rc, RefCell ou unsafe.
Zero fragmentação: Alocações contíguas maximizam o uso de cache e eliminam fragmentação.
Usado em compiladores reais: rustc, V8, Clang e inúmeros outros compiladores usam arenas para ASTs.

O trade-off principal é que arenas não suportam desalocação individual. Se você precisa liberar objetos individualmente durante o uso da arena, essa não é a ferramenta certa. Mas para cenários de “aloca tudo, usa tudo, descarta tudo” — compiladores, parsers, frames de jogos, processamento de requisições — arenas são imbatíveis.

Para produção em Rust, use a crate typed-arena para arenas de tipo único, ou bumpalo para arenas que suportam múltiplos tipos (mais flexível, usada no ecossistema Wasm). O compilador rustc tem sua própria implementação em rustc_arena, otimizada para seu caso de uso específico.

Arenas nos lembram que, em programação de sistemas, a escolha do alocador pode ter impacto tão grande quanto a escolha do algoritmo. Dominar estratégias de alocação é o que diferencia um programador Rust competente de um excepcional.