Principe du stack allocator

Le stack allocator (ou bump allocator) repose sur un bloc de mémoire pré‑alloué – par exemple 1 MiB – et un indice tos (top of stack). Chaque allocation se résume à un addition d’entier qui avance tos de la taille demandée, comme le montre le code :

uint8_t* StackAllocate(uint8_t* mem, size_t& tos, size_t size){
    uint8_t* ret = &mem[tos];
    tos += size;
    return ret;
}

La désallocation globale consiste à remettre tos à zéro : tos = 0;. Dans le cadre d’un moteur de jeu, les allocations temporaires liées à l’animation d’un cadre sont ainsi libérées en un seul write. L’auteur indique que, après implémentation, « l’allocation ne prenait plus aucun temps mesurable dans le profiler », ce qui confirme l’impact nul du coût d’allocation.

Optimisation et contraintes

Ce modèle ne déclenche pas les destructeurs ; il faut recourir à placement new pour les constructeurs et gérer manuellement les destructeurs, ce qui augmente le risque d’erreurs. Le design reste toutefois adapté aux types simples où la libération massive est acceptable. Le même principe s’étend aux environnements multithread : en déclarant tos comme std::atomic<size_t>, chaque thread effectue une addition atomique, garantissant l’absence de contention même lors d’un fork/join CPU ou d’un calcul GPU. De plus, le partial deallocation est possible en sauvegardant la valeur de tos au début d’une récursion et en la restaurant à la fin, évitant ainsi des libérations intermédiaires.

Allocateur double‑tête et gestion de la fragmentation

Lorsque deux sous‑systèmes (par ex. le streaming de niveaux et la transformation de personnage) allouent et libèrent de façon indépendante, la fragmentation apparaît rapidement. L’exemple fourni utilise 100 MiB au total : le niveau consomme 20 MiB, le personnage 30 MiB, puis le niveau 20 MiB et le personnage les 30 MiB restants. Après libération du niveau, 40 MiB restent libres mais répartis en deux blocs de 20 MiB, empêchant une nouvelle allocation de 30 MiB.

La solution consiste à placer deux pointeurs de tête dans le même bloc : le level tos croît depuis l’adresse de base, le character tos décroît depuis la fin du bloc. La condition d’épuisement de mémoire est simplement level_tos > character_tos. Ainsi, chaque sous‑système peut réinitialiser son pointeur (niveau à 0, personnage à la fin) sans créer d’interstices, tout en conservant la flexibilité du partage proportionnel : si un niveau nécessite plus de 50 MiB, le personnage en reçoit moins, mais aucune fragmentation n’apparaît.

Comme pour le stack simple, les deux têtes utilisent des additions atomiques, ce qui rend l’allocateur double‑tête compatible avec le multithreading. Le principal compromis réside dans la nécessité de connaître à l’avance la capacité totale du bloc et d’accepter que la somme des deux usages ne dépasse jamais cette capacité, faute de quoi les deux têtes se croiseraient et déclencheraient un échec d’allocation.