Moduł FreeList

Nagłówek: FreeList.hpp
Elementy modułu: FreeList Module

Moduł FreeList rozszerza przestrzeń nazw common o dwa szablony klas - common::FreeList oraz common::DynamicFreeList. Obiekty tych klas to napisane we własnym zakresie alokatory przeznaczone do alokowania dużych ilości zmiennych jednego wybranego typu, które działają znacząco szybciej niż standardowe operatory new i delete.

FreeList nadają się dobrze wszędzie tam, gdzie często trzeba alokować i zwalniać różne drobiazgi (niekoniecznie małe rozmiarem, bo działają szybciej zarówno dla małych jak i dużych elementów), na przykład struktury cząsteczek czy węzły drzewa BSP.

Zalety:

• Znacząco szybsza alokacja i zwalnianie obiektów.
• Poprawiona Spatial Locality of Reference - lepsze wykorzystanie cache.

Wady:

• Trzeba utworzyć FreeList i korzystać z niej przy alokacji i zwalnianiu.
• Z powodu rezerwowania całych dużych bloków pamięci część pamięci się marnuje.

Rodzaje FreeList

Są dwie klasy. Po utworzeniu ich obiektów dalsza obsługa wygląda już tak samo.

1. Klasa common::FreeList Rezerwuje jeden blok o podanej liczbie elementów i jest to maksymalna liczba elementów, jakie można z jej użyciem zaalokować. Konstruktor:
   FreeList(uint Capacity);
2. Klasa common::DynamicFreeList Zarządza całą kolekcją zarezerwowanych bloków o podanym rozmiarze (liczbie elementów w jednym bloku), potrafi rezerwować nowe, a także zwalniać te kompletnie nieużywane (oczywiście z pewną histerezą). Konstruktor:
   DynamicFreeList(uint BlockCapacity);

Obsługa

#include "Base.hpp"
#include "FreeList.hpp"
using namespace common;

Utworzenie listy:
  FreeList<int> L(1024);
  DynamicFreeList<int> L(1024);

Alokacja domyślnym konstruktorem:
(typy atomowe zostają niezainicjalizowane)
  int *p = L.New();
Alokacja jawnie wywołanym domyślnym konstruktorem:
(typy atomowe zostają zainicjalizowane zerem)
  int *p = L.New_ctor();
Alokacja z wywołaniem konstruktora z parametrami:
(istnieją wersje dla 1, 2, 3, 4, 5 parametrów)
  int *p = L.New(123);

Zwolnienie pamięci:
(pamięć musi być przydzielona wcześniej z puli tej listy)
  L.Delete(p);

Sprawdzanie stanu i statystyki - metody:
- IsEmpty, IsFull
- GetUsedCount, GetFreeCount, GetCapacity, GetUsedSize itd...

Uwagi

Przed ususnięciem obiektu listy zwolnione muszą być wszystkie zaalokowane z jej użyciem elementy. Jest to sprawdzane za pomocą asercji.

Każda z wersji metod do alokacji New ma też wersję o nazwie TryNew, która w przypadku błędu (brak miejsca w bloku pamięci) nie rzuca wyjątku std::bad_alloc jak tamte, tylko zwraca NULL.

Wydajność

Pomiar dla 10240 losowych alokacji lub zwolnień (90% szansa na alokację, 10% na zwolnienie, na końcu zwolnienie pozostałych zmiennych):

DEBUG:
Element typu int:
  FreeList : 68.0636 ms
  DynamicFreeList : 184.441 ms
  new i delete : 78.8142 ms
Element typu zajmujacego 1024 bajty:
  FreeList : 69.3896 ms
  DynamicFreeList : 203.506 ms
  new i delete : 93.2942 ms
RELEASE:
Element typu int:
  FreeList : 7.87224 ms
  DynamicFreeList : 11.4786 ms
  new i delete : 17.0348 ms
Element typu zajmujacego 1024 bajty:
  FreeList : 9.18059 ms
  DynamicFreeList : 18.0729 ms
  new i delete : 24.0537 ms