Warsztat.GDCompo!ProjektyMediaArtykułyQ&AForumOferty pracyPobieranie

Opisz napotkaną sytuację, a redakcja niezwłocznie znajdzie rozwiązanie!

wyślij anuluj

Szybki alokator FreeList

Wstęp

Artykuł przedstawia klasy służące do szybkiej alokacji pamięci z zarezerwowanej wcześniej puli, wykorzystujące ideę listy wolnych komórek (ang. Free List). Omawia szczegóły implementacji tych klas oraz prezentuje wyniki testu ich wydajności w porównaniu ze standardową alokacją pamięci new i delete. Do jego zrozumienia wymagana jest dobra znajomość programowania w C++.

Wprowadzenie

Pamięć przydzielamy dynamicznie - w czasie działania programu - za pomocą operatora new (lub funkcji malloc), a zwalniamy za pomocą operatora delete (lub funkcji free). To oczywista rzecz. W życiu programisty gier przychodzi jednak taka chwila, kiedy trzeba dowiedzieć się, że alokowanie pamięci ze sterty nie jest idealne - ma kilka wad. Te wady ujawniają się szczególnie wtedy, kiedy do utworzenia jest dużo małych bloków.

  1. Alokacja pamięci jest wolna.Oczywiście nie trwa tak długo, jak otwieranie pliku dyskowego, ale jednak wymaga od systemu operacyjnego wielu obliczeń. Jeśli chcesz przydzielić na raz tysiące bloków pamięci albo planujesz wiele alokacji w każdej klatce gry, to ten czas może mieć znaczenie.
  2. Część pamięci może się marnować.Nie jestem specem od spraw niskopoziomowych, więc nie potrafię powiedzieć jak jest na pewno, ale możemy się domyślać, że system potrzebuje wraz z każdym zaalokowanym blokiem zająć dodatkową pamięć na jakieś swoje metadane na jego temat albo też wyrównuje rozmiar przydzielonego bloku do całkowitej wielokrotności 2, 4 czy może 4096 bajtów :) Szczegóły zależą od konkretnej platformy i systemu operacyjnego.
  3. Słabe wykorzystanie pamięci podręcznej. Dostęp do pamięci jest trochę wolniejszy niż obliczenia na procesorze. Procesor jest więc wyposażony w pamięć podręczną Cache, w której przechowuje ostatnio używane dane. Jednak buforowane są w niej nie pojedyncze bajty, tylko całe bloki pamięci. Dlatego odwołanie pod jakiś adres powoduje, że odwołanie pod adresy sąsiednie będzie z dużym prawdopodobieństwem szybsze. Jeśli natomiast skaczemy po różnych, osobno zaalokowanych blokach pamięci, to wykorzystanie pamięci podręcznej jest słabe i spada wydajność.

Rozwiązaniem tych problemów jest napisanie własnego mechanizmu przydzielania pamięci. Będzie to klasa, która zaalokuje jeden duży blok pamięci na całą pulę elementów, a alokacja elementu z jej pomocą będzie polegała na zwróceniu wskaźnika do wybranego miejsca z tego bloku. Wewnętrznie można to prosto zrealizować przechowując listę łączoną jednokierunkową wolnych komórek - stąd właśnie pochodzi angielska nazwa Free List. Po szczegóły na temat tej koncepcji odsyłam do artykułów [1] i [2], na których oparłem swoją implementację.

Przydzielanie bloków pamięci z jednej dużej puli wydaje się trudne i takie jest faktycznie, ale dla pewnego szczególnego przypadku można go radykalnie uprościć. Ten przypadek to alokowanie elementów tylko jednego typu, a więc o znanym, zawsze jednakowym rozmiarze. Dlatego omówione tu klasy będą szablonami parametryzowanymi typem T elementów, które będą zdolne alokować, a rozmiar takiego elementu wynosi zawsze sizeof(T).

Implementacja alokatora

Przejdźmy do rzeczy. Wszystko co omówię w tym artykule to tak naprawdę kod z pliku FreeList.hpp. Możesz ten plik pobrać i wykorzystywać w swoich programach - jest gotowy do użycia, korzysta tylko z biblioteki standardowej C/C++ i udostępniam go na licencji Public Domain. Składają się na niego dwa szablony klas - FreeList i DynamicFreeList. W tym rozdziale omówię pierwszy z nich.

Obiekt klasy FreeList alokuje w konstruktorze, a zwalnia w destruktorze duży blok pamięci, z którego może udostępniać fragmenty. Można więc używać go jako dodatkowej puli pamięci, innej niż standardowa sterta, z której można przydzielać pamięć i z jej pomocą trzeba też ją zwalniać. Nie robi się tego wówczas za pomocą standardowych operatorów new i delete, tylko z użyciem metod tej klasy. (Istnieje w C++ możliwość przeciążenia operatorów new i delete dla konkretnej klasy lub globalnie, ale nie będziemy tutaj o tym mówić.)

Ta pula pamięci ma oczywiście ograniczony rozmiar, podawany do konstruktora jako Capacity - pojemność. Jest to maksymalna liczba elementów, jakie będzie można z jej pomocą przydzielić. Rozmiar bloku w bajtach musi być więc równy tej maksymalnej liczbie elementów razy rozmiar pojedynczego elementu. Widoczne na listingu poniżej pola liczbowe pamiętają odpowiednio: m_Capacity - pojemność, czyli liczba komórek w puli pamięci (pozostaje stała), m_FreeCount - liczba wolnych komórek (na początku równa poprzedniej).

template <typename T>
class FreeList
{
private:
  char *m_Data;
  unsigned m_Capacity;
  unsigned m_FreeCount;
  // ...

public:
  FreeList(unsigned Capacity) :
    m_Capacity(Capacity),
    m_FreeCount(Capacity)
  {
    // ...
    m_Data = new char[Capacity * sizeof(T)];
    // ...
  }

  ~FreeList()
  {
    // ...
    delete [] m_Data;
  }

  //...
};

To chyba było dość proste? Blok pamięci jest typu char*, żeby mieć łatwość adresowania jego poszczególnych bajtów, ale tak naprawdę ma rozmiar który jest wielokrotnością rozmiaru jednego elementu - dokładnie jest to Capacity * sizeof(T) bajtów.

Esencją całego mechanizmu jest śledzenie, które komórki są przydzielone, a które wolne. Pomysł polega na utrzymywaniu listy łączonej jednokierunkowej pamiętającej adresy wolnych komórek. Gdzie przechowywać tą listę? Zaalokować w tym celu osobny blok pamięci? A może użyć std::list? Nie! Sprytną sztuczką jest tu wykorzystanie czterech pierwszych bajtów każdej wolnej komórki (której zawartość i tak jest przecież nieużywana) do przechowywania wskaźnika na następną wolną komórkę.

Rys. 1 pokazuje, jak wygląda pula pamięci zawierająca same wolne komórki ułożone w listę łączoną, zaraz po utworzeniu obiektu FreeList:

Lista wolnych komórek zaraz po utworzeniu
Rys. 1. Lista wolnych komórek zaraz po utworzeniu.

Żeby pamięć wyglądała tak jak pokazuje rysunek 1, trzeba tą listę połączyć przy inicjalizacji. Dokonuje tego konstruktor. Każdemu elementowi (który na tą okazję rzutowany jest do typu FreeBlock) do pierwszych czterech bajtów wpisuje adres poprzedniego elementu. Element pierwszy pokazuje na NULL. Pole m_FreeBlocks to natomiast wskaźnik na początek listy (pierwszy element na liście), wiec zostaje ustawiony na adres elementu ostatniego. Równie dobrze listę możnaby ułożyć od początku do końca albo w dowolnym innym porządku - kolejność bloków nie ma znaczenia.

struct FreeBlock
{
  FreeBlock *Next;
};

FreeBlock *m_FreeBlocks;

FreeList(unsigned Capacity) :
  m_Capacity(Capacity),
  m_FreeCount(Capacity)
{
  assert(Capacity > 0);
  assert(sizeof(T) >= sizeof(FreeBlock) &&
    "FreeList cannot work with such small elements.");

  m_Data = new char[Capacity * sizeof(T)];

  char *data_current = m_Data;
  FreeBlock *fb_prev = NULL, *fb_current;

  for (unsigned i = 0; i < Capacity; i++)
  {
    fb_current = (FreeBlock*)(data_current);
    fb_current->Next = fb_prev;

    fb_prev = fb_current;
    data_current += sizeof(T);
  }

  m_FreeBlocks = fb_prev;
}

Kiedy użytkownik zażąda przydzielenia nowego elementu z puli, jego zarezerwowanie i zwrócenie wskaźnika jest w takiej sytuacji banalnie proste i bardzo szybkie. Wykonuje się w czasie stałym. Wystarczy wziąć jakiś wolny element, który mamy pod ręką (najprościej pierwszy element listy, czyli ten na który pokazuje m_FreeBlocks), usunąć go z listy wolnych i zwrócić wskaźnik do niego. Odpowiada za to prywatna metoda PrvTryNew. Sytuację po przydzieleniu jednego, a dalej dwóch elementów pokazuje rys. 2. Jeśli nie uda się zaalokować nowego elementu, bo w puli nie ma już wolnego miejsca, poniższa metoda zwraca NULL.

T * PrvTryNew()
{
  if (m_FreeBlocks == NULL)
    return NULL;
  T *Ptr = (T*)m_FreeBlocks;
  m_FreeBlocks = m_FreeBlocks->Next;
  m_FreeCount--;
  return Ptr;
}

Alokacja elementów z listy.
Rys. 2. Alokacja elementów polega na ich usuwaniu z listy wolnych komórek.

Operacja zwalniania pamięci elementu też sprowadza się do prostego algorytmu znanego z podstaw informatyki (listy łączone to w końcu elementarna struktura danych) i jest bardzo szybkie. Zwalniany blok zostaje dołączony na początek listy wolnych bloków. W tym celu do jego czterech pierwszych bajtów wpisany zostaje adres pierwszego dotychczas wolnego bloku, a od tej pory to on staje się pierwszy. Wszystko to wykonuje metoda publiczna Delete. Przekazany adres musi być oczywiście poprawnym adresem komórki z puli pamięci należącej do danego obiektu FreeList, zaalokowanym wcześniej w opisany wyżej sposób.

void Delete(T *x)
{
  // ...
  FreeBlock *new_fb = (FreeBlock*)x;
  new_fb->Next = m_FreeBlocks;
  m_FreeBlocks = new_fb;
  m_FreeCount++;
}

Mamy już omówione przydzielanie i zwalnianie elementów, ale na tym nie koniec ciekawostek, na których opiera się nasz FreeList. Kolejną z nich jest pytanie, co powinno się stać, kiedy nie można wykonać żądania alokacji kolejnego elementu, bo nie ma już wolnego miejsca. Kiedy taka sytuacja zdarza się w rzeczywistości (podczas alokacji ze sterty operatorem new), rzucony zostaje wyjątek std::bad_alloc. Jest też wersja nie rzucająca wyjątku, ale zwracająca w takiej sytuacji po prostu wskaźnik pusty NULL - wygląda ona tak: new(std::nothrow). Funkcja malloc również w przypadku niepowodzenia zwraca NULL.

Mamy więc dwie możliwości. Nasz FreeList oferuje każdą z nich, do wyboru. Wersja zwracająca w przypadku braku wolnej pamięci NULL obejmuje metody z przedrostkiem "Try-", tak jak pokazana wyżej metoda PrvTryNew. Na jej podstawie napisana jest metoda PrvNew, która w przypadku niepowodzenia rzuca wyjątek, tak jak standardowy operator new:

T * PrvNew()
{
 T *R = PrvTryNew();
 if (R == NULL)
    throw std::bad_alloc();
  return R;
}

Standardowe operatory new i delete nie tylko przydzielają pamięć, ale i wywołują odpowiednio konstruktor i destruktor, jeśli dany typ jest klasą. Nasz alokator również powinien to robić. Problem w tym, że pamięć mamy już przydzieloną - jako alokację zwracamy przecież tylko wskaźnik do istniejącego bloku. Czy istnieje w C++ możliwość jawnego wywołania konstruktora i destruktora jakiejś klasy dla podanego adresu pamięci?

Tak, istnieje. Konstruktor można wywołać używając tzw. Placement New. Na przykład jeśli mamy typ Klasa posiadający konstruktor domyślny i wskaźnik Wsk typu Klasa*, możemy wywołać konstruktor tak jakby pod tym adresem tworzony był obiekt tej klasy używając konstrukcji:

new (Wsk) Klasa();

Jest tu jednak pewien mały haczyk. Otóż takie wywołanie można zrobić na dwa sposoby, których zachowanie będzie się różniło w pewnych sytuacjach. Dla klas każde z nich wywoła konstruktor domyślny, ale dla typów atomowych pierwsze pozostawi wartość niezainicjalizowaną, a drugie wywoła "konstruktor domyślny typu atomowego", który zainicjalizuje pamięć zerem. Tak, naprawdę istnieje coś takiego jak konstruktor domyślny typów atomowych (nazywa się to domyślnym inicjalizatorem). Można napisać int() i wyrażenie to zwróci liczbę 0. To bywa nieocenioną pomocą podczas pisania szablonów C++. Oto przykład ilustrujący tą subtelną różnicę:

// Tu wywoła się konstruktor domyślny
Klasa *Wsk11 = new Klasa;
// Tu też wywoła się konstruktor domyślny
Klasa *Wsk12 = new Klasa();

// Ta liczba pozostanie niezainicjalizowana
int *Wsk21 = new int;
// Ta liczba zostanie zainicjalizowana zerem
int *Wsk22 = new int();

Dlatego we FreeList udostępnione są dwie pary metod do alokacji elementów. Pierwsza pozostawia typy atomowe niezainicjalizowane, a druga jawnie wywołuje ich konstruktor domyślny. Dla typów użytkownika posiadających konstruktor (struktury i klasy) obydwa zestawy działają tak samo.

T * TryNew() { T *Ptr = PrvTryNew(); return new (Ptr) T; }
T * New   () { T *Ptr = PrvNew   (); return new (Ptr) T; }

T * TryNew_ctor() { T *Ptr = PrvTryNew(); return new (Ptr) T(); }
T * New_ctor   () { T *Ptr = PrvNew   (); return new (Ptr) T(); }

Dodatkowo można też napisać wersje metody alokującej, które wywołają konstruktor typu T z parametrami. Żeby mogły to być parametry dowolnego typu, poniższe metody są szablonami. Klasa posiada wersje tych metod przyjmujące od 1 do 5 parametrów.

template <typename T1> T * TryNew(
  const T1 &v1)
{
  T *Ptr = PrvTryNew(); return new (Ptr) T(v1);
}
template <typename T1> T * New   (
  const T1 &v1)
{
  T *Ptr = PrvNew   (); return new (Ptr) T(v1);
}
template <typename T1, typename T2> T * TryNew(
  const T1 &v1, const T2 &v2)
{
  T *Ptr = PrvTryNew(); return new (Ptr) T(v1, v2);
}
template <typename T1, typename T2> T * New   (
  const T1 &v1, const T2 &v2)
{
  T *Ptr = PrvNew   (); return new (Ptr) T(v1, v2);
}

// itd...

Jawne wywołanie destruktora podczas zwalniania elementów jest dużo prostsze. W C++ można wywołać destruktor ręcznie tak samo, jak wywołuje się zwykłe metody klasy. Brakującą linijką metody Delete jest więc po prostu:

x->~T();

Przykład

Dotychczas mowa była o wewnętrznej implementacji FreeList, czas teraz na przykład jej użycia (choć może on powinien być najpierw? :)

struct STRUKTURA
{
  int Pole1, Pole2;

  STRUKTURA()
  {
    std::cout << "Konstruktor." << std::endl;
  }
  ~STRUKTURA()
  {
    std::cout << "Destruktor." << std::endl;
  }
};

int main()
{
  // Utwórz FreeList
  FreeList<STRUKTURA> FreeList1(1024);
  std::cout << "FreeList1 zarezerwowal " << FreeList1.GetAllSize() <<
    " bajtow" << std::endl;

  // Zaalokuj 2 elementy
  std::cout << "Alokacja dwoch elementow..." << std::endl;
  STRUKTURA *Wsk1, *Wsk2;
  Wsk1 = FreeList1.New();
  Wsk2 = FreeList1.New();

  // Zobacz statystyki
  std::cout << "Zajete jest komorek " << FreeList1.GetUsedCount() <<
    ", wolne zostalo " << FreeList1.GetFreeCount() << std::endl;

  // Używam sobie wskaźników...
  Wsk1->Pole1 = 11; Wsk1->Pole2 = Wsk1->Pole1 + 1;
  Wsk2->Pole1 = 21; Wsk2->Pole2 = Wsk2->Pole1 + 2;

  // Zwolnij elementy
  std::cout << "Zwalnianie elementow..." << std::endl;
  FreeList1.Delete(Wsk1);
  FreeList1.Delete(Wsk2);
}

Pokazany kod jest chyba tak prosty, że nie wymaga wyjaśnienia. Oto generowane przez niego wyjście:

FreeList1 zarezerwowal 8192 bajtow
Alokacja dwoch elementow...
Konstruktor.
Konstruktor.
Zajete jest komorek 2, wolne zostalo 1022
Zwalnianie elementow...
Destruktor.
Destruktor.

Alokator dynamiczny

Napisałem też drugą klasę alokatora - DynamicFreeList. Różni się od poprzedniej tym, że nie ma ograniczonej, określonej z góry pojemności. Zamiast jednego dużego bloku pamięci, zdolna jest przechowywać całą kolekcję takich bloków, aby w razie potrzeby rezerwować nowe. Dzięki temu może przydzielić tak dużo elementów, dopóki wystarczy pamięci w systemie.

Do przechowywania tych bloków wykorzystuje obiekty wyżej opisanej klasy FreeList. Utrzymuje ich tablicę zawsze w porządku posortowanym wg liczby wolnych komórek. Kiedy nie ma wolnego miejsca w żadnym z bloków, tworzy nowy blok. Kiedy w jakimś bloku wolne stają się wszystkie komórki, zostaje zwolniony. Nie będę tu opisywał dokładnie zasady działania DynamicFreeList. Zainteresowanych odsyłam do dołączonego kodu.

Test wydajności

Cały ten własny alokator ma służyć głównie do tego, żeby przyspieszyć alokowanie pamięci. Wypada więc zbadać, czy dobrze spełnia swoją rolę. Aby to zrobić, po napisaniu przedstawionego tu kodu przeprowadziłem pomiar średniego czasu trwania następującego eksperymentu. Każdy test składał się z 10240 losowych operacji z 90% szansy, że tą operacją będzie alokacja nowego elementu i 10% szansy, że tą operacją będzie zwolnienie jednego z zaalokowanych elementów. Dodatkowo na końcu następowało zwolnienie wszystkich zaalokowanych i niezwolnionych wcześniej elementów. Test przeprowadziłem dla trzech różnych metod alokacji - z użyciem klasy FreeList, DynamicFreeList i standardowych operatorów new/delete oraz dla dwóch przypadków - w których rozmiar pojedynczego elementu był mały (4 B) i stosunkowo duży (1024 B). Oto wyniki zebrane w tabeli i na rys. 3, który przedstawia czas trwania eksperymentu dla konfiguracji RELEASE.

Konfiguracja Rozmiar elementu FreeList DynamicFreeList new i delete
DEBUG 4 B  68.0636 ms 184.441 ms 78.8142 ms
DEBUG 1024 B  69.3896 ms 203.506 ms 93.2942 ms
RELEASE 4 B 7.8722 ms 11.4786 ms 17.0348 ms
RELEASE 1024 B 9.1805 ms 18.0729 ms 24.0537 ms

Wyniki pomiaru czasu trwania eksperymentu pokazują przewagę FreeList
Rys. 3. Czas trwania eksperymentu w konfiguracji RELEASE.

Widać wyraźnie, że alokator napisany we własnym zakresie w oparciu o mechanizm Free List jest dużo szybszy, niż standardowa alokacja pamięci systemu.

Załącznik

Pobierz kod: FreeList.hpp.

Bibliografia

  1. Paul Glinker, Fight Memory Fragmentation with Templated Freelists, w: Andrew Kirmse, Game Programming Gems 4, Charles River Media, 2004.
  2. Nathan Mefford, Improving Freelists with Policy Based Design, w: Kim Pallister, Game Programming Gems 5, Charles River Media, 2005.
Adam Sawicki
http://asawicki.info
28.05.2008

Tekst dodał:
Adam Sawicki
28.05.2008 22:22

Ostatnia edycja:
Adam Sawicki
05.05.2012 15:06

Kategorie:

Aby edytować tekst, musisz się zalogować.

# Edytuj Porównaj Czas Autor Rozmiar
#5 edytuj (poprz.) 05.05.2012 15:06 Adam Sawicki 21.22 KB
#4 edytuj (poprz.) (bież.) 05.05.2012 15:06 Adam Sawicki 21.22 KB (+82)
#3 edytuj (poprz.) (bież.) 05.05.2012 15:05 Adam Sawicki 21.14 KB (-24)
#2 edytuj (poprz.) (bież.) 05.05.2012 15:03 Adam Sawicki 21.16 KB (+461)
#1 edytuj (bież.) 28.05.2008 22:22 Adam Sawicki 20.71 KB
Zwykły
Do sprawdzenia
Do akceptacji
  • Hadrian Węgrzynowski (@Queight) 30 maja 2008 13:34
    Bardzo ciekawe :]

    Mam kilka pytań: 1. Ile każdy testowany przypadek wykorzystuje RAM-u? 2. Czy mógłbyś dać kod testowy? Albo po prostu przetestować na innym systemie?
  • moriturius (@moriturius) 30 maja 2008 16:38
    Ja mam jedno pytanie: co się stanie jeśli za typ wezmę sobie char? ;)

    sizeof(T) < 4 więc wskaźniki będą się na siebie "nakładać" i będzie klops :P
  • maVes (@maVes) 30 maja 2008 17:37
    moriturius - w konstruktorze stoi assert chroniący przed takim przypadkiem.
  • ~yarpen 03 czerwca 2008 00:03
    Ten assert powinien byc compile-time.
  • Adam Sawicki (@Reg) 11 czerwca 2008 21:06
    yarpen: Racja.
  • jobsi (@jobsi) 23 kwietnia 2010 15:31
    Powinienaś chyba użyć inteligenych pointerów w przypadku kiedy konstruktor lub funkcja | operator w nim wywoływany może wyrzucić wyjątek Zwłaszcza przy alokacji pamięci bo destruktor nie będzie w stanie dokładnie posprzątać co może skutkować wyciekami pamięci
  • jobsi (@jobsi) 23 kwietnia 2010 15:32
    albo zdefiniować globalną funkcje obsługi błędów dla new (new_handler)
  • Napisz komentarz:
    Aby dodać swój komentarz, musisz się zalogować.
Licencja Creative Commons

Warsztat używa plików cookies. | Copyright © 2006-2017 Warsztat · Kontakt · Regulamin i polityka prywatności
build #ff080b4740 (Tue Mar 25 11:39:28 CET 2014)