Arena Allocators in C

C is een taal op een zeer laag niveau. Dit betekent dat het je toestaat — en in zekere zin ook dwingt — om het geheugen dat je gebruikt zelf te beheren. Dit is een van de redenen waarom veel programmeurs overstappen naar andere talen voor hun dagelijkse werk.

In dit artikel introduceer ik een paradigma voor geheugenbeheer dat niet alleen zeer performant is, maar ook uiterst veelzijdig. Het maakt de taak van het geheugenbeheer aanzienlijk eenvoudiger en vermindert de kans op geheugenlekken met een grote marge. Ik heb het over arena allocators.

Voordat we naar de implementatie kijken, volgt eerst een korte introductie in het concept.

Wat zijn Arena Allocators?

De gebruikelijke manier van geheugenbeheer is dat er telkens wanneer er geheugen nodig is, een kleine hoeveelheid van de heap wordt gereserveerd met malloc — precies de hoeveelheid die op dat moment nodig is. Mocht men er later achter komen dat er meer ruimte nodig is dan oorspronkelijk gepland, dan wordt realloc gebruikt om de grootte van de allocatie te vergroten.

Zodra het geheugen niet meer nodig is, wordt free aangeroepen om het besturingssysteem te laten weten dat dit geheugen weer beschikbaar is voor andere taken.

Hoewel dit werkt, kleven er enkele nadelen aan:

1. Handmatig beheer: De programmeur moet onthouden om het geheugen vrij te geven. Dit is extra riskant bij allocaties in een loop (zoals in games), omdat het besturingssysteem dan steeds meer geheugen toewijst dat nooit wordt vrijgegeven. Aangezien geheugen een eindige bron is, zal het programma uiteindelijk crashen wanneer het systeem geen geheugen meer heeft.
2. Performance: Het herhaaldelijk alloceren en vrijgeven van veel kleine stukjes geheugen is traag.
3. Onduidelijkheid over eigenaarschap: Neem bijvoorbeeld de volgende functie:

i32 *create_array(usize len) {
    i32 *elements = (i32 *)malloc(sizeof(int));
    return elements;
}

Hoe weet de programmeur die deze functie aanroept dat er een geheugenallocatie heeft plaatsgevonden? Men kan dit afleiden uit de naam van de functie, maar dat is niet altijd triviaal. Dit is cruciaal, omdat de programmeur moet weten wanneer het zijn verantwoordelijkheid is om het geheugen vrij te geven.

De Oplossing

Hier komt de arena allocator in beeld. De meeste lifetimes (de duur dat een bepaald gebied in het geheugen wordt gebruikt voordat het wordt vrijgegeven) kunnen worden ingedeeld in een handvol categorieën:

• Geheugen dat gedurende het gehele programma blijft bestaan.
• Geheugen dat bestaat tot het voltooien van een specifieke taak (bijvoorbeeld één frame in een game of het afhandelen van een HTTP-verzoek).
• Geheugen dat alleen binnen de scope van een functie bestaat.

In plaats van veel kleine allocaties, kunnen we één groot blok geheugen reserveren voor objecten met een vergelijkbare levensduur (objecten die samen kunnen worden vrijgegeven).

We hebben dan een groot stuk geheugen tot onze beschikking. Telkens wanneer we een deel van dat geheugen gebruiken, verschuiven we een pointer om bij te houden tot welk punt het geheugen is gebruikt en waar het vrije geheugen begint.

Wanneer de data in dat grote blok niet meer nodig is, kunnen we alles in één keer vrijgeven. Alternatief kunnen we de arena re-initialiseren naar de begintoestand en opnieuw beginnen met alloceren. Dit bespaart individuele allocaties (die traag zijn) en vermindert de zorgen over geheugenbeheer, omdat we alleen nog maar hoeven te letten op een paar grote "chunks" in plaats van talloze kleine fragmenten.

De Implementatie

Verduidelijking: types.c

Voordat we beginnen: ik voeg bijna altijd het volgende bestand toe aan de top van mijn C-code. Dit bestand bevat typedefs voor ingebouwde types en enkele handige utilities. Ik gebruik unity builds voor snellere compilatie, waardoor ik .c-bestanden direct include.

// types.c
#ifndef TYPES_C
#define TYPES_C
#include <stddef.h>
#include <stdint.h>

typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int8_t i8;
typedef int16_t i16;
typedef int32_t i32;
typedef int64_t i64;
typedef float f32;
typedef double f64;
typedef size_t usize;

#define KiB(x) x * 1024
#define MiB(x) KiB(x) * 1024
#define GiB(x) MiB(x) * 1024
#define MIN(a, b) a < b ? a : b
#define MAX(a, b) a > b ? a : b
#endif // TYPES_C

arena.c

Hier volgt de eigenlijke arena-implementatie. We beginnen met de include guards en de nodige libc-headers:

#ifndef ARENA_C
#define ARENA_C
#include "types.c"
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

De definitie van de arena struct:

struct arena {
    void *data;
    usize size;
    usize used;
};

De struct houdt bij hoeveel geheugen er is gebruikt. De size is nodig om te controleren of we de arena overschrijden tijdens het alloceren, en data wijst naar het begin van de arena.

Om een nieuwe arena te maken, gebruiken we de volgende functies en structs:

struct arena_create_out {
    struct arena arena;
    bool success;
};

[[nodiscard]]
struct arena_create_out arena_create(usize size) {
    struct arena_create_out out = {0};
    out.arena.data = malloc(size);
    if (out.arena.data == NULL)
        return out;
    out.arena.size = size;
    out.arena.used = 0;
    out.success = true;
    return out;
}

In plaats van output-parameters te gebruiken, wat ik verwarrend vind en de API intuïtiever maakt, geef ik de voorkeur aan het teruggeven van structs.

Allocatie en Uitlijning (Alignment)

Voor de allocatiefunctie definiëren we eerst een macro voor de uitlijning:

#define ARENA_ALIGN 8

Computers verwerken data die is uitgelijnd op 8 bytes efficiënter. Dit betekent dat het begin van elke nieuwe allocatie een veelvoud van 8 bytes moet zijn. malloc regelt dit normaal gesproken voor ons, maar omdat we nu zelf ruimte reserveren in een reeds gealloceerd blok, moeten we de uitlijning handmatig beheren voor een snellere toegang.

Hier is de allocatiefunctie:

struct arena_alloc_out {
    void *ptr;
    bool success;
};

[[nodiscard]]
struct arena_alloc_out arena_alloc(struct arena *arena, usize size) {
    struct arena_alloc_out out = {0};
    usize alignment = (ARENA_ALIGN - (arena->used % ARENA_ALIGN)) % ARENA_ALIGN;
    out.ptr = arena->data + arena->used + alignment;
    if (out.ptr + size > arena->data + arena->size)
        return out;
    arena->used += size + alignment;
    out.success = true;
    return out;
}

Hier berekenen we hoeveel "padding" er nodig is via de variabele alignment, zodat de volgende allocatie weer op 8 bytes is uitgelijnd. Bij een fout retourneert de functie vroegtijdig, waardoor success (geïnitialiseerd op 0/false) ongewijzigd blijft.

Reallocatie en Opschonen

Ik heb een eenvoudige wrapper gemaakt om de grootte van een allocatie te wijzigen. Deze reserveert simpelweg nieuwe ruimte aan het einde van de arena en kopieert de data. De oude data blijft staan, aangezien individuele allocaties niet kunnen worden vrijgegeven; het is alles of niets.

struct arena_realloc_out {
    void *ptr;
    bool success;
};

[[nodiscard]]
struct arena_realloc_out arena_realloc(struct arena *arena, usize new_size, void *src, usize old_size) {
    struct arena_realloc_out out = {0};
    struct arena_alloc_out alloc_out = arena_alloc(arena, new_size);
    if (!alloc_out.success)
        return out;
    out.ptr = memcpy(alloc_out.ptr, src, MIN(old_size, new_size));
    out.success = true;
    return out;
}

Omdat onze arena de grootte van individuele allocaties niet bijhoudt, moet de gebruiker de old_size apart meegeven.

Tot slot zijn er twee eenvoudige wrappers voor het gemak:

void arena_clear(struct arena *arena) { arena->used = 0; }
void arena_free(struct arena *arena) { free(arena->data); }

Voorbeeld van gebruik

Ik heb een eenvoudige string-bibliotheek geïmplementeerd met twee concepten: een string view en een owned string.

• Een owned string is NUL-terminated en is eigenaar van zijn eigen data (moet gealloceerd en vrijgegeven worden). Deze kan direct worden gewijzigd.
• Een string view bekijkt enkel de data en kan niet direct worden gewijzigd. Dit voorkomt onverwachte wijzigingen wanneer meerdere views naar dezelfde data kijken.

Om een string view om te zetten naar een owned string, moeten we geheugen alloceren en de data kopiëren. We voegen ook een NUL-terminator toe voor compatibiliteit met legacy C-API's. Dit doen we door een arena allocator aan de functie mee te geven:

struct str_view {
    const u8 *data;
    usize len;
};

struct str_owned {
    u8 *data;
    usize len;
};

struct str_view_to_str_owned_out {
    struct str_owned str;
    bool success;
};

[[nodiscard]]
struct str_view_to_str_owned_out str_view_to_str_owned(
    struct arena *arena,
    struct str_view s
) {
    struct str_view_to_str_owned_out out = {0};
    struct arena_alloc_out alloc_out = arena_alloc(arena, s.len + 1);
    if (!alloc_out.success)
        return out;
    out.str.data = alloc_out.ptr;
    memcpy(out.str.data, s.data, s.len);
    out.str.len = s.len;
    out.str.data[out.str.len] = 0;
    out.success = true;
    return out;
}

Dit biedt twee grote voordelen:

1. De aanroeper weet direct dat deze functie geheugen alloceert (omdat de eerste argument een arena-pointer is).
2. De aanroeper bepaalt waar (met welke levensduur) het geheugen wordt gealloceerd.

Omdat de aanroeper de relevante arena doorgeeft, hoeft hij zich geen zorgen te maken over het handmatig vrijgeven van de string. Het geheugen wordt simpelweg vrijgegeven zodra de levenscyclus is voltooid en de arena wordt weggegooid of geleegd.

Conclusie

Ik ben onlangs begonnen met het implementeren van arena's in mijn programmeergewoonten en ik ben zeer tevreden. De winst in developer experience is aanzienlijk.

Ik claim niet expert te zijn en deze implementatie is gebouwd voor persoonlijk gebruik. Het is wellicht niet perfect, maar het dient als een goede introductie om mee te beginnen.

Voor vragen, feedback of inzichten kun je me bereiken via: info@eliasebner.com