Arena y Pool Allocators: gestión de memoria de alto rendimiento

Cuando diseñas sistemas de alto rendimiento, malloc suele ser tu enemigo. Aunque es un generalista versátil, su diseño para cubrir todos los casos de uso introduce un overhead de metadatos por cada asignación (cabeceras para el tamaño, punteros a bloques contiguos, etc.) y un tiempo de ejecución no determinista debido a la búsqueda de huecos en el heap. Para evitar esto, implementamos estrategias donde nosotros tomamos el control de la memoria.

Un Arena Allocator (o bump allocator) consiste en un bloque de memoria contiguo donde la asignación es tan simple como incrementar un puntero (offset) hacia adelante. Es extremadamente rápido ($O(1)$) y ofrece una localidad de caché excelente, pero tiene una limitación crítica: no puedes liberar objetos individuales; solo puedes resetear la arena completa, lo cual es ideal para datos con el mismo ciclo de vida, como el estado de un frame en un motor de videojuegos o un árbol de sintaxis en un compilador.

Por otro lado, el Pool Allocator está diseñado para gestionar múltiples objetos de tamaño idéntico. En lugar de buscar huecos, mantiene una lista libre (free list) de bloques disponibles. Si necesitas un bloque, lo sacas de la lista; si lo devuelves, lo reinsertas. Esto garantiza un tiempo de ejecución $O(1)$ tanto para la asignación como para la liberación, sin fragmentación externa, siendo perfecto para nodos de estructuras de datos dinámicas como listas o colas de mensajes.

Si implementas estas técnicas para ganar velocidad pero fallas en el alineamiento (alignment), provocarás un error de bus o un degradado de rendimiento masivo. Si usas una arena para objetos con ciclos de vida distintos, acabarás con un consumo de memoria insostenible porque no podrás reutilizar el espacio intermedio.

#define _POSIX_C_SOURCE=200809L
#include <stdio.h>
#include <stdint.h>
#include <stddef.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

/* Arena Allocator: Gestión por región */
typedef struct {
    uint8_t *base;
    size_t offset;
    size_t capacity;
} Arena;

/* Pool Allocator: Gestión de bloques de tamaño fijo */
typedef struct PoolNode {
    struct PoolNode *next;
} PoolNode;

typedef struct {
    void *memory;
    PoolNode *free_list;
    size_t block_size;
    size_t capacity;
} Pool;

/* Alinea un puntero según el requerimiento de la CPU */
static inline uintptr_t align_up(uintptr_t addr, size_t align) {
    return (addr + (uintptr_t)(align - 1)) & ~(uintptr_t)(align - 1);
}

/* Arena: Asignación de un bloque con alineación garantizada */
void* arena_alloc(Arena *a, size_t size, size_t align) {
    uintptr_t current_ptr = (uintptr_t)a->base + a->offset;
    uintptr_t aligned_ptr = align_up(current_ptr, align);
    size_t new_offset = (size_t)(aligned_ptr - (uintptr_t)a->base) + size;

    if (new_offset > a->capacity) {
        return NULL; // Out of memory en la arena
    }

    a->offset = new_offset;
    return (void *)aligned_ptr;
}

void arena_reset(Arena *a) {
    a->offset = 0;
}

/* Pool: Inicialización de la lista libre */
bool pool_init(Pool *p, void *mem, size_t block_size, size_t capacity) {
    // El tamaño del bloque debe ser al menos el tamaño de un puntero
    size_t actual_block_size = (block_size < sizeof(PoolNode)) ? sizeof(PoolNode) : block_size;
    
    p->memory = mem;
    p->block_size = actual_block_size;
    p->capacity = capacity;
    p->free_list = (PoolNode *)mem;

    // Encadenamos todos los bloques inicialmente
    PoolNode *curr = p->free_list;
    for (size_t i = 0; i < capacity - 1; i++) {
        uintptr_t next_ptr = (uintptr_t)curr + actual_block_size;
        curr->next = (PoolNode *)next_ptr;
        curr = curr->next;
    }
    curr->next = NULL; // Fin de la lista
    return true;
}

void* pool_alloc(Pool *p) {
    if (p->free_list == NULL) return NULL;

    void *ptr = p->free_list;
    p->free_list = p->free_list->next;
    return ptr;
}

void pool_free(Pool *p, void *ptr) {
    if (!ptr) return;
    // Reinsertamos el bloque al inicio de la lista libre
    PoolNode *node = (PoolNode *)ptr;
    node->next = p->free_list;
    p->free_list = node;
}

typedef struct {
    double x, y;
    int id;
} Entity;

int main(void) {
    // --- Escenario Arena ---
    // Ideal para datos temporales de un parser o un frame de juego
    size_t arena_size = 4096;
    uint8_t *arena_mem = malloc(arena_size);
    if (!arena_mem) return 1;

    Arena frame_arena = { .base = arena_mem, .offset = 0, .capacity = arena_size };

    Entity *e1 = arena_alloc(&frame_arena, sizeof(Entity), _Alignof(Entity));
    if (e1) {
        e1->id = 1; e1->x = 10.5; e1->y = 20.5;
        printf("Arena: Entity %d asignada en %p\n", e1->id, (void*)e1);
    }

    // Resetear la arena es O(1), limpia todo de golpe
    arena_reset(&frame_arena);
    printf("Arena reseteada. Offset actual: %zu\n", frame_arena.offset);

    // --- Escenario Pool ---
    // Ideal para miles de entidades pequeñas de mismo tamaño
    size_t num_entities = 10;
    size_t pool_mem_size = num_entities * sizeof(Entity);
    void *pool_mem = malloc(pool_mem_size);
    if (!pool_mem) { free(arena_mem); return 1; }

    Pool entity_pool;
    pool_init(&entity_pool, pool_mem, sizeof(Entity), num_entities);

    Entity *entities[num_entities];
    for (int i = 0; i < 5; i++) {
        entities[i] = pool_alloc(&entity_pool);
        if (entities[i]) entities[i]->id = i;
    }

    printf("Pool: Asignadas 5 entidades. El resto está en la lista libre.\n");
    
    // Liberamos una entidad de forma aleatoria (O(1))
    pool_free(&entity_pool, entities[2]);
    printf("Pool: Entidad 2 liberada. Reutilizable inmediatamente.\n");

    Entity *reused = pool_alloc(&entity_pool);
    printf("Pool: Nueva asignación (reutilizando %p)\n", (void*)reused);

    // Limpieza final
    free(arena_mem);
    free(pool_mem);
    return 0;
}

Desglose del funcionamiento

En la arena_alloc, la clave reside en align_up. No podemos simplemente sumar el tamaño; si el offset actual apunta a una dirección que no es múltiplo de 8 y queremos guardar un double, la CPU podría lanzar una excepción de alineación o perder ciclos en operaciones de lectura/escritura no alineadas. Usamos un masking de bits (addr + (align - 1)) & ~(align - 1) que es una operación extremadamente eficiente para asegurar que el puntero resultante respete la arquitectura.

En la pool_init, aplicamos un truco de gestión de memoria clásica: aprovechamos el espacio del propio bloque libre para guardar el puntero al siguiente bloque disponible. El PoolNode es una estructura que no consume espacio adicional porque “vive” dentro del bloque que está esperando a ser asignado. Cuando llamas a pool_alloc, simplemente mueves el cabecero de la free_list al siguiente nodo. Cuando llamas a pool_free, el bloque liberado se convierte en el nuevo cabecero de la lista, insertándose al principio para mantener la operación en $O(1)$.

El error frecuente

Un error crítico con los Pool Allocators es ignorar el tamaño mínimo de los bloques. Si intentas implementar un pool para estructuras de tamaño muy pequeño, por ejemplo, un char, el puntero next de la free_list desbordará la memoria del bloque y corromperá el bloque adyacente. Como hemos visto en pool_init, siempre debemos asegurar que block_size sea al menos sizeof(PoolNode). Herramientas como AddressSanitizer (ASan) detectarán este desbordamiento inmediatamente al intentar escribir el puntero de la lista libre.

N° 130