Allokator (C++)

I C++ datorprogrammering är allokatorer en komponent i C++ Standard Library . Standardbiblioteket tillhandahåller flera datastrukturer , såsom list och set , vanligtvis kallade containrar . Ett vanligt drag bland dessa behållare är deras förmåga att ändra storlek under körningen av programmet . För att uppnå detta krävs vanligtvis någon form av dynamisk minnesallokering . Allokatorer hanterar alla förfrågningar om allokering och avallokering av minne för en given behållare. C++ Standard Library tillhandahåller allokatorer för allmänna ändamål som används som standard, men anpassade allokatorer kan också tillhandahållas av programmeraren .

Allokatorer uppfanns av Alexander Stepanov som en del av Standard Template Library (STL). De var ursprungligen avsedda som ett sätt att göra biblioteket mer flexibelt och oberoende av den underliggande minnesmodellen , vilket gör det möjligt för programmerare att använda anpassade pekare och referenstyper med biblioteket. Men i processen att införa STL i C++-standarden insåg C++-standardiseringskommittén att en fullständig abstraktion av minnesmodellen skulle medföra oacceptabla prestationspåföljder . För att råda bot på detta gjordes kraven på fördelningsorganen mer restriktiva. Som ett resultat är nivån av anpassning som tillhandahålls av allokatorer mer begränsad än vad Stepanov ursprungligen hade tänkt sig.

Ändå finns det många scenarier där skräddarsydda allokatorer är önskvärda. Några av de vanligaste anledningarna till att skriva anpassade allokatorer inkluderar att förbättra prestanda för tilldelningar genom att använda minnespooler och kapsla in åtkomst till olika typer av minne, som delat minne eller skräpsamlat minne. I synnerhet program med många frekventa tilldelningar av små mängder minne kan dra stor nytta av specialiserade allokatorer, både när det gäller körtid och minnesfotavtryck .

Bakgrund

Ytterligare information: Standardmallbibliotek

Alexander Stepanov och Meng Lee presenterade standardmallbiblioteket för C++- standardkommittén i mars 1994. Biblioteket fick ett preliminärt godkännande, även om några frågor togs upp. I synnerhet ombads Stepanov att göra biblioteksbehållarna oberoende av den underliggande minnesmodellen , vilket ledde till skapandet av allokatorer. Följaktligen var alla STL-containergränssnitt tvungna att skrivas om för att acceptera allokatorer.

Vid anpassningen av STL för att inkluderas i C++ Standard Library arbetade Stepanov nära med flera medlemmar av standardkommittén, inklusive Andrew Koenig och Bjarne Stroustrup , som observerade att anpassade allokatorer potentiellt skulle kunna användas för att implementera beständiga lagrings -STL-behållare, som Stepanov på tiden betraktas som en "viktig och intressant insikt".

Ur portabilitets synvinkel är alla maskinspecifika saker som relaterar till begreppet adress, pekare och så vidare inkapslade i en liten, välförstådd mekanism.

— Alex Stepanov , designer av standardmallbiblioteket

Det ursprungliga fördelningsförslaget innehöll några språkegenskaper som ännu inte hade godkänts av kommittén, nämligen möjligheten att använda mallargument som i sig själva är mallar. Eftersom dessa funktioner inte kunde kompileras av någon befintlig kompilator fanns det, enligt Stepanov, "en enorm efterfrågan på Bjarne [Stroustrup] och Andy [Koenig]s tid för att försöka verifiera att vi använde dessa icke-implementerade funktioner korrekt." Där biblioteket tidigare hade använt pekar- och referenstyper direkt, skulle det nu endast hänvisa till de typer som definierats av allokatorn. Stepanov beskrev senare allokatorer enligt följande: "En trevlig egenskap hos STL är att den enda plats som nämner de maskinrelaterade typerna (...) är inkapslad inom ungefär 16 rader kod."

Medan Stepanov ursprungligen hade avsett allokatorer att helt kapsla in minnesmodellen, insåg standardkommittén att detta tillvägagångssätt skulle leda till oacceptabla effektivitetsförsämringar. För att råda bot på detta lades ytterligare formuleringar till fördelningskraven. Speciellt kan containerimplementeringar anta att allokatorns typdefinitioner för pekare och relaterade integraltyper är likvärdiga med de som tillhandahålls av standardallokatorn, och att alla instanser av en given allokatortyp alltid jämförs lika, vilket effektivt motsäger de ursprungliga designmålen för allokatorer och begränsa användbarheten av allokatorer som bär tillstånd.

Stepanov kommenterade senare att även om tilldelare "inte är en så dålig [idé] i teorin (...) så kan de tyvärr inte fungera i praktiken". Han observerade att för att göra allokatorer verkligen användbara, var en förändring av kärnspråket med avseende på referenser nödvändig.

års revidering av C++-standarden tog bort vesslaorden som kräver att allokatorer av en given typ alltid jämför lika och använder normala pekare. Dessa ändringar gör tillståndsstyrda allokatorer mycket mer användbara och tillåter allokatorer att hantera delat minne som inte är i processen. Det nuvarande syftet med allokatorer är att ge programmeraren kontroll över minnesallokering inom behållare, snarare än att anpassa adressmodellen för den underliggande hårdvaran. Faktum är att den reviderade standarden eliminerade allokatorernas förmåga att representera tillägg till C++-adressmodellen, vilket formellt (och medvetet) eliminerade deras ursprungliga syfte.

Krav

Vilken klass som helst som uppfyller allokeringskraven kan användas som allokator. I synnerhet måste en klass A som kan allokera minne för ett objekt av typ T tillhandahålla typerna A::pointer , A::const_pointer , A::reference , A::const_reference och A::value_type för att generiskt deklarera objekt och referenser (eller pekare) till objekt av typen T . Den bör också tillhandahålla typ A::size_type , en osignerad typ som kan representera den största storleken för ett objekt i allokeringsmodellen som definieras av A , och på liknande sätt en signerad integral A::difference_type som kan representera skillnaden mellan två valfria pekare i fördelningsmodellen.

Även om en överensstämmande standardbiblioteksimplementering tillåts anta att allokatorns A::pointer och A::const_pointer helt enkelt är typdefs för T* och T const* , uppmuntras biblioteksimplementatorer att stödja mer allmänna allokatorer.

En allokator, A , för objekt av typen T måste ha en medlemsfunktion med signaturen 0 A :: pointer A :: allocate ( size_type n , A < void >:: const_pointer hint = ) . Denna funktion returnerar en pekare till det första elementet i en nyligen allokerad array som är tillräckligt stor för att innehålla n objekt av typen T ; endast minnet är allokerat, och objekten är inte konstruerade. Dessutom kan ett valfritt pekarargument (som pekar på ett objekt som redan allokerats av A ) användas som en ledtråd till implementeringen om var det nya minnet ska allokeras för att förbättra lokaliteten . Implementeringen är dock fri att ignorera argumentet.

Motsvarande void A::deallocate(A::pointer p, A::size_type n) medlemsfunktion accepterar alla pekare som returnerades från ett tidigare anrop av A::allocate member-funktionen och antalet element som ska avallokeras (men inte destruera).

A ::max_size()- medlemsfunktionen returnerar det största antalet objekt av typen T som kan förväntas bli framgångsrikt allokerat genom en anrop av A::allocate ; värdet som returneras är vanligtvis A::size_type(-1) / sizeof (T) . Dessutom returnerar funktionen A:: adressmedlem en A::pekare som anger adressen till ett objekt, givet en A::referens .

Objektkonstruktion och destruktion utförs separat från allokering och deallokering. Allokatorn måste ha två medlemsfunktioner, A::construct och A::destroy (båda funktionerna har föråldrats i C++17 och tagits bort i C++20), som hanterar objektkonstruktion respektive destruktion. Funktionernas semantik bör motsvara följande: 

  
          

  
     mall  <  typnamn  T  >  void  A  ::  konstruktion  (  A  ::  pointer  p  ,  A  ::  const_reference  t  )  {  new  ((  void  *  )  p  )  T  (  t  );  }  mall  <  typnamn  T  >  void  A  ::  förstöra  (  A  ::  pointer  p  ){  ((  T  *  )  p  )  ->~  T  ();  }

Ovanstående kod använder placeringens ny syntax och anropar förstöraren direkt.

Tilldelare bör kunna kopieras . En allokator för objekt av typ T kan konstrueras från en allokator för objekt av typ U . Om en allokator, A , allokerar en minnesregion, R , så kan R endast deallokeras av en allokator som jämför lika med A .

Tilldelare krävs för att tillhandahålla en mallklassmedlemsmall < typnamn U> struct A::rebind { typedef A<U> other; }; , vilket möjliggör möjligheten att erhålla en relaterad allokator, parametrerad i termer av en annan typ. Till exempel, givet en allokeringstyp IntAllocator för objekt av typen int , kan en relaterad allokeringstyp för objekt av typen long erhållas med IntAllocator::rebind<long>::other .

Anpassade fördelare

En av de främsta anledningarna till att skriva en anpassad allokator är prestanda. Att använda en specialiserad anpassad allokator kan avsevärt förbättra programmets prestanda eller minnesanvändning, eller båda. Standardallokatorn använder operator new för att allokera minne. Detta implementeras ofta som ett tunt lager runt C -högallokeringsfunktionerna , som vanligtvis är optimerade för sällsynt allokering av stora minnesblock. Det här tillvägagångssättet kan fungera bra med behållare som oftast allokerar stora minnesbitar, som vektor och deque . Men för behållare som kräver frekventa tilldelningar av små objekt, som karta och lista , är det vanligtvis långsamt att använda standardallokatorn. Andra vanliga problem med en malloc -baserad allokator inkluderar dålig referenslokalitet och överdriven minnesfragmentering .

Ett populärt sätt att förbättra prestanda är att skapa en minnespoolbaserad allokator. Istället för att allokera minne varje gång ett objekt sätts in eller tas bort från en behållare, allokeras ett stort minnesblock (minnespoolen) i förväg, eventuellt vid starten av programmet. Den anpassade allokatorn kommer att betjäna individuella allokeringsförfrågningar genom att helt enkelt returnera en pekare till minnet från poolen. Faktisk avallokering av minne kan skjutas upp tills livslängden för minnespoolen tar slut. Ett exempel på minnespoolbaserade allokatorer finns i Boost C++ Libraries .

En annan användbar användning av anpassade allokatorer är för att felsöka minnesrelaterade fel. Detta kan uppnås genom att skriva en allokator som allokerar extra minne där den placerar felsökningsinformation. En sådan allokator skulle kunna användas för att säkerställa att minnet allokeras och avallokeras av samma typ av allokator, och även ge begränsat skydd mot överskridningar .

Kort sagt, denna paragraf (...) är standardens " Jag har en dröm "-tal för tilldelare. Tills den drömmen blir vanlig verklighet kommer programmerare som är oroade över portabilitet att begränsa sig till anpassade allokatorer utan tillstånd

— Scott Meyers , effektiv STL

Ämnet anpassade allokatorer har behandlats av många C++ -experter och författare, inklusive Scott Meyers i Effective STL och Andrei Alexandrescu i Modern C++ Design . Meyers betonar att C++98 kräver att alla instanser av en allokator är likvärdiga, och noterar att detta i praktiken tvingar bärbara allokatorer att inte ha tillstånd. Även om C++98-standarden uppmuntrade biblioteksimplementatorer att stödja statliga allokatorer, kallar Meyers den relevanta paragrafen "en härlig känsla" som "ger dig nästan ingenting", och karakteriserar begränsningen som "drakonisk".

I The C++ Programming Language hävdar Bjarne Stroustrup å andra sidan att den "uppenbarligen [d]rakoniska begränsningen mot per-objekt information i allokatorer inte är särskilt allvarlig", och påpekar att de flesta allokatorer inte behöver stat, och har bättre prestanda utan det. Han nämner tre användningsfall för anpassade allokatorer, nämligen minnespoolallokatorer , delade minnesallokatorer och skräpinsamlade minnesallokatorer. Han presenterar en allokeringsimplementering som använder en intern minnespool för snabb allokering och avallokering av små bitar av minne, men noterar att en sådan optimering redan kan utföras av allokatorn som tillhandahålls av implementeringen.

Användande

När en av standardbehållarna instansieras specificeras allokatorn genom ett mallargument , som som standard är std::allocator<T> : 

  
           
 namnområde  std  {  mall  <  klass  T  ,  klass  Allokator  =  allokator  <  T  >  >  klassvektor  ;  _  // ...

Liksom alla C++-klassmallar är instansieringar av standardbiblioteksbehållare med olika allokeringsargument distinkta typer . En funktion som förväntar sig ett std::vector<int> -argument kommer därför bara att acceptera en vektor instansierad med standardallokatorn.

Förbättringar av allokatorer i C++11

C ++11 -standarden har förbättrat allokeringsgränssnittet för att tillåta "scoped" allokatorer, så att behållare med "kapslade" minnesallokeringar, såsom vektor av strängar eller en karta över listor med uppsättningar av användardefinierade typer, kan säkerställa att alla minne hämtas från containerns allokator.

Exempel 

 
  
  

 


	 
	 
	   


 

	    

 

	    


          
	
		
			  
			     
			    
				
					  
				
		
	  
		
			     
		



 


	   
			   

	 
	   

	




	    
	   

	  
	   

	 0
 #include  <iostream>  med  namnutrymme  std  ;  använder  namnutrymmet  __gnu_cxx  ;  class  RequiredAllocation  {  public  :  RequiredAllocation  ();  ~  RequiredAllocation  ();  std  ::  basic_string  <  char  >  s  =  "hej världen!  \n  "  ;  };  RequiredAllocation  ::  RequiredAllocation  ()  {  cout  <<  "RequiredAllocation::RequiredAllocation()"  <<  endl  ;  }  RequiredAllocation  ::~  RequiredAllocation  ()  {  cout  <<  "RequiredAllocation::~RequiredAllocation()"  <<  endl  ;  }  void  alloc  (  __gnu_cxx  ::  new_allocator  <  RequiredAllocation  >*  all  ,  unsigned  int  size  ,  void  *  pt  ,  RequiredAllocation  *  t  ){  try  {  all  ->  allocate  (  size  ,  pt  );  cout  <<  alla  ->  max_size  ()  <<  endl  ;  for  (  auto  &  e  :  t  ->  s  )  {  cout  <<  e  ;  }  }  catch  (  std  ::  bad_alloc  &  e  )  {  cout  <<  e  .  vad  ()  <<  endl  ;  }  }  int  main  ()  {  __gnu_cxx  ::  new_allocator  <  RequiredAllocation  >  *  all  =  new  __gnu_cxx  ::  new_allocator  <  RequiredAllocation  >  ();  RequiredAllocation  t  ;  void  *  pt  =  &  t  ;  /**  * Vad händer när nya inte hittar någon butik att tilldela? Som standard skickar allokatorn ett standard   -library bad_alloc-undantag (för ett alternativ, se §11.2.4.1) *  @C Bjarne Stroustrup C++-programmeringsspråket  */  unsigned  int  size  =  1073741824  ;  alloc  (  alla  ,  storlek  ,  &  pt  ,  &  t  );  storlek  =  1  ;  alloc  (  alla  ,  storlek  ,  &  pt  ,  &  t  );  återvända  ;  }

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Allocator_(C%2B%2B)&oldid=1106694697 "