Allocator (C++)

Alexander Stepanov, de persoon die de invoering van allocatoren binnen C++ sterk heeft bevorderd.

In C++ programmering zijn allocatoren (Engels: allocators) een belangrijk onderdeel van de C++ Standaardbibliotheek. Deze softwarebibliotheek biedt een aantal gegevensstructuren, zoals lijsten en verzamelingen, meestal aangeduid als containers. Tijdens uitvoering van het programma kunnen deze containers hun grootte aanpassen. Daartoe is doorgaans een vorm van dynamische geheugentoewijzing vereist. Allocatoren behandelen alle aanvragen voor het toewijzen en het vrijmaken van geheugen voor een container. Voor algemene doeleinden biedt de C++ Standaardbibliotheek allocatoren die standaard worden gebruikt. Programmeurs kunnen desgewenst ook op maat gemaakte allocatoren definiëren en bouwen.

Het idee van allocatoren werden uitgewerkt door Alexander Stepanov als onderdeel van de Standard Template Library (STL). Allocatoren waren oorspronkelijk bedacht als een middel om deze bibliotheek flexibel en onafhankelijk van het onderliggende geheugenmodel te maken. Zij moesten programmeurs in staat stellen op binnen de STL op maat gemaakte pointer- en referentietypen te gebruiken. In het beslissingsproces hoe STL binnen de C++-standaard moest worden ingepast, realiseerde de C++-standaardisatiecommissie zich echter dat een volledige abstractie van het geheugenmodel tot een onaanvaardbaar verlies aan performance zou leiden. Om dit te verhelpen werden er restrictievere eisen aan allocatoren gesteld. Als gevolg daarvan werd de mate van aanpasbaarheid van allocatoren binnen C++ een stuk beperkter dan wat Stepanov oorspronkelijk voor ogen had gestaan.

Toch zijn er tal van scenario's denkbaar waarin het gebruik van op maat gedefinieerde allocatoren wenselijk is. Enkele van de meest voorkomende redenen voor het definiëren van op maat gedefinieerde allocatoren zijn onder meer het verbeteren van de performance door gebruik te maken van geheugenpools en het inkapselen van de toegang tot verschillende soorten geheugen, zoals gedeeld geheugen of garbage collectiongeheugen. In het bijzonder kunnen programma's waarin op zeer frequente basis kleine hoeveelheden geheugen worden gealloceerd en weer vrijgegeven veel baat hebben bij op maat gedefinieerde allocatoren, zowel in termen van de looptijd van het programma (runtime) als ook wat betreft haar "geheugenfootprint".

Achtergrond

In maart 1984 presenteerden Alexander Stepanov en Meng Lee de Standard Template Library aan het C++ standaardcomité. De bibliotheek kreeg een voorlopige goedkeuring, hoewel er wel een aantal kwesties aan de orde werden gesteld. In het bijzonder werd Stepanov gevraagd om de bibliotheek-containers onafhankelijk van het onderliggende geheugenmodel te implementeren. Dit leidde tot de creatie van allocatoren. Bijgevolg moesten alle STL-containerinterfaces worden herschreven om deze allocatoren te accepteren.

In het aanpassen van STL om te worden opgenomen in de C++ Standaard Bibliotheek werkte Stepanov nauw samen met verschillende leden van het standaardcomité, daaronder Andrew Koenig en Bjarne Stroustrup. Zij observeerden dat maatwerkallocatoren mogelijk zouden kunnen worden gebruikt om persistente opslag van STL-containers te implementeren, wat Stepanov op dat moment als een "belangrijk en interessant inzicht" beschouwde.

Vanuit het oogpunt van portabiliteit zijn alle machinespecifieke zaken, die betrekking hebben op de notie van adressen, pointers, en ga zo maar door, in een klein, goed begrepen mechanisme ingekapseld. -Alex Stepanov, de ontwerper van de Standard Template Library

Het oorspronkelijke allocatorvoorstel behelste ook een aantal taalfuncties, die nog niet door het comité waren aangenomen, namelijk de mogelijkheid om template-argumenten te gebruiken, die zelf templates waren. Aangezien deze functies niet door enige bestaande compiler kon worden gecompileerd, was er volgens Stepanov, "een enorme vraag naar Bjarne Stroustrups en Andy Koenigs tijd om te proberen te verifiëren dat wij deze niet-geïmplementeerde features wel correct gebruikten." Waar de bibliotheek eerder direct gebruik had gemaakt van pointers en referentietypen, zou het nu alleen nog aan de typen refereren die door de allocatoren werden gedefinieerd. Stepanov beschreef allocatoren als volgt: "Een leuke feature van STL is dat de enige plek waar de machine-gerelateerde typen (...) genoemd worden in ongeveer 16 regels code is ingekapseld."

Hoewel Stepanov allocatoren oorspronkelijk bedoeld had om het onderliggende geheugenmodel volledig in te kapselen, realiseerde de standaardcommissie zich dat deze aanpak tot een onaanvaardbare degradatie van de efficiency zou leiden. Om dit probleem te verhelpen werd er een extra formulering aan de allocatoreisen toegevoegd. In het bijzonder mogen containerimplementaties ervan uitgaan dat de type-definities (typedefs) van de allocator voor pointers en verwante integrale typen gelijkwaardig zijn aan die waar de standaardallocator in voorziet. Ook moeten alle instanties van een bepaald allocatortype altijd gelijk vergelijken. Dit is effectief in tegenspraak met de oorspronkelijke ontwerpdoelen voor allocatoren.

Stepanov schreef later dat hoewel allocatoren "in theorie niet zo'n slecht idee zijn (...) zij jammer genoeg in de praktijk niet kunnen werken". Hij beweert dat om allocatoren echt nuttig te maken een wijziging in de kerntaal met betrekking tot referenties nodig was.

Externe links

• (en) CodeGuru: Allocators (STL).
• (en) "C++ Standard Allocator, An Introduction and Implementation". Inleidend artikel.