Custom Arena Allocators

The Problem with General-Purpose Allocators

In systems where performance is paramount, every CPU cycle and memory access matters. The standard library's malloc and free are marvels of engineering, designed to be general-purpose and work for any allocation pattern. However, this flexibility comes at a cost.

malloc must search for a free block of memory that fits the requested size, manage complex data structures to track free and used blocks, and handle multi-threading with locks. This can lead to:

• Performance Overhead: The logic inside malloc/free is non-trivial. In a hot loop, these calls can become a significant bottleneck.
• Memory Fragmentation: Over time, the heap can become a patchwork of small, free blocks separated by allocated blocks. This makes it hard to find large contiguous chunks of memory and hurts data locality.
• Poor Cache Performance: Related data allocated at different times might end up scattered across memory, leading to frequent cache misses as the CPU has to fetch data from different locations in main memory.
• Complex Lifetime Management: You must perfectly pair every malloc with a free, which becomes a major source of bugs (memory leaks, use-after-free, double-frees) in complex programs.

The following flowchart provides a high-level comparison of the standard heap allocator versus two custom strategies: the memory pool and the arena allocator we are about to build. Notice the complexity of the "Traditional Heap" path compared to the simple "Bump" and "Return" of the arena.

The Arena: A Simpler, Faster Approach

An arena allocator (also known as a linear or region-based allocator) operates on a simple principle. Instead of managing individual blocks, it works with a single, large, pre-allocated region of memory.

1. Allocation: It maintains a pointer or offset indicating the next available address. An allocation is simply a "bump" of this pointer by the requested size. This is an extremely fast, O(1) operation.
2. Deallocation: Individual objects cannot be freed. Instead, the entire arena is freed at once by resetting the pointer back to the beginning.

This strategy is perfect for objects that share a similar lifetime. For example, all memory needed to process a single web request, render a single frame in a game, or, in our case, build a temporary data structure for a search query.

To understand this philosophy, it's helpful to think of an arena as a "user-space stack". Ryan Fleury's talk, "Enter The Arena," provides an excellent explanation of this concept.

Implementing an Arena Allocator

Now, let's get our hands dirty and implement a practical arena allocator. We will add the necessary files to the project you created in the last lesson and integrate it into our hnsw_core library.

The article "Memory Allocation Strategies - Part 2" by gingerBill provides a clear, step-by-step guide that we will follow.

Step 1: Project Setup

First, create the new files for our allocator within your hnsw_from_scratch project structure:

hnsw_from_scratch/
├── ...
└── src/
    ├── arena.c          <-- NEW FILE
    ├── arena.h          <-- NEW FILE
    ├── CMakeLists.txt
    ├── hnsw.c
    └── main.c

We also need a public header in the include directory. Let's create arena.h there as well.

hnsw_from_scratch/
├── include/
│   └── hnsw_from_scratch/
│       ├── arena.h      <-- NEW FILE
│       └── hnsw.h
└── ...

Step 2: Header File (include/hnsw_from_scratch/arena.h)

This file will contain the public interface for our allocator. It defines the Arena struct and the function prototypes that users of our library will interact with.

#ifndef HNSW_ARENA_H
#define HNSW_ARENA_H




#include <stddef.h>
#include <stdint.h>

// Arena struct holds the state of the allocator.
typedef struct Arena {
    unsigned char *buf; // The backing memory buffer.
    size_t buf_len;     // The total length of the buffer.
    size_t curr_offset; // The current offset into the buffer (where the next allocation will start).
    size_t prev_offset; // The offset of the previous allocation.
} Arena;

// Initializes an arena with a pre-allocated backing buffer.
void arena_init(Arena *a, void *backing_buffer, size_t backing_buffer_length);

// Allocates a block of memory from the arena with a specified alignment.
void *arena_alloc_align(Arena *a, size_t size, size_t align);

// Allocates memory with a default alignment.
void *arena_alloc(Arena *a, size_t size);

// Resets the arena, effectively "freeing" all memory allocated from it.
void arena_free_all(Arena *a);




#endif // HNSW_ARENA_H

Step 3: Implementation File (src/arena.c)

This is where the magic happens. We will implement the functions declared in our header. The code is adapted from the gingerBill article.

#include "hnsw_from_scratch/arena.h"
#include <assert.h>
#include <string.h> // For memset




#ifndef DEFAULT_ALIGNMENT
#define DEFAULT_ALIGNMENT (2 * sizeof(void *))
#endif

void arena_init(Arena *a, void *backing_buffer, size_t backing_buffer_length) {
    a->buf = (unsigned char *)backing_buffer;
    a->buf_len = backing_buffer_length;
    a->curr_offset = 0;
    a->prev_offset = 0;
}

// Helper to check if a number is a power of two. Alignment must be a power of two.
static inline int is_power_of_two(uintptr_t x) {
    return (x & (x - 1)) == 0;
}

// Aligns a pointer forward to the nearest address that is a multiple of 'align'.
static inline uintptr_t align_forward(uintptr_t ptr, size_t align) {
    assert(is_power_of_two(align));

    uintptr_t p = ptr;
    uintptr_t a = (uintptr_t)align;
    uintptr_t modulo = p & (a - 1); // Same as p % a, but faster for power of 2

    if (modulo != 0) {
        // If 'p' is not aligned, push it forward to the next alignment boundary.
        p += a - modulo;
    }
    return p;
}

void *arena_alloc_align(Arena *a, size_t size, size_t align) {
    // Align the current offset to the specified alignment.
    uintptr_t curr_ptr = (uintptr_t)a->buf + (uintptr_t)a->curr_offset;
    uintptr_t offset = align_forward(curr_ptr, align);
    offset -= (uintptr_t)a->buf; // Change to a relative offset.

    // Check if there's enough space in the buffer.
    if (offset + size <= a->buf_len) {
        void *ptr = &a->buf[offset];
        a->prev_offset = offset;
        a->curr_offset = offset + size;

        // Zero the allocated memory by default.
        memset(ptr, 0, size);
        return ptr;
    }

    // Not enough memory.
    return NULL;
}

// Convenience wrapper for default alignment.
void *arena_alloc(Arena *a, size_t size) {
    return arena_alloc_align(a, size, DEFAULT_ALIGNMENT);
}

void arena_free_all(Arena *a) {
    a->curr_offset = 0;
    a->prev_offset = 0;
}

Step 4: Update CMakeLists.txt

Now, we need to tell CMake about our new arena.c file. Modify your src/CMakeLists.txt to include it in the hnsw_core library definition.

src/CMakeLists.txt:

# Define a library target named 'hnsw_core' from its source files.
add_library(hnsw_core 
    hnsw.c
    arena.c   # <-- ADD THIS LINE
)




# Specify the include directories for the 'hnsw_core' target.
target_include_directories(hnsw_core
    PUBLIC
        ${PROJECT_SOURCE_DIR}/include
)




# Define an executable target named 'hnsw_app' from the source file main.c.
add_executable(hnsw_app main.c)




# Link our executable against our library.
target_link_libraries(hnsw_app PRIVATE hnsw_core)

Step 5: Using the Arena in main.c

Finally, let's modify src/main.c to test our new allocator. We'll allocate a backing buffer using malloc, initialize our arena with it, allocate a small struct from the arena, and then clean up.

src/main.c:

#include "hnsw_from_scratch/hnsw.h"
#include "hnsw_from_scratch/arena.h"
#include <stdio.h>
#include <stdlib.h> // For malloc and free

// A simple test struct
typedef struct {
    int id;
    double value;
    char name[16];
} TestStruct;

int main(void) {
    say_hello_from_library();

    // 1. Create a backing buffer for the arena. 1 megabyte.
    size_t arena_size = 1024 * 1024;
    void* arena_buffer = malloc(arena_size);
    if (!arena_buffer) {
        fprintf(stderr, "Failed to allocate memory for arena.\n");
        return 1;
    }

    // 2. Initialize the arena.
    Arena my_arena;
    arena_init(&my_arena, arena_buffer, arena_size);
    printf("Arena initialized with %zu bytes.\n", arena_size);

    // 3. Allocate an object from the arena.
    printf("Allocating TestStruct from arena...\n");
    TestStruct* my_struct = (TestStruct*)arena_alloc(&my_arena, sizeof(TestStruct));

    if (my_struct) {
        // Use the allocated memory
        my_struct->id = 123;
        my_struct->value = 3.14;
        snprintf(my_struct->name, 16, "TestObject");

        printf("Struct allocated at address %p\n", (void*)my_struct);
        printf("Struct content: id=%d, value=%f, name='%s'\n", my_struct->id, my_struct->value, my_struct->name);
        printf("Arena current offset: %zu\n", my_arena.curr_offset);
    } else {
        fprintf(stderr, "Arena allocation failed.\n");
    }

    // 4. "Free" all allocations by resetting the arena.
    arena_free_all(&my_arena);
    printf("Arena has been reset. Current offset: %zu\n", my_arena.curr_offset);
    
    // 5. Free the backing buffer itself.
    free(arena_buffer);
    printf("Backing buffer has been freed.\n");

    return 0;
}

Now, compile and run the project from your build directory:

cmake ..
make
./src/hnsw_app

You should see output confirming that the arena was initialized, the struct was allocated, and the arena was successfully reset.

Conclusion

Congratulations, you have just implemented a fundamental tool for high-performance C programming. By moving away from malloc, you've taken direct control over a critical aspect of your program's performance profile.

Here are the key takeaways from this lesson:

• Standard malloc/free can be slow due to fragmentation, search algorithms, and synchronization overhead.
• An arena allocator offers a simple, powerful alternative by using a large, pre-allocated memory region.
• Allocations from an arena are O(1) "bump-pointer" operations, making them extremely fast.
• Deallocation is also O(1): the entire arena is reset at once, which simplifies lifetime management for groups of objects.
• Memory alignment is not just a theoretical concept; it is crucial for performance on modern hardware, and a good custom allocator must handle it correctly.

In the next lesson, we will introduce Valgrind, a powerful tool for memory debugging. We will use it to analyze our project, confirm that our arena allocator correctly manages its backing buffer without leaks, and learn how to detect common memory errors like invalid reads/writes. This will add another layer of robustness to our low-level C development skills.