Gdy na początku studiów, buszując w sieci, natrafiłem na te koncepcje - byłem nimi niesamowicie oczarowany. Na uczelni wałkowaliśmy (pseudo) obiektowy paradygmat i byliśmy przekonani, że kod w nim napisany będzie najlepszy pod każdym względem. Przez myśl mi wtedy nie przeszło, że programy pokazywane w książkach i na wykładach obarczone są  pewnymi konsekwencjami wydajnościowymi. Tyle moich osobistych historii - zobaczmy o co w tym wszystkim chodzi.

Czym jest DOD?

Data-Oriented Design to podejście projektowania oprogramowania w taki sposób, aby było ono zorientowane na danych na których wykonujemy operacje. W tym podejściu, nieustannie musimy pamiętać o tym, jak nasze dane przetwarzane są przez procesor i w jaki sposób przechowywane są w jego pamięci Cache. Efekt jest taki, że kod zorientowany na danych działa dużo wydajniej w porównaniu do kodu czysto obiektowego.

Data-Oriented Programming to sposób programowania zgodny z paradygmatem DOD. W przeciwieństwie do paradygmatu OOP, w DOP kładziemy nacisk na tworzeniu kodu wydajnego dla procesora, zamiast skupiać się na idealnym odwzorowaniu rzeczywistości za pomocą obiektów.

Co jest złego w podejściu obiektowym?

... nic. Tak naprawdę, jeżeli nie potrzebujemy większej wydajności, to możemy przy OOP pozostać. Istnieją jednak, takie obszary programowania (jak np. gamedev), w których wysoka wydajność jest na wagę złota.

Przeanalizujmy poniższy przykład:

class Component {
  int result;
public:
  void update(float dt) {
    this->result += PI * dt;
  }
};
class Entity {
  std::unique_ptr<Component> component;

public:
  Entity() : component(new Component) {}

  Component& getComponent() {
    return *this->component;
  }
};

Mamy tutaj dwie klasy: Entity oraz Component. Entity agreguje u siebie komponent, który można uzyskać za pomocą gettera getComponent(). Komponent posiada funkcję update(), która przyjmuje za parametr DeltaTime (czas jednej klatki aktualizacji - powszechne w grach) i dodaje go do zmiennej result. W innym miejscu w aplikacji, dokonujemy aktualizacji wszystkich jednostek:

// std::vector<std::unique_ptr<Entity>> entities;
for(auto& entity : entities) {
  entity->getComponent().update(dt);
}

Iterujemy po wszystkich jednostkach i wykonujemy funkcje update() na ich komponentach. Warto zauważyć, że zmienna entities to kontener na wskaźniki do obiektów jednostek.

Jak to wygląda w pamięci?

W kontenerze std::vector, w ciągłym obszarze pamięci przechowywane są wskaźniki na dynamicznie utworzone entity. Każdy entity dodatkowo przechowuje wskaźnik na swój komponent. Mechanizmy dynamicznej alokacji pamięci, przydzielają pierwszy wolny obszar pamięci ze sterty - przez co nie możemy zakładać, że obiekty przez nas zalokowane będą umieszczone blisko siebie. Wprost przeciwnie, możemy być pewni, że nasze komponenty będą rozsiane w różnych miejscach w pamięci.

Jakie to niesie konsekwencje?

Procesor komputera, podczas swojego działania, wykorzystuje pamięć podręczna Cache. Jest ona paro(nasto)krotnie szybsza od pamięci RAM i służy do przechowywania małych porcji danych, które są właśnie przetwarzane przez procesor.

Gdy procesor wymaga określonego bajtu z pamięci, sprawdza jego obecność w pamięci Cache. Jeżeli się tam znajduje, mamy szczęście (tzw. cache hit). Jeżeli nie (tzw. cache miss), uprzednio, do pamięci podręcznej, musi zostać ściągnięty fragment zawierający wymagany bajt - co jest operacją dużo bardziej czasochłonną.

Kopiowanie danych z pamięci RAM do pamięci cache, odbywa się na większych porcjach danych, które następnie trafiają do jednego z cache line'ów. Gdy do cache kopiowany jest interesujący nas obiekt, przy okazji kopiowany jest również fragment jego otoczenia.

Zauważmy, że gdy wymagamy danych, które występują bezpośrednio po sobie w pamięci RAM, zostają one skopiowane wspólnie w ramach jednego przenoszenia do pamięci cache i nie trzeba sięgać po każde z nich osobno.
W ten sposób minimalizujemy całkowitą ilość cache miss'ów (bo przecież te dane już znajdują się w cache) i tym samym zwiększamy wydajność naszych operacji.

W naszym przykładzie, obiekty Component porozrzucane są po całej pamięci. Skutkuje to tym, że podczas kolejnych wywołań funkcji update(), następny obiekt Component nie znajduje się w pamięci Cache i tym samym musi zostać ściągnięty z pamięci RAM.

Chyba nie o to nam chodzi, prawda? :)

Poprawiamy kod

Pojęcie data locality definiuje, jak informacje rozmieszczone są względem siebie w RAM'ie. W naszych działaniach, będziemy dążyć do uzyskania ciągłego obszaru pamięci, w którym komponenty będą umieszczone bezpośrednio po sobie. Warto wspomnieć, że kontener std::vector w języku C++ zapewnia ciągłość pamięci - więc to przy nim pozostaniemy. Dla naszych potrzeb jednak, nie będziemy przechowywali w nim wskaźników, a bezpośrednio obiekty komponentów.

Oczywiście nic nie stoi na przeszkodzie, aby w tym podejściu kontener przechowywał wskaźniki, jednak należy wtedy ręcznie dbać o poprawne miejsce alokacji (np. przy pomocy placement new).  

struct Component {
  int result;
};

Na początek zamieńmy klasę Component na zwykłą strukturę i usuńmy z niej logikę (funkcja update została przeniesiona poza ramy struktury).

class Entity {
  Component& component;
  
public:
  Entity(Component& component) : component(component) {}

  Component& getComponent() {
    return this->component;
  }
};

Aby nie komplikować przykładu, załóżmy, że komponenty tworzone są poza klasą Entity, a następnie zostają do niej wstrzyknięte przez konstruktor. To podejście nie jest idealne, ponieważ kod zwalniający obiekt Entity, będzie dodatkowo musiał pamiętać o zwolnieniu obiektu Component.

void update(std::vector<Component>& components, float dt) {
  for(auto& component : components) {
    component.result += PI * dt;
  }
}

Powyższy listing odkrywa sedno całej sprawy. Wydzielona z klasy Component, funkcja update, przyjmuje jako parametr vector komponentów. Aktualizacja odbywa się iterując po każdym elemencie w tym kontenerze.

Rady końcowe

Nie wszystkie języki oferują dynamicznie rozszerzalny kontener, zapewniający ciągły obszar pamięci. Na szczęście to nie problem, ponieważ można wspomóc się wzorcem object pool i zarezerwować sobie wcześniej trochę miejsca na dane. Należy jednak wtedy pomyśleć o zapobieganiu fragmentacji, ponieważ ona też będzie powodować cache miss'y.

Musimy pamiętać, że pamięć podręczna ma dość małą pojemność. Z uwagi na to, lepiej przechowywać w strukturach tylko te dane, które potrzebne są do aktualizacji. Każde nadmiarowe informacje, będą powodować, że w jednym cache line pomieści się mniejsza ilość komponentów.

Podsumowując

Wszystko to na pewno sprawi, że nasz kod będzie wykonywać się szybciej. Podejście DOD, kładzie fundamenty pod architekturę ECS - zdobywającą ostatnio na popularności architekturę gameobjectów w grach.

Oczywiście wiele przedstawionych tutaj rzeczy można jeszcze bardziej zoptymalizować. Warto zainteresować się również SIMD - architekturą procesorów, pozwalającą zrównoleglić wykonywane instrukcje.

To na tyle, w razie pytań i sugestii - zapraszam do komentarzy.