W pierwszym wpisie poświęconym Data-Oriented Design, zaprezentowałem ogólną koncepcję podejścia do tworzenia oprogramowania. Temat DOD jest jednak rozległy i kryje przed nami wiele niespodzianek. Nawiązując do tytułowego pytania - czy zastanawiałeś się kiedyś, czy kolejność deklaracji zmiennych w strukturze ma jakiekolwiek znaczenie? Odpowiem już teraz - ma znaczenie. Szczególnie, gdy mówimy o pamięci cache. W tym wpisie, postaram się przedstawić jak działa wyrównanie pamięci, oraz co kryje się pod skrótami AOS&SOA.

Zapraszam również do lektury pierwszego wpisu z tej serii: Data-Oriented Design & Programming - czyli jak łatwo przyspieszyć swój kod

Kolejność pól w klasie

Jakiś czas temu w firmie, w której programuję, rzuciłem na Slacka krótką zagadkę. Wyglądała ona następująco:

Jaki rozmiar będzie miała struktura? Pierwsza część zagadki.
Mamy architekturę 64-bitową (czyli słowa w pamięci są 8-bajtowe). Programujemy w języku Swift, gdzie Int ma rozmiar 8 bajtów, a Float 4 bajty. Jaki rozmiar będzie miała struktura, zaprezentowana na obrazku?

Dla przypomnienia - struktura jest oczywiście ciągłym obszarem pamięci. Łatwo więc obliczyć, że 2 * 8 + 4 = 20. Struktura Base2 ma rozmiar 20 bajtów.
Proste? Jasne, że tak!

Druga część zagadki

Jaki rozmiar będzie miała struktura? Druga część zagadki.
W poprzedniej strukturze, przesunięto pole c, tak aby znajdowało się pomiędzy dwoma pozostałymi Int'ami. Jaki rozmiar będzie mieć struktura po takiej zmianie?

Poprawna odpowiedź: Inny.
A dokładnie: większy, bo 24 bajty.

No ale przecież, w dzisiejszych czasach, nie musimy martwić się już zbytnio o pamięć. Musimy się wciąż martwić o wydajność naszego oprogramowania, ale póki nie programujemy dla CERN'u, to pamięć jest sprawą drugorzędną. Często spotyka się nawet, stosowanie redundancji danych - np. tworząc indeks odwrotny dla jakiegoś zbioru danych, tylko po to, aby uzyskać do niego jeszcze szybszy dostęp.

Przykład z naszej zagadki, nie jest wstępem do wpisie o oszczędzaniu pamięci, ale o optymalizacji. Otóż zrozumienie, co tak naprawdę dzieje się pod spodem (w pamięci), jest kolejnym sposobem na zwiększenie wydajności programu.

Wyjaśnienie zagadki

Dla przypomnienia - pamięć skonstruowana jest z bloków pamięci tzw. słów (ang. word). Każde słowo posiada swój adres - identyfikator, po którym komputer może odnaleźć wymagane dane. W zależności od architektury komputera, mamy do czynienia z innym rozmiarem słowa. Najpopularniejsze architektury 32-bitowe oraz 64-bitowe, zawierają już w nazwie długość słowa na jakim operują. Zagadka dotyczyła architektury 64-bitowej, więc mówimy o 8-bajtowym słowie. Jednak w kontekście opisywanego problemu, rozmiar słowa nie jest aż tak istotny.

Wycinek pamięci, dwie struktury z wcześniejszej zagadki, umieszczone w 3 słowach po 8 bajtów. Grubą krawędzią zaznaczyłem granicę struktury.

Spójrzmy na chwilę na obrazek powyżej. Widzimy na nim dwie struktury z poprzedniej zagadki, umieszczone w pamięci (obrazek przedstawia 3 wycięte słowa z pamięci). Zakreślony obszar to tak zwany Padding, który wypełnia wolną przestrzeń słowa. To on jest głównym winowajcą powiększenia rozmiaru naszej struktury.

Jak pamiętamy, wydobywanie danych z pamięci odbywa się przez odwoływanie się do konkretnych adresów słów. Co za tym idzie - pamięć wyłuskiwana jest całymi blokami (zawierającymi słowa). Potrzebujemy zmienną typu Int? Parę cykli procesora, jedno odwołanie do pamięci - mamy naszą zmienną w pamięci cache i już procesor może na niej operować (oczywiście wrzucając ją potem z cache do odpowiednich rejestrów procesora, ale to taka dygresja).

Przypadek braku wyrównania pamięci. Zmienna b została umieszczona w dwóch osobnych słowach.

W przypadku zaprezentowanym powyżej, zmienna b została rozbita i część z niej znajduje się w jednym słowie, a część w kolejnym. Uzyskiwanie takiej zmiennej z pamięci, jest mniej efektywne, ponieważ muszą zostać pobrane dwa osobne bloki, następnie zmienna musi zostać "sklejona", wykonując parę sprytnych operacji przesuwania itp.

Oczywiście takie operacje są w naszych komputerach powszechne. Jednak w większości przypadków, następuje samoistne wyrównanie danych (ang. data alignment) i za pomocą wypełniania słów pamięci wolną przestrzenią, zmienne dużo rzadziej są dzielone.

Wpływ na wydajność

Być może pamiętasz, jak w poprzednim wpisie z tej serii Data-Oriented Design & Programming - czyli jak łatwo przyspieszyć swój kod, pisałem, że lepiej trzymać takie same struktury w ciągłym obszarze pamięci. Każde dodatkowe sięganie do pamięci, po kolejny obiekt, to dodatkowe cykle procesora. Upakowanie obiektów w jednym miejscu powoduje, że do pamięci podręcznej procesora trafia od razu nie jeden - a dużo więcej obiektów.

Zapewne już domyśliłeś się o co chodzi. Zmniejszenie rozmiaru struktury, za pomocą zmiany kolejności pól, powoduje jeszcze większe upakowanie danych w pamięci cache. Skutkuje to jeszcze większą liczbą obiektów znajdujących się w pamięci cache w jednym momencie i mniejszą częstotliwość wczytywania brakujących obiektów z dużo wolniejszej pamięci RAM.

AOS i SOA

Przy okazji analizowania Data-Oriented Design, można natknąć się również na dwa terminy opisujące strategie przechowywania danych. Pojęcia te są sobie przeciwstawne.

AOS - Array of Structures

Tłumacząc na polski - tablica struktur. Podejście to jest najpowszechniej stosowane w programowaniu obiektowym. Nie ma co opisywać - struktura z obiektami, a następnie kontener na te struktury.

struct Entity {
  A componentA;
  B componentB;
  C componentC;
};

std::vector<Entity> entities;

for(auto& entity : entities) {
  // entity.componentA
}

Spójrzmy teraz na obrazek ilustrujący "okno", w jakim kopiowany jest fragment pamięci RAM do pamięci Cache. Przy operacjach jedynie na obiektach typu A, w pamięci cache znajdują się niepotrzebne nam teraz obiekty typu B oraz C.

Array of Structures

SOA - Structure of Arrays

Drugim ze wspomnianych sposobów jest struktura tablic. Tutaj, nie tworzymy już jednego kontenera na strukturę z polami. Mamy teraz do czynienia z strukturą, trochę stającą się takim kontenerem. Pola za to przechowywane są w tablicach.

struct Entities {
  std::vector<A> componentsA;
  std::vector<B> componentsB;
  std::vector<C> componentsC;
};

Entities entities;

for(auto& componentA : entities.componentsA) {
  // componentA
}
Gdybyśmy chcieli uzyskać dostęp do componentu A, dla entity o indeksie 4, musielibyśmy odwołać się do niego np. w taki sposób: entities.componentsA[4]
Nie entities[4].componentA, jak w przypadku AOS.

Spójrzmy teraz jak to wygląda w pamięci:

Structure of Arrays

Lepiej prawda?

Podsumowanie

W poprzednim wpisie nakreśliłem, czym DOD tak naprawdę jest oraz pokazałem, jak trzymać dane aby były cache-friendly. W tym wpisie natomiast, zwróciłem uwagę na to jak wygląda pamięć struktury oraz o czym musimy pamiętać, aby w cache zmieściło się więcej przetwarzanych obiektów.

Jeżeli coś jest niejasne, albo znalazłeś jakiś błąd - daj mi znać, szybciutko się tym zajmę :)
Do zobaczenia w kolejnych wpisach!