Alokator (C++)

W programowaniu komputerowym C++ alokatory są składnikiem standardowej biblioteki C++ . Biblioteka standardowa udostępnia kilka struktur danych , takich jak lista i zestaw , powszechnie nazywanych kontenerami . Wspólną cechą tych kontenerów jest ich zdolność do zmiany rozmiaru w trakcie wykonywania programu . Aby to osiągnąć, zwykle wymagana jest jakaś forma dynamicznej alokacji pamięci . Alokatory obsługują wszystkie żądania alokacji i dezalokacji pamięci dla danego kontenera. Standardowa biblioteka C++ zawiera alokatory ogólnego przeznaczenia, które są używane domyślnie, jednak programista może również dostarczyć alokatory niestandardowe .

Alokatory zostały wynalezione przez Aleksandra Stiepanowa jako część Standardowej Biblioteki Szablonów (STL). Pierwotnie miały one na celu uczynienie biblioteki bardziej elastyczną i niezależną od podstawowego modelu pamięci , umożliwiając programistom wykorzystanie niestandardowych typów wskaźników i odwołań w bibliotece. Jednak w procesie przyjmowania STL do standardu C++ komitet normalizacyjny C++ zdał sobie sprawę, że całkowita abstrakcja modelu pamięci wiązałaby się z niedopuszczalnymi spadkami wydajności . Aby temu zaradzić, wymagania stawiane alokatorom zostały zaostrzone. W rezultacie poziom dostosowania zapewniany przez alokatory jest bardziej ograniczony, niż pierwotnie przewidywał Stiepanow.

Niemniej jednak istnieje wiele scenariuszy, w których pożądane są dostosowane alokatory. Niektóre z najczęstszych powodów pisania niestandardowych alokatorów obejmują poprawę wydajności alokacji przy użyciu pul pamięci i enkapsulację dostępu do różnych typów pamięci, takich jak pamięć współdzielona lub pamięć zbierana bezużytecznie . W szczególności programy z wieloma częstymi alokacjami małych ilości pamięci mogą znacznie skorzystać na wyspecjalizowanych alokatorach, zarówno pod względem czasu działania, jak i rozmiaru pamięci .

Tło

Dalsze informacje: Standardowa biblioteka szablonów

Alexander Stepanov i Meng Lee przedstawili Standardową Bibliotekę Szablonów komitetowi normalizacyjnemu C++ w marcu 1994 roku. Biblioteka została wstępnie zatwierdzona, chociaż poruszono kilka kwestii. W szczególności Stiepanow został poproszony o uniezależnienie kontenerów bibliotecznych od bazowego modelu pamięci , co doprowadziło do stworzenia alokatorów. W związku z tym wszystkie interfejsy kontenerów STL musiały zostać przepisane, aby akceptowały alokatory.

Przystosowując STL do standardowej biblioteki C++ , Stiepanow ściśle współpracował z kilkoma członkami komitetu ds . czas uważany za „ważny i interesujący wgląd”.

Z punktu widzenia przenośności wszystkie specyficzne dla maszyny rzeczy, które odnoszą się do pojęcia adresu, wskaźnika itd., są zamknięte w małym, dobrze zrozumiałym mechanizmie.

— Alex Stepanov , projektant Biblioteki Standardowych Szablonów

Pierwotna propozycja alokatora zawierała pewne cechy językowe, które nie zostały jeszcze zaakceptowane przez komisję, a mianowicie możliwość korzystania z szablonowych argumentów , które same są szablonami. Ponieważ te funkcje nie mogły zostać skompilowane przez żaden istniejący kompilator , według Stiepanowa „było ogromne zapotrzebowanie na czas Bjarne [Stroustrup] i Andy'ego [Koeniga] na próby sprawdzenia, czy używamy tych niezaimplementowanych funkcji prawidłowo." Tam, gdzie biblioteka wcześniej bezpośrednio używała wskaźników i odwołań , teraz odnosiłaby się tylko do typów zdefiniowanych przez alokator. Stiepanow opisał później alokatory w następujący sposób: „Miłą cechą STL jest to, że jedyne miejsce, w którym wspomina się o typach związanych z maszyną (...), jest zawarte w około 16 liniach kodu”.

Chociaż Stiepanow pierwotnie zamierzał, aby alokatory całkowicie obejmowały model pamięci, komitet normalizacyjny zdał sobie sprawę, że takie podejście doprowadzi do niedopuszczalnego spadku wydajności. Aby temu zaradzić, do wymagań alokatora dodano dodatkowe sformułowania. definicje typu alokatora dla wskaźników i powiązanych typów całkowitych są równoważne z definicjami dostarczonymi przez alokator domyślny oraz że wszystkie instancje danego typu alokatora zawsze są równe, co skutecznie zaprzecza pierwotnym celom projektowym dla alokatorów i ograniczenie użyteczności alokatorów przenoszących stan.

Stiepanow skomentował później, że chociaż alokatory „w teorii nie są takim złym [pomysłem] (...) [nie] niestety nie mogą działać w praktyce”. Zauważył, że aby alokatory były naprawdę przydatne, konieczna jest zmiana podstawowego języka w odniesieniu do odniesień .

W rewizji standardu C++ z 2011 r. usunięto słowa łasicy wymagające, aby alokatory danego typu zawsze porównywały równe i używały normalnych wskaźników. Te zmiany sprawiają, że stanowe alokatory są znacznie bardziej przydatne i umożliwiają alokatorom zarządzanie współdzieloną pamięcią poza procesem. Obecnym celem alokatorów jest zapewnienie programiście kontroli nad alokacją pamięci w kontenerach, a nie dostosowywanie modelu adresowego bazowego sprzętu. W rzeczywistości poprawiony standard wyeliminował zdolność alokatorów do reprezentowania rozszerzeń modelu adresowego C++, formalnie (i celowo) eliminując ich pierwotny cel.

Wymagania

Każda klasa spełniająca wymagania alokatora może być użyta jako alokator. W szczególności klasa A zdolna do przydzielania pamięci dla obiektu typu T musi zapewniać typy A::pointer , A::const_pointer , A::reference , A::const_reference i A::value_type do ogólnego deklarowania obiektów i odniesienia (lub wskaźniki) do obiektów typu T . Powinien również zapewniać typ A::size_type , typ bez znaku, który może reprezentować największy rozmiar obiektu w modelu alokacji zdefiniowanym przez A , i podobnie całkę ze znakiem A ::difference_type , która może reprezentować różnicę między dowolnymi dwoma wskaźnikami w model alokacji.

A::pointer i A::const_pointer alokatora są po prostu definicjami typów dla T* i T const* , zachęca się implementatorów bibliotek do obsługi bardziej ogólnych alokatorów.

Alokator A dla obiektów typu T musi mieć funkcję członkowską z podpisem 0 A :: wskaźnik A :: allocate ( size_type n , A < void >:: const_pointer tips = ) . Ta funkcja zwraca wskaźnik do pierwszego elementu nowo przydzielonej tablicy wystarczająco dużej, aby pomieścić n obiektów typu T ; alokowana jest tylko pamięć, a obiekty nie są konstruowane. Co więcej, opcjonalny argument wskaźnika (wskazujący na obiekt już przydzielony przez A ) może być użyty jako wskazówka dla implementacji, gdzie należy przydzielić nową pamięć, aby poprawić lokalność . Jednak implementacja może zignorować argument.

Odpowiednia funkcja członkowska void A::deallocate(A::pointer p, A::size_type n) akceptuje każdy wskaźnik, który został zwrócony z poprzedniego wywołania funkcji składowej A::allocate oraz liczbę elementów do cofnięcia alokacji (ale nie zniszczyć).

Funkcja członkowska A::max_size() zwraca największą liczbę obiektów typu T , które mogą zostać pomyślnie przydzielone przez wywołanie A::allocate ; zwracana wartość to zazwyczaj A::size_type(-1) / sizeof (T) . Ponadto A::address zwraca A::wskaźnik oznaczający adres obiektu, biorąc pod uwagę A::reference .

Budowa i niszczenie obiektów odbywa się niezależnie od alokacji i dezalokacji. Alokator musi mieć dwie funkcje składowe, A::construct i A::destroy (obie funkcje zostały uznane za przestarzałe w C++ 17 i usunięte w C++ 20), które obsługują odpowiednio konstruowanie i niszczenie obiektów. Semantyka funkcji powinna być równoważna z następującą: 

  
          

  
     szablon  <  nazwa typu  T  >  void  A  ::  konstrukcja  (  A  ::  wskaźnik  p  ,  A  ::  const_reference  t  )  {  new  ((  void  *  )  p  )  T  (  t  );  }  szablon  <  nazwa typu  T  >  unieważnienie  A  ::  zniszczenie  (  A  ::  wskaźnik  p  ) {  ((  T  *  )  p  )  ->~  T  ();  }

Powyższy kod używa nowej składni umieszczania i bezpośrednio wywołuje destruktor .

Alokatory powinny być konstruowalne przez kopiowanie . Alokator dla obiektów typu T można zbudować z alokatora dla obiektów typu U . Jeśli alokator A przydziela region pamięci R , to R może zostać zwolniony tylko przez alokator, który porównuje się z A .

Alokatory muszą dostarczyć element członkowski klasy szablonu template < nazwa typu U> struct A::rebind { typedef A<U> other; }; , co daje możliwość uzyskania powiązanego alokatora, sparametryzowanego ze względu na inny typ. Na przykład, biorąc pod uwagę typ alokatora IntAllocator dla obiektów typu int , powiązany typ alokatora dla obiektów typu long można uzyskać przy użyciu IntAllocator::rebind<long>::other .

Alokatory niestandardowe

Jednym z głównych powodów napisania niestandardowego alokatora jest wydajność. Wykorzystanie wyspecjalizowanego niestandardowego alokatora może znacznie poprawić wydajność lub użycie pamięci lub oba te elementy programu. Domyślny alokator używa operatora new do przydzielania pamięci. Jest to często realizowane jako cienka warstwa wokół funkcji alokacji sterty C , które są zwykle optymalizowane pod kątem rzadkiej alokacji dużych bloków pamięci. Takie podejście może dobrze działać w przypadku kontenerów, które w większości przydzielają duże fragmenty pamięci, takie jak vector i deque . Jednak w przypadku kontenerów, które wymagają częstych alokacji małych obiektów, takich jak map i list , użycie domyślnego alokatora jest ogólnie powolne. Inne typowe problemy z malloc to słaba lokalizacja odniesienia i nadmierna fragmentacja pamięci .

Popularnym podejściem do poprawy wydajności jest utworzenie alokatora opartego na puli pamięci . Zamiast przydzielać pamięć za każdym razem, gdy element jest wkładany lub usuwany z kontenera, duży blok pamięci (pula pamięci) jest przydzielany wcześniej, prawdopodobnie podczas uruchamiania programu. Niestandardowy alokator będzie obsługiwał indywidualne żądania alokacji, po prostu zwracając wskaźnik do pamięci z puli. Rzeczywiste cofnięcie alokacji pamięci można odłożyć do czasu okresu istnienia puli pamięci. Przykład alokatorów opartych na puli pamięci można znaleźć w bibliotekach Boost C++ .

Innym realnym zastosowaniem niestandardowych alokatorów jest debugowanie błędów związanych z pamięcią. Można to osiągnąć, pisząc alokator, który przydziela dodatkową pamięć, w której umieszcza informacje debugowania. Taki alokator mógłby służyć do zapewnienia, że ​​pamięć jest przydzielana i zwalniana przez ten sam typ alokatora, a także zapewniać ograniczoną ochronę przed przekroczeniami .

Krótko mówiąc, ten akapit (...) jest przemówieniem Standardu „ Mam marzenie ” dla alokatorów. Dopóki to marzenie nie stanie się rzeczywistością, programiści zaniepokojeni przenośnością będą ograniczać się do niestandardowych alokatorów bez stanu

— Scott Meyers , Skuteczny STL

Temat niestandardowych alokatorów był poruszany przez wielu ekspertów i autorów C++ , w tym Scotta Meyersa w Effective STL i Andrei Alexandrescu w Modern C++ Design . Meyers podkreśla, że ​​C++ 98 wymaga, aby wszystkie instancje alokatora były równoważne, i zauważa, że ​​w efekcie zmusza to przenośne alokatory do braku stanu. Chociaż standard C++ 98 zachęcał implementatorów bibliotek do obsługi stanowych alokatorów, Meyers nazywa odpowiedni akapit „cudownym sentymentem”, który „nie oferuje prawie nic”, określając ograniczenie jako „drakońskie”.

Z drugiej strony, w The C++ Programming Language , Bjarne Stroustrup argumentuje, że „najwyraźniej [d]rakońskie ograniczenie informacji o obiektach w alokatorach nie jest szczególnie poważne”, wskazując, że większość alokatorów nie potrzebuje stanu i ma lepsze wydajność bez tego. Wspomina o trzech przypadkach użycia niestandardowych alokatorów, a mianowicie alokatorów puli pamięci , alokatorów pamięci współużytkowanej i alokatorów pamięci zbieranej bezużytecznie . Przedstawia implementację alokatora, która wykorzystuje wewnętrzną pulę pamięci do szybkiego przydzielania i zwalniania małych fragmentów pamięci, ale zauważa, że ​​taka optymalizacja może być już wykonana przez alokator dostarczony przez implementację.

Stosowanie

Podczas tworzenia instancji jednego ze standardowych kontenerów alokator jest określany za pomocą argumentu szablonu , który domyślnie ma std::allocator<T> : 

  
           
 przestrzeń nazw  std  {  szablon  <  klasa  T  ,  alokator  klasy  =  alokator  <  T  >  >  wektor  klasy  ;  // ...

kontenerów bibliotek standardowych z różnymi argumentami alokatora są odrębnymi typami . Funkcja oczekująca argumentu std::vector<int> zaakceptuje zatem tylko instancję wektora z domyślnym alokatorem.

Udoskonalenia alokatorów w C++11

Standard C++ 11 udoskonalił interfejs alokatora, aby umożliwić alokatory o „zakresie”, dzięki czemu kontenery z „zagnieżdżonymi” alokacjami pamięci, takimi jak wektor łańcuchów lub mapa list zestawów typów zdefiniowanych przez użytkownika, mogą zapewnić, że wszystkie pamięć jest pobierana z alokatora kontenera.

Przykład 

 
  
  

 


	 
	 
	   


 

	    

 

	    


          
	
		
			  
			     
			    
				
					  
				
		
	  
		
			     
		



 


	   
			   

	 
	   

	




	    
	   

	  
	   

	 0
 #include  <iostream>  używając  przestrzeni nazw  std  ;  używając  przestrzeni nazw  __gnu_cxx  ;  class  Wymagana alokacja  {  public  :  Wymagana alokacja  ();  ~  Wymagana alokacja  ();  std  ::  basic_string  <  char  >  s  =  "Witaj świecie!  \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  <<  wszystko  ->  max_size  ()  <<  endl  ;  for  (  auto  &  e  :  t  ->  s  )  {  cout  <<  e  ;  }  }  catch  (  std  ::  bad_alloc  &  e  )  {  cout  <<  e  .  co  ()  <<  endl  ;  }  }  int  main  ()  {  __gnu_cxx  ::  new_allocator  <  Wymagana alokacja  >  *  all  =  new  __gnu_cxx  ::  new_allocator  <  Wymagana alokacja  >  ();  Wymagana alokacja  t  ;  pustka  *  pt  =  &  t  ;  /**  * Co się dzieje, gdy new nie może znaleźć magazynu do przydzielenia? Domyślnie alokator zgłasza   wyjątek bad_alloc standardowej biblioteki  *  /  unsigned  int  size  =  1073741824  ;  alloc  (  wszystko  ,  rozmiar  ,  &  pt  ,  &  t  );  rozmiar  =  1  ;  alloc  (  wszystko  ,  rozmiar  ,  &  pt  ,  &  t  );  powrót  ;  }

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Allocator_(C%2B%2B)&oldid=1106694697 ”