Les 4 allocateurs que tout développeur C devrait connaître

malloc est un outil généraliste. Il gère des blocs de taille arbitraire, dans n’importe quel ordre, avec libération individuelle. Cette flexibilité a un coût : métadonnées par bloc, fragmentation, appels système sous-jacents (brk, mmap), verrous internes pour la sécurité multi-fils.

Sur un benchmark de 1 million d’allocations, un allocateur bump termine en 4,31 ms là où malloc met 87,52 ms. Pas parce que malloc est mal écrit – la glibc est excellente – mais parce qu’il résout un problème plus général que celui dont tu as besoin.

Voici quatre allocateurs spécialisés, du plus simple au plus complet. Chacun sacrifie une capacité de malloc en échange de performances ou de simplicité.

1. Bump allocator (allocateur linéaire)

Principe : un gros bloc de mémoire, un pointeur qui avance. Chaque allocation déplace le pointeur. Pas de libération individuelle – tout est libéré d’un coup à la fin.

typedef struct {
    unsigned char *buffer;
    size_t capacity;
    size_t offset;
} BumpAllocator;

void *bump_allocate(BumpAllocator *allocator, size_t size, size_t alignment) {
    size_t aligned_offset = (allocator->offset + alignment - 1) & ~(alignment - 1);
    if (aligned_offset + size > allocator->capacity) return NULL;
    void *pointer = allocator->buffer + aligned_offset;
    allocator->offset = aligned_offset + size;
    return pointer;
}

void bump_reset(BumpAllocator *allocator) {
    allocator->offset = 0;
}

Le paramètre alignment garantit que le pointeur retourné est correctement aligné pour le type demandé (typiquement _Alignof(type) ou 16 pour un usage générique). Sans cet alignement, les accès à des types comme double ou des structures provoquent un comportement indéfini sur certaines architectures.

Coût : une addition, un masquage et une comparaison par allocation. Pas de métadonnées, pas de liste libre, pas de fragmentation.

Cas d’usage : traitement par lots. Tu alloues tout ce dont tu as besoin pour traiter une requête, un fichier, une image – puis tu réinitialises l’allocateur et tu recommences. C’est le schéma “allouer, traiter, tout libérer”.

Limite : impossible de libérer un bloc individuel. Si tu as besoin de libérer le troisième bloc sur dix, le bump allocator ne convient pas.

Performance : 4,31 ms pour 1 million d’allocations, contre 87,52 ms pour malloc. Le facteur 20x vient de l’absence totale de comptabilité interne.

2. Pool allocator (allocateur par bassin)

Principe : un bloc de mémoire découpé en cellules de taille fixe. Une liste chaînée relie les cellules libres. Allouer prend la première cellule libre, libérer la remet en tête de liste.

typedef struct PoolFreeNode {
    struct PoolFreeNode *next;
} PoolFreeNode;

typedef struct {
    unsigned char *buffer;
    size_t cell_size;
    size_t cell_count;
    PoolFreeNode *free_list;
} PoolAllocator;

void *pool_allocate(PoolAllocator *allocator) {
    if (!allocator->free_list) return NULL;
    PoolFreeNode *node = allocator->free_list;
    allocator->free_list = node->next;
    return node;
}

void pool_deallocate(PoolAllocator *allocator, void *pointer) {
    PoolFreeNode *node = pointer;
    node->next = allocator->free_list;
    allocator->free_list = node;
}

Coût : une opération sur pointeur par allocation et par libération. O(1) garanti, pas de fragmentation possible (toutes les cellules font la même taille).

Cas d’usage : quand tu gères beaucoup d’objets de même taille – nœuds d’un arbre, entrées d’une table, connexions réseau, entités d’un moteur de jeu. bc-duplicate utilise un pool allocator pour ses entrées de fichiers : chaque entrée fait exactement la même taille, des centaines de milliers sont allouées et libérées pendant l’exécution.

Limite : une seule taille de bloc. Si tu as besoin de blocs de 32 octets ET de blocs de 256 octets, il te faut deux pools séparés (ou un autre allocateur).

3. Free-list allocator (allocateur à liste libre)

Principe : comme malloc, mais simplifié. Un bloc de mémoire, une liste chaînée de zones libres de tailles variables. À chaque allocation, on parcourt la liste pour trouver un bloc assez grand. À chaque libération, on remet le bloc dans la liste et on fusionne les blocs adjacents.

typedef struct FreeBlock {
    size_t size;
    struct FreeBlock *next;
} FreeBlock;

typedef struct {
    unsigned char *buffer;
    size_t capacity;
    FreeBlock *free_list;
} FreeListAllocator;

void *freelist_allocate(FreeListAllocator *allocator, size_t size) {
    FreeBlock *previous = NULL;
    FreeBlock *current = allocator->free_list;

    while (current) {
        if (current->size >= size) {
            if (previous)
                previous->next = current->next;
            else
                allocator->free_list = current->next;
            return (unsigned char *)current + sizeof(FreeBlock);
        }
        previous = current;
        current = current->next;
    }
    return NULL;
}

void freelist_deallocate(FreeListAllocator *allocator, void *pointer) {
    FreeBlock *block = (FreeBlock *)((unsigned char *)pointer - sizeof(FreeBlock));
    block->next = allocator->free_list;
    allocator->free_list = block;
}

L’allocation parcourt la liste (stratégie premier ajustement ici) et retourne le premier bloc assez grand. La libération remet le bloc en tête de liste. Cette version minimale ne découpe pas les blocs et ne fusionne pas les voisins – une implémentation complète ajouterait ces deux opérations pour limiter la fragmentation.

Coût : O(n) dans le pire cas (n = nombre de blocs libres). Plus lent que le bump et le pool, mais permet de libérer n’importe quel bloc individuellement.

Cas d’usage : quand tu as besoin de blocs de tailles différentes avec libération individuelle, mais que tu veux éviter malloc (par exemple pour contrôler la mémoire totale consommée, ou pour éviter les appels système). Les moteurs de jeux utilisent souvent un free-list pour les ressources dont la durée de vie est imprévisible.

Limite : fragmentation. Avec le temps, la mémoire se découpe en petits blocs inutilisables. Les stratégies de fusion (coalescing) atténuent le problème mais ne l’éliminent pas. C’est exactement le même problème que malloc résout avec des arenas, des bins et des mmap de secours.

4. Arena allocator (allocateur par arène)

Principe : un bump allocator qui sait grandir. Quand le bloc courant est plein, l’arena alloue un nouveau bloc et continue. La libération reste collective : on libère tous les blocs d’un coup.

typedef struct ArenaBlock {
    unsigned char *buffer;
    size_t capacity;
    size_t offset;
    struct ArenaBlock *next;
} ArenaBlock;

typedef struct {
    ArenaBlock *current;
    size_t default_block_size;
} ArenaAllocator;

L’allocation fonctionne comme un bump. Si le bloc courant n’a plus de place, un nouveau bloc est chaîné et devient le bloc courant. La réinitialisation parcourt la chaîne et libère ou réinitialise chaque bloc.

Coût : presque identique au bump – une addition et une comparaison par allocation, plus rarement une allocation de bloc. L’amortissement est excellent.

Cas d’usage : c’est l’allocateur le plus polyvalent des quatre. Il combine la vitesse du bump avec la capacité de grandir sans limite prédéterminée. bc-duplicate l’utilise pour stocker les chemins de fichiers : chaque chemin a une longueur différente, le nombre total n’est pas connu à l’avance, et tous sont libérés en même temps à la fin du traitement.

Les compilateurs utilisent massivement les arenas : chaque phase (analyse lexicale, syntaxique, génération de code) alloue dans son arena, puis tout est libéré à la fin de la phase.

Limite : comme le bump, pas de libération individuelle. Et la chaîne de blocs peut gaspiller de la mémoire si la taille des blocs est mal calibrée (trop petits = trop d’allocations système, trop grands = mémoire inutilisée).

Quand utiliser quoi

Le vrai message

Ces quatre allocateurs ne remplacent pas malloc. Ils le complètent. malloc reste le bon choix quand tu ne connais pas tes schémas d’allocation à l’avance, quand la portabilité compte, quand le code est appelé par des tiers qui s’attendent à free().

Mais dans ton propre code, dans les boucles critiques, dans les chemins où tu alloues des milliers d’objets par seconde – connaître ces alternatives te donne le choix. Et le choix, en C, c’est la raison pour laquelle tu as choisi ce langage.

Le code source complet de ces quatre allocateurs est disponible sur GitHub sous licence MIT.