Alokator

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Alexander Stepanov, twórca alokatorów

Alokator – jeden z niskopoziomowych mechanizmów Standardowej Biblioteki Szablonów, wykorzystywany w kontenerach do dynamicznej alokacji oraz zwalniania pamięci. Biblioteka STL definiuje wiele róznych struktur danych, takich jak lista (std::vector) czy zbiór (std::set), powszechnie nazywanych kontenerami. Ich podstawową własnością jest możliwość zmiany rozmiaru w czasie działania programu, podczas której może dojść do dynamicznej alokacji lub dealokacji pamięci. Za przydzielanie i zwalnianie pamięci w takich sytuacjach odpowiedzialne są alokatory. Standardowa biblioteka szablonów definiuje alokatory wykorzystywane domyślnie przez kontenery. Programista może jednak definiować i wstrzykiwać własne[1].

Pomysłodawcą i twórcą alokatorów był Alexander Stepanov, jeden z głównych autorów biblioteki STL. Początkowo ich celem było zwiększenie elastyczności biblioteki oraz uniezależnienie jej od konkretnych modeli pamięci, co pozwoliłoby na wykorzystanie w niej niestandardowych wskaźników oraz referencji. Jednak podczas dyskusji nad włączeniem biblioteki do standardu języka C++, komitet standaryzacyjny zauważył, że w pełni abstrakcyjny model pamięci wiąże się ze znacznym zmniejszeniem wydajności. Aby temu zapobiec, zwiększono wymagania stawiane alokatorom. W efekcie poziom konfiguracji jest dużo mniejszy niż początkowo zakładał Stepanov.

Istnieje wiele różnych scenariuszy w których zdefiniowane przez programistę alokatory bywają przydatne. Jednym z najczęstszych powodów wykorzystywania własnych alokatorów jest próba zwiększenia wydajności alokacji poprzez wykorzystanie puli pamięci (ang. memory pool). Przykładowo programy, które alokują dużą liczbę małych obiektów mogą zyskać wykorzystując własne alokatory, zarówno jeżeli chodzi o szybkość działania jak i całościowe zużycie pamięci. Inną sytuacją jest zapewnienie ograniczenia dostępu do różnych typów pamięci, na przykład pamięci współdzielonej lub odzyskanej przez mechanizm garbage collection.

Historia[edytuj | edytuj kod]

W marcu 1994 roku Aleksander Stepanov oraz Meng Lee zaprezentowali bibliotekę STL komitetowi standaryzacyjnemu C++[2]. Biblioteka została wstępnie zatwierdzona, pomimo tego, że wskazano kilka niedociągnięć. W szczególności nakazano Stepanovowi jak największe uniezależnienie kontenerów od modelu pamięci, co doprowadziło do stworzenia alokatorów. Konsekwencją tej decyzji było wymuszenie przepisania interfejsów kontenerów w taki sposób, aby akceptowały alokatory napisane przez klientów biblioteki.

W celu zadoptowania biblioteki do standardu Stepanov współpracował z kilkoma członkami komitetu standaryzacyjnego, włączając w to Adrew Koeninga oraz Bjarne Stroustrupa, którzy odkryli, że własne alokatory mogą zostać wykorzystane do zaimplementowania kontenerów przechowujących obiekty trwałe[3].

Pierwotnie, projekt stworzenia alokatorów opierał się na cechach języka, które nie zostały jeszcze zaakceptowane przez komitet standaryzacyjny (np. korzystanie z szablonów jako argumentów dla innych szablonów). Ponieważ większość z tych cech nie była zaimplementowana w ówczesnych kompilatorach, Bjarne Stroustroup oraz Andy Koening dokładnie sprawdzali, czy cechy te są wykorzystywane poprawnie[3].

Wymagania dla alokatorów[edytuj | edytuj kod]

Każda klasa, która spełnia wymagania stawiane alokatorom może zostać wykorzystana jako alokator. W szczególności, klasa A, której zadaniem jest alokowanie pamięci dla obiektów typu T musi definiować następujące typy[4]:

  • A::pointer - typ wskaźnika do zaalokowanego obszaru pamięci
  • A::const_pointer - typ stałego wskaźnika do zaalokowanego obszaru pamięci
  • A::reference - typ referencji do zaalokowanego obszaru pamięci
  • A::const_reference - typ stałej referencji do zaalokowanego obszaru pamięci
  • A::value_type - typ obiektu dla którego alokator alokuje pamięć
  • A::size_type - typ mogący przechować rozmiar największego możliwego do zaalokowania obszaru pamięci
  • A::difference_type - typ mogący reprezentować różnicę pomiędzy dwoma dowolnymi wskaźnikami w danym modelu pamięci

Dodatkowo alokator A dla obiektów typu T musi posiadać zdefiniowaną metodę A::pointer A::allocate(size_type n, A<void>::const_pointer hint = 0). Metoda ta zwraca wskaźnik na pierwszy element zaalokowanej tablicy, która jest w stanie pomieścić co najmniej <n> obiektów typu T. Metoda ta alokuje tylko pamięć, nie jest odpowiedzialna za konstrukcje obiektów danego typu. Opcjonalny argument w postaci wskaźnika na pamięć już zaalokowaną przez alokator A może zostać użyty, aby wskazać w jakim obszarze powinna być zrobiona nowa alokacja.

Alokator musi także posiadać zdefiniowaną metodę void A::deallocate(A::pointer p, A::size_type n), która jako parametry przyjmuje wskaźnik zwrócony przez wywołanie metody allocate oraz ilość elemtentów dla których pamięć ma być zdealokowana (bez niszczenia obiektów).

Tworzenie i usuwanie obiektu jest oddzielone od procesu alokacji i dealokacji pamięci. Alokator musi definiować metody A::construct oraz A::destroy, które będzą odpowiedzialnę za tworzenie i usuwanie obiektu. Ich implementacja może wyglądać następująco:

template <typename T> void A::construct(A::pointer p, A::const_reference t) { new ((void*) p) T(t); }

template <typename T> void A::destroy(A::pointer p){ ((T*)p)->~T(); }

Poza tym alokatorem powinien spełniać poniższe wymagania[5]:

  • powinna posiadać domyślny konstruktor oraz destruktor, które nie mogą wyrzucać wyjątków,
  • powinna posiadać dwa konstruktory kopiujące, z których jeden jest szablonem.

Przypisy

  1. Allocators (ang.). [dostęp 2012-06-11].
  2. Prezentacja biblioteki STL. [dostęp 2009-06-02].
  3. 3,0 3,1 Wywiad ze Stepanovem o kontenerach (ang.). [dostęp 2009-06-03].
  4. Allocators (STL) (ang.). [dostęp 2012-06-11].
  5. Artykuł o alokatorach na CodeGuru (ang.). [dostęp 2009-06-05].