De Double Headed Stack Allocator

Wanneer je "stack allocator" hoort, denk je misschien aan alloca, waarmee je geheugen kunt alloceren van de eigenlijke programmastack. Dat is zeer nuttig in noodgevallen, maar dat is niet waar deze post over gaat. Een andere naam voor het type stack allocator waar we het vandaag over hebben, is een "bump allocator".

De Stack Allocator

Rond 2010 werkte ik bij Surreal Software (Midway Seattle) aan een open-wereldgame genaamd This is Vegas, die helaas werd geannuleerd toen Midway failliet ging.

Binnen dat project was een van mijn taken het programmeren van animaties. De animaties werkten via een state machine voor sets botten, waarbij elke staat een boom van animatie-blends was. Wanneer staten veranderden, blendden ze uit van de oude staat naar de nieuwe staat om de continuïteit te bewaren.

Er vond veel blending plaats, en dit vereiste een groot aantal dynamische geheugenallocaties om deze animaties op de CPU te kunnen evalueren en blenden. Deze allocaties waren echter allemaal tijdelijk (transient) en hoefden slechts voor een deel van de frame te bestaan. Bovendien moesten deze allocaties per frame plaatsvinden, omdat zaken per frame drastisch konden veranderen—zoals welke personages er in dat frame werden geanimeerd, bijvoorbeeld op basis van het camera-frustum. Bij het profileren van dit deel van de code bleek de allocator een "hot spot" (bottleneck) te zijn.

Om dit probleem op te lossen, hebben we een "stack allocator" geïmplementeerd waarbij allocatie simpelweg een optelling van een integer is, en deallocatie zelfs nog goedkoper is.

Om dit te doen, reserveer je een hoeveelheid geheugen die gelijk is aan de maximale hoeveelheid die je nodig zult hebben, bijvoorbeeld 1MB. Dit is je stack. Daarnaast houd je een integer-variabele tos (top of stack) bij om te weten waar de bovenkant van de stack zich bevindt.

Wanneer je geheugen wilt alloceren, is je geheugen het geheugen aan de bovenkant van de stack, en tel je het aantal bytes dat je wilt alloceren op bij de tos-variabele, zodat de volgende allocatie na die van jou komt:

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

In een echte implementatie zou je ook willen weten hoe groot het geheugen is, zodat je kunt afhandelen wanneer de tos het einde van het geheugen bereikt—bijvoorbeeld door null terug te geven, een assert te triggeren of iets anders.

Wanneer je klaar bent met het geheugen, zet je de tos-variabele simpelweg terug op 0:

tos = 0; // dealloceer alle stack-allocaties

In ons geval zetten we de tos op 0 nadat de animatie-blending was voltooid en we de resultaten hadden gekopieerd naar de buffers die naar de vertex shader gingen voor skinning. Als je een stack allocator algemener zou gebruiken voor alle tijdelijke geheugenallocaties tijdens een frame van een game, zou je deze terug kunnen zetten naar 0 aan het begin van elk frame.

Het resultaat was een wereld van verschil. Allocatie nam geen meetbare tijd meer in beslag in de profiler, omdat allocatie een integer-optelling was en het vrijgeven van al het geheugen een enkele integer-toewijzing. Sneller dan dat kan het niet.

Eén ding om op te merken is dat deze allocator, zoals hier geschreven, geen destructoren aanroept. Het gebruik van placement new voor constructoren zou eenvoudig genoeg zijn. Het aanroepen van destructoren is lastiger, omdat dit een handmatig proces zou moeten zijn, wat foutgevoelig is. Je zou een RAII-patroon kunnen gebruiken, maar stack allocators werken het beste voor eenvoudigere typen.

Een ander groot voordeel van stack allocators is dat ze kunnen werken in multi-threaded omgevingen. Als de tos-variabele atomaire optelling gebruikt, kunnen meerdere threads uit dezelfde stack allocator alloceren. Dit is handig in een fork/join-situatie op de CPU, of voor een complex algoritme dat op de GPU draait.

Je kunt met stack allocators ook "gedeeltelijke deallocaties" uitvoeren. Stel dat je een recursief proces hebt waarbij elk niveau dynamische allocatie nodig heeft; je kunt dan onthouden waar de tos stond toen dat niveau begon, en deze terugzetten naar die waarde wanneer dat niveau van verwerking is voltooid.

De Double Headed Stack Allocator

Een paar jaar later werkte ik bij Blizzard in het StarCraft 2-team. Mijn baas, James Anhalt, is een zeer slimme man die me introduceerde bij ShaderToy en verschillende coole technieken met me deelde. Hij vertelde me over double headed stack allocators als oplossing voor een probleem met geheugenfragmentatie waar hij in het verleden tegenaan was gelopen.

Stel je voor dat je een game hebt met een streaming wereld. Terwijl de speler door de wereld loopt, wordt oude level-geometrie gedealloceerd en wordt nieuwe level-geometrie gealloceerd en vanaf de schijf gestreamd.

Tegelijkertijd kan het personage van de speler van vorm veranderen (shape shift). Elke keer dat ze van vorm veranderen, wordt de oude vorm gedealloceerd en wordt de nieuwe vorm gealloceerd en vanaf de schijf gestreamd.

De uitdaging is dat wanneer je deze twee systemen hebt die willekeurige hoeveelheden geheugen alloceren en dealloceren op hun eigen tijdlijnen, het geheugen gefragmenteerd zal raken.

Laten we een simpel voorbeeld nemen. Stel dat je in totaal 100 MB geheugen hebt voor het level (rood) en het personage (groen). Het level alloceert 20 MB, daarna alloceert het personage 30 MB, vervolgens alloceert het level weer 20 MB en alloceert het personage de laatste 30 MB. De allocaties van de leveldata (rood) zijn dus afgewisseld met de allocaties van het personage (groen).

Stel nu dat de speler naar een nieuw gedeelte loopt, waardoor het geheugen van de oude leveldata wordt vrijgegeven. De nieuwe leveldata heeft slechts één allocatie van 30 MB nodig. We hebben wel 40 MB aan vrij geheugen, maar dit is niet in één blok! We hebben slechts twee blokken van 20 MB. Dus, hoewel de nieuwe leveldata kleiner is, kunnen we geen ruimte hiervoor alloceren. Dit is geheugenfragmentatie, en het is een groot probleem in omgevingen met beperkt geheugen.

James vertelde me dat ze in dit soort situaties een blok geheugen gebruikten zoals bij een normale stack allocator, maar dat de leveldata een tos had die omhoog groeide vanaf 0, en de personage-data een tos had die omlaag groeide vanaf het einde van het geheugen. Je wist dat het geheugen op was wanneer ze elkaar kruisten en de level-tos groter was dan de personage-tos.

Dit werkt als volgt:

  1. Leveldata (rood) en personage-allocaties (groen) vullen het geheugen van beide kanten in.
  2. Wanneer leveldata wordt vrijgegeven, blijven alleen de personage-allocaties over aan de rechterkant.
  3. Leveldata kan vervolgens de benodigde 30 MB alloceren door een aparte stack allocator in hetzelfde geheugenblok te behouden. Er is geen sprake van geheugenfragmentatie.

Hierdoor kon het levelgeheugen, wanneer dit moest veranderen, de level-tos terugzetten naar 0 en het benodigde geheugen opnieuw alloceren zonder enige fragmentatie. Op dezelfde manier kon het personage, wanneer het zijn geheugen vrijgaf, de tos terugzetten naar het einde van het geheugen en opnieuw alloceren zonder fragmentatie.

Ook deze allocators werken prima in multi-threaded omgevingen, zelfs als elke thread van beide kanten alloceert. Atomaire optellingen van de tos-indices zijn hiervoor voldoende.

Je vraagt je misschien af: "Waarom niet gewoon twee aparte stack allocators gebruiken in plaats van één double headed?" Het belangrijkste voordeel is wanneer je beperkt geheugen hebt en weet dat de totale grootte van één allocator voldoende is voor beide systemen, maar dat de verhouding tussen de twee flexibel moet zijn. In de beschreven gamesituatie betekent dit dat sommige levels meer geheugen kunnen gebruiken, maar dat in die gevallen het personage minder geheugen moet gebruiken. Het is een enigszins kunstmatig voorbeeld, maar hopelijk is het principe duidelijk.

Variabele objecten opslaan in een eindig gebied

Er is een variatie op dit systeem voor wanneer je een aantal objecten van variabele grootte wilt opslaan in een vaste hoeveelheid geheugen, maar wel random access via een index wilt behouden. Een voorbeeld hiervan is het versturen van netwerkpakketten van een specifieke grootte (voor de efficiëntie), waarbij dit geheugen een variabel aantal netwerkcommando's van variabele grootte moet coderen. Je wilt eenvoudig door de berichten kunnen itereren, maar ze moeten wel verschillende groottes kunnen hebben.

Wat je doet, is een double headed stack allocator gebruiken waarbij de ene stack bedoeld is voor de dynamische allocaties en de andere stack voor een array van integers. Deze integers bevatten de offset in het geheugen naar de dynamische allocaties.

Dit werkt als volgt:

  1. Start met een lege double headed stack allocator.
  2. Je wilt 24 bytes alloceren. Stack 0 heeft een tos van 0, dus daar schrijf je je object van 24 bytes. Je telt 24 op bij de tos van stack 0, waardoor deze nu 24 is (de volgende vrije regio). Tegelijkertijd alloceer je een integer uit stack 1 en schrijf je daar 0 in, als offset voor waar dit eerste item staat.
  3. Vervolgens wil je 14 bytes alloceren. Stack 0 heeft een tos van 24, dus daar schrijf je je object. Je telt 14 op bij de tos van stack 0, waardoor deze nu 38 is. Je alloceert opnieuw een integer uit stack 1 en schrijft daar 24 in, als offset voor dit tweede item.
  4. En zo enzovoort...

Daarnaast moet je op een bepaalde manier bijhouden hoeveel objecten er zijn. Je zou een aparte integer kunnen gebruiken die het aantal offsets in de offset-tabel bijhoudt, of je zou een sentinel-waarde in de offset-tabel kunnen plaatsen om het einde aan te geven (bijvoorbeeld ~0, wat in binair alle enen zijn).

Net als de andere stack allocators kan deze ook in een multi-threaded omgeving werken. Je zou in overweging kunnen nemen om de twee updates transactioneel te maken—bijvoorbeeld met een compare and swap loop—maar dat is niet nodig.

Ten slotte maakt deze configuratie het mogelijk om items te verwijderen of te verplaatsen in het geheugen, wat een andere manier is om fragmentatie te verminderen. Je hoeft alleen de offset-tabel bij te werken om overeen te komen met de nieuwe realiteit.

Bronnen

Een andere korte beschrijving over dit onderwerp is te vinden in de AMD Vulkan memory allocator: Custom Memory Pools - Linear Algorithm