0xDEADBEEF

RSS odkazy english edition
««« »»»

Struct of arrays & array of structs

2. 4. 2021 #D #paměť #CPU

Další článek, který tvrdí OOP je zlo, mainstream jazyky špatné a naše mentální modely zastaralé. Takových jsme četli tucet jenom dnes před snídaní. Tenhle ale mění zaběhlé sofistiky: O katastrofy jde proto, že vedou ke organizaci dat, která je na moderních CPU apriori neefektivní. OOP objekty jsou array of structs, ale CPU jsou efektivní se struct of arrays. To je pochopitelně nesmysl.

Arrays of structs (AoS) označuje layout paměti, kdy všechny atributy jednoho objektu jsou v paměti pohromadě pěkně vedle sebe.

struct Ant {
  string color;
  int age;
  bool warrior;
}

Ant[] aos;

Naproti tomu struct of arrays (SoA) ukládá postupně atributy všech objektů do spojitých polí.

struct AntSoA {
  string[] color;
  int[] age;
  bool[] warrior;
}

AntSoA soa;

SoA má navrch v situacích, kdy je potřeba pár atributů všech objektů. Ty jsou v paměti naskládané pěkně za sebou a hromadné čtení je rychlé: malý počet cache-miss, každý bajt z cache line je použit a hardwarový prefetch může efektivně pracovat.

Důležitý detail spočívá v tom, že SoA i AoS mají různé použití podobně jako jako sloupcové a řádkové databáze. Předpokládají lokalitu v různých dimenzích. A v určitých situacích bude efektivnější jedna varianta, v jiných druhá. Článek vyznívá, že SoA je vždy lepší pro CPU a brnká na strunu líného ikonoklasmu: Rozboří jedno dogma a nahradí ho jiným.

Navíc SW se přizpůsobuje HW a HW se vyvíjí podle SW. Odhadovat chování a rychlost programu jen počtem dotčených cache line je většinou nedostatečné. Jde o přístup, který zastaral před dekádou. Dnešní CPU jsou mnohem komplikovanější, jde o out-of-order bestie s rozsáhlými cache a dělají agresivní prefetch, aby maskovaly latence RAM. OOO spekuluje stovky instrukcí dopředu, aby šláply na co nejvíc cache line a co nejvíce cache-miss proběhlo najednou. Prefetch v ideálním případě znamená, že čtení z paměti není limitované latencí, ale propustností. Dostat cache line z paměti (na mém laptopu) může v nejhorším případě trvat 130 ns, když jde o plně serializovaný cache miss nebo jen 5 ns, pokud ji doručí prefetcher. Článek mluví o cache a lokalitě, ale vynechává datové závislosti, které jsou o zákeřnější, protože přes ně hardware nemůže spekulovat.

Jeden demonstrační příklad: Testovací program se dotýká cache line v náhodném pořadí, jednou s datovou závislostí a podruhé bez ní. Rozdíly v efektivitě jsou drastické.

struct Line { ubyte[64] data; }

auto len = 1 << 24;
Line[] lines = new Line[len];
Line*[] points = lines.map!((ref l) => &l).array;
randomShuffle(points);

// se závislostí
ulong prev;
foreach (p; points) {
  // Přičítání prev uvede datovou závislost. prev má vždy hodnotu 0, procesor
  // to neví a musí čekat, až se data dostanou z paměti. Přístupy do RAM jsou
  // ve výsledku serializované.
  sink += prev = (*(p+prev)).data[0];
}

// bez závislosti
foreach (p; points) {
  sink += (*p).data[0];
}

Obě varianty procházejí data stejným způsobem, liší se jen fakt, že program se závislostí načítá jednu cache line a teprve potom další, přístupy jsou efektivně zcela serializované. Verze bez závislostí může spekulovat, strpět několik cache-miss paralelně a ve výsledku běží znatelně rychleji.

Verze se závislostmi běží víc než 3.5x pomaleji a to jde o můj historický i5-2520M. U novějších CPU s agresivnější OOO a větším MLP, dost možná bude propast mezi oběma variantami ještě větší. Jako obvykle záleží na detailech. SoA a AoS jsou jen nástroje, jeden není univerzálně efektivnější než jiný.

Na druhou stranu je pravda, že programovací jazyky by měly nabídnout možnost zvolit mezi SoA nebo AoS tak, aniž by došlo k masivním změnám v programu. Layout dat v paměti je další abstrakce, kterou by mělo jít volit, jak je třeba.

Není ale pravda, že to žádný jazyk nedokáže, jak článek tvrdil. Stačí k tomu dostatečně silné meta-programování a trochu mstivé vynalézavosti. Za chvíli jsem něco takového nacvakal v jazyce D. Tady je zkrácená verze:

struct StructOfArrays(T) if (is(T == struct)) {

  private static forEachField(string code) {
    string res;
    static foreach (field; FieldNameTuple!T) { res ~= code.replace("$f", field); }
    return res;
  }

  mixin(forEachField(q{ typeof(T.$f)[] $f; }));

  struct FakeItem {
    ulong i;
    StructOfArrays* soa;

    mixin(forEachField(q{ auto $f() { return soa.$f[i]; } }));

    T convertToT() {
      T res;
      mixin(forEachField(q{ res.$f = $f; }));
      return res;
    }

    alias convertToT this;
  }

  ulong length() {
    return mixin((FieldNameTuple!T)[0]).length;
  }

  auto opIndex(ulong i) {
    return FakeItem(i, &this);
  }

  auto opIndexAssign(U)(U x, ulong i) if (is(U == T) || is(U == FakeItem)) {
    mixin(forEachField(q{ $f[i] = x.$f; }));
  }

  auto opOpAssign(alias op)(T x) if (op == "~") {
    mixin(forEachField(q{ $f ~= x.$f; }));
  }

  // další metody v podobném duchu ...

}

Kód není žádný krasavec, převážně jen generuje metody, které rozbalují a sbalují objekty do polí. Na kráse moc nesejde, jde o abstrakci a navíc převážně mechanickou.

Použití je velice podobné, jako kdyby člověk pracoval s obvyklými daty.

struct Ant {
  string color;
  int age;
  bool warrior;
}

auto ants = StructOfArrays!Ant();
ants ~= Ant("red", 11, false);
ants ~= Ant("blue", 1, true);

writeln(ants[0]);       // soa.Ant(color: red, age: 11, warrior: false)
writeln(ants.warrior);  // [false, true]
writeln(ants.length);   // 2
ants[1] = ants[0];
writeln(ants);          // StructOfArrays!(Ant)(["red", "red"], [11, 11], [false, false])
Ant x = ants[0];
writeln(x);             // Ant("red", 11, false)

Když Andrei Alexandrescu prohlašoval, že introspekce a meta-programování bude next big thing, kdy během kompilace bude generován optimální kód pro danou situaci, rozhodně na něco kápnul. Jde o velice mocný nástroj, který může překlenout propast mezi expresivitou na jedné straně a efektivitou na druhé.


Pozn:

Zdá se, že termín data-oriented programming se používá ve dvou kontextech: Jednak metoda optimalizace programu pro efektivní využití CPU cache a druhak obludný sen Rich Hickeyho o reprezentaci dat jako neměnné netypované datové struktury. Jde o světy tak diametrálně odlišné, jak jen to je možné.

píše k47 (@kaja47, k47)