Dynamic Data Structures and Arena Allocation

Building dynamic data structures — linked lists, trees, hash tables — requires frequent small heap allocations. Each `malloc` call has overhead: the allocator must find a free block, possibly lock a mutex in multi-threaded code, and write bookkeeping information. For performance-sensitive code that creates and destroys many small objects, this overhead can be significant. An arena (also called a region or bump allocator) is a simple allocation strategy that addresses this. You allocate one large block upfront, then serve individual allocations by bumping a pointer forward within that block. Freeing individual objects is O(1) — or simply not done. When you're finished with all the objects in the arena, you free the entire block in a single call. This pattern is ideal for compilers, parsers, and request-scoped allocation in servers. Another approach is a memory pool: pre-allocate a fixed number of same-sized objects and keep a free list of unused slots. Allocating from the pool and returning to it are both O(1) and involve no system calls after the initial setup. Memory pools eliminate fragmentation entirely for uniform objects and are commonly used in embedded systems, game engines, and OS kernels where predictability matters more than flexibility.

Example

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

/* ---- Simple linear arena allocator ---- */
typedef struct {
    uint8_t *base;
    size_t   used;
    size_t   capacity;
} Arena;

Arena arena_create(size_t capacity)
{
    Arena a;
    a.base     = malloc(capacity);
    a.used     = 0;
    a.capacity = capacity;
    return a;
}

void *arena_alloc(Arena *a, size_t size)
{
    /* Align to 8 bytes */
    size = (size + 7) & ~(size_t)7;
    if (a->used + size > a->capacity) return NULL;
    void *ptr = a->base + a->used;
    a->used  += size;
    return ptr;
}

void arena_free(Arena *a)
{
    free(a->base);
    a->base     = NULL;
    a->used     = 0;
    a->capacity = 0;
}

typedef struct { int x, y; } Point;

int main(void)
{
    Arena arena = arena_create(1024);
    if (!arena.base) { perror("malloc"); return EXIT_FAILURE; }

    Point *points[10];
    for (int i = 0; i < 10; i++) {
        points[i] = arena_alloc(&arena, sizeof(Point));
        points[i]->x = i;
        points[i]->y = i * i;
    }

    printf("Arena used: %zu / %zu bytes\n", arena.used, arena.capacity);
    for (int i = 0; i < 10; i++)
        printf("  (%d, %d)\n", points[i]->x, points[i]->y);

    arena_free(&arena);  /* free everything in one shot */
    printf("Arena freed.\n");
    return EXIT_SUCCESS;
}

HTML

Full Editor

Related Resources

C Reference

Complete tag & property list

C How-To Guides

Step-by-step practical guides

C Exercises

Practice what you've learned