Arena allocators

Una arena invierte la pregunta. En lugar de decidir cuándo muere cada objeto, decides cuándo muere el grupo entero, y a cambio asignar cuesta una suma y liberar cuesta una asignación a cero. El resultado no es solo velocidad: es un modelo de propiedad tan pequeño que familias enteras de errores dejan de ser posibles, no porque las evites, sino porque la operación que las causaba ha desaparecido del programa.

La anatomía de un asignador de avance

Una arena mantiene tres datos: la base del bloque, cuánto se ha usado y cuánto cabe. Asignar es alinear el cursor, comprobar que queda sitio y devolver la posición anterior. No hay búsqueda, no hay metadatos por objeto, no hay cabecera de ocho o dieciséis bytes precediendo a cada bloque como en un malloc clásico.

typedef struct {
    unsigned char *base;
    size_t         usado;
    size_t         capacidad;
} Arena;

static inline size_t alinear_arriba(size_t n, size_t a) {
    return (n + a - 1) & ~(a - 1);          // a debe ser potencia de dos
}

void *arena_alloc(Arena *ar, size_t bytes, size_t alineacion) {
    size_t inicio = alinear_arriba(ar->usado, alineacion);
    if (inicio > ar->capacidad || bytes > ar->capacidad - inicio) return nullptr;
    ar->usado = inicio + bytes;
    return ar->base + inicio;
}

#define ARENA_NEW(ar, T, n) \
    ((T *)arena_alloc((ar), sizeof(T) * (n), alignof(T)))

Dos detalles separan esta versión de la ingenua. El primero es la alineación explícita: si repartes bytes crudos sin redondear el cursor, tarde o temprano devolverás una dirección impar para un double o para un vector SIMD, y eso es comportamiento indefinido incluso en arquitecturas que lo toleran en silencio. El segundo es la forma de la comprobación de espacio. Escribir inicio + bytes > capacidad invita al desbordamiento aritmético cuando bytes procede de una entrada externa; restar antes de sumar, como arriba, no puede desbordar porque ambos operandos son magnitudes ya acotadas.

La memoria devuelta no está inicializada. Una arena de propósito general suele ofrecer una variante que llama a memset y otra que no, porque poner a cero un megabyte que vas a sobrescribir inmediatamente es exactamente el tipo de coste invisible que las arenas existen para eliminar.

Marcas de posición y crecimiento

De la disciplina de avance sale gratis un mecanismo poderoso: si el estado de la arena cabe en un size_t, guardarlo y restaurarlo te da regiones temporales anidadas.

typedef struct { Arena *ar; size_t marca; } Temporal;

Temporal temp_inicio(Arena *ar)  { return (Temporal){ ar, ar->usado }; }
void     temp_fin(Temporal t)    { t.ar->usado = t.marca; }

Esto es un asignador de pila construido sobre un asignador de avance, y su coste es literalmente el de copiar y restaurar un entero. Es el patrón de la scratch arena: una función que necesita espacio auxiliar toma una marca al entrar, reparte todo lo que quiera y la restaura al salir, sin que el llamante sepa nada. La regla que lo sostiene es la única disciplina real que una arena impone: ningún puntero obtenido después de la marca puede sobrevivir a su restauración.

Cuando la capacidad se agota hay dos respuestas. La primera es encadenar bloques: la arena guarda un puntero al bloque anterior y pide otro al sistema cuando el actual no da más de sí. Los punteros ya entregados siguen siendo válidos —nada se mueve, jamás—, pero la restauración de marcas se complica porque una marca pasa a ser un par de bloque y desplazamiento.

typedef struct Bloque Bloque;
struct Bloque { Bloque *anterior; size_t usado, capacidad; unsigned char datos[]; };

La segunda respuesta, más elegante en sistemas de 64 bits, consiste en separar reserva de compromiso. Con mmap puedes reservar un rango de direcciones enorme sin respaldarlo con memoria física, y dejar que el sistema asigne páginas solo cuando las tocas.

// Reserva un espacio de direcciones amplio; las paginas se comprometen al usarse.
void *base = mmap(nullptr, 1ull << 34, PROT_READ | PROT_WRITE,
                  MAP_PRIVATE | MAP_ANONYMOUS | MAP_NORESERVE, -1, 0);

Una arena así nunca crece ni se fragmenta: tiene dieciséis gibibytes de espacio virtual, consume solo las páginas que ha escrito y devuelve punteros permanentemente estables. El coste es un fallo de página menor la primera vez que se toca cada página, y la dependencia de que el sistema sobrecomprometa, que es lo habitual en Linux pero no una garantía universal.

flowchart LR
A[Reserva virtual grande] --> B[Cursor avanza]
B --> C[Marca guardada]
C --> D[Region temporal]
D --> E[Restaurar marca]
E --> B
B --> F[Reset total del cursor]
style F fill:#a6e3a1,color:#11111b

Por qué la eligen compiladores y juegos

La afinidad no es casual: ambos dominios tienen ciclos de vida con forma de fase, y la arena es la estructura de datos que representa exactamente esa forma.

Un compilador construye un grafo enorme e intrincado —nodos de sintaxis, tipos, símbolos, representaciones intermedias— con muchísimas aristas cruzadas y ninguna noción clara de propiedad. Averiguar quién libera cada nodo sería un ejercicio de contabilidad inútil, porque todos mueren en el mismo instante: cuando la unidad de traducción termina. Con una arena por unidad, el compilador no escribe una sola llamada a free durante toda la fase de análisis, y el gráfico puede tener tantos ciclos como quiera sin que importe.

Un motor de juego tiene un ciclo aún más nítido. Cada fotograma genera listas de objetos visibles, comandos de dibujo, resultados de colisión y contactos físicos, y absolutamente nada de eso sobrevive al fotograma siguiente. Dos arenas alternadas —una para el fotograma actual y otra para el anterior, intercambiadas al final de cada iteración— cubren incluso el caso de los datos que deben durar exactamente un fotograma más.

Hay un beneficio menos citado y probablemente más importante: la localidad. Los objetos asignados consecutivamente quedan consecutivos en memoria, así que recorrer el grafo en el orden en que se construyó recorre la memoria linealmente y el prebúsqueda del procesador acierta. Un malloc de propósito general dispersa esos mismos nodos por todo el montón, y el coste no aparece en el asignador sino en cada recorrido posterior, donde es mucho más difícil de atribuir a su verdadera causa.

Lo que una arena te quita

Ninguna técnica que compre tanto es gratis, y conviene enunciar el precio sin adornos.

Pierdes la liberación individual. Si un objeto de vida corta se asigna en una arena de vida larga, su memoria queda retenida hasta el reset: eso no es una fuga en el sentido de la memoria inalcanzable, pero el consumo crece igual. Una arena mal dimensionada convierte un patrón de uso normal en un crecimiento monótono que solo se detiene cuando el proceso termina.

Aparece un error nuevo, específico y muy desagradable: el uso tras reset. Un puntero a memoria de arena que sobrevive a la restauración de su marca no apunta a memoria liberada por el sistema, sino a memoria perfectamente válida que pronto contendrá otro objeto. No hay SIGSEGV, no hay corrupción del montón, no hay nada que un depurador convencional señale: solo dos objetos distintos compartiendo bytes.

Peor aún, los detectores automáticos se quedan ciegos. Para AddressSanitizer y para Valgrind, la arena es un único bloque grande y correctísimo; un desbordamiento de un objeto a otro dentro de ella es, desde fuera, una escritura legítima. La contramedida existe y merece la pena en desarrollo: envenenar manualmente la memoria no repartida.

#if defined(__SANITIZE_ADDRESS__) || \
    (defined(__has_feature) && __has_feature(address_sanitizer))
#  include <sanitizer/asan_interface.h>
#  define ARENA_ENVENENAR(p, n)   ASAN_POISON_MEMORY_REGION((p), (n))
#  define ARENA_DESENVENENAR(p, n) ASAN_UNPOISON_MEMORY_REGION((p), (n))
#else
#  define ARENA_ENVENENAR(p, n)    ((void)0)
#  define ARENA_DESENVENENAR(p, n) ((void)0)
#endif

Con eso, la arena vuelve a ser transparente para el sanitizador: cada objeto queda rodeado de bytes envenenados y los desbordamientos entre objetos vecinos reaparecen como errores. Es la práctica estándar en las bases de código serias que usan arenas, y la diferencia entre una técnica profesional y una trampa lenta.