Kontenery STL a pamięć


Zapotrzebowanie na pamięć kontenerów STL

Przy okazji wpisu odnośnie do zadania rekrutacyjnego, wywiązała się dyskusja o klasach std::set oraz std::unordered_set. W tym wpisie zamierzam zbadać zapotrzebowanie pamięciowe powyższych dwóch klas. Aby móc śledzić alokacje dokonywane przez kontener STL, napisałem swój alokator pamięci rr_debug_allocator. Klasa ta dziedziczy po  std::allocator< T > i jedynym jej zadaniem jest wypisywanie na konsole zajmowanych i zwalnianych obszarów pamięci.

Jako punkt odniesienia przedstawiam zapotrzebowanie na pamięć dla kontenerów std::vector oraz std::list.

STL Custom Allocator

Poniżej moja bardzo prymitywna implementacja wrapera na std::allocator< T >.

Logujemy zajmowanie i zwalnianie pamięci. Nie logujemy wywołań konstruktora kopiującego, konstruktora standardowego oraz destruktora.

Aplikacja testowa

Analiza otrzymanych wyników

Logi dla trybu 32 bit

Logi dla trybu 64 bit

Podsumowanie

Na potrzeby podsumowania przyjmuję, że:

  • mamy N elementów do wstawiania,
  • kontenery były tworzone z domyślnymi ustawieniami,
  • kompilator MinGW-w64 (w64 4.0).

std::vector

Element w kontenerze zajmuje dokładnie tyle samo pamięci co element poza kontenerem. W najgorszym przypadku całkowita pamięć zaalokowana przez kontener będzie równa   M = \frac{3}{2}N * sizeof(T)

std::list

Element w kontenerze potrzebuje dwóch wskaźników na kolejny i poprzedni węzeł listy.
  M = 2N * sizeof(void*) + N * sizeof(T)

std::set

Dla każdego elementu kontener tworzy nowy węzeł drzewa. Każdy taki węzeł potrzebuje przechować dwa wskaźniki, przekazaną wartość oraz pewne wartości zależne od implementacji (głębokość obydwu poddrzew potrzebna do balansowania drzewem)
  M = 4N * sizeof(void*) + N * sizeof(T)

std::unordered_set

Wewnętrzna implementacja kontenera std::unordered_set, w mojej wersji gcc, to połączenie klasy vector i list. Każdy element to węzeł listy jednokierunkowej, tyle tylko, że zamiast jednej listy mamy pewną ilość list K. Wartość K jest zależna od ilości elementów w kontenerze, podobnie jak ma to miejsce w klasie vector. Wraz z dodawaniem nowych elementów rozmiar K jest zwiększany.  Przybliżoną wartość dla najgorszego przypadku możemy policzyć następująco.
  M \approx N*sizeof(T) + 3N*sizeof(void*)

Dodaj komentarz

Twój adres email nie zostanie opublikowany.