Poznámky k výkonu

28. 12. 2017 #JVM #CPU

Před nějakou dobou mi twitterem proletěla prezentace Adventures in efficiency and performance (slajdy, video), kde autor mluvil o tom jak dosáhnout výkonu na JVM a vyprávěl o hardwaru. Některé informace mi přišly nedostatečné, tady jsou moje poznámky.

V části „Good“ failed speculations uvádí:

Both branches will be executed in parallel, only one of them will be retired

Ukázkový kód vypadá takhle:

def foo(a: Array[Int], idx: Int) = {
  val s = a[idx]
  if (s < 0) idx + idx
  else idx - idx
}

Záleží, jak bude kód zkompilován. Na jednu stranu může být převeden na compare+branch instrukce, které povedou k tomu, že CPU bude dynamicky spekulovat a bude záležet na branch prediction. Na druhou stranu to může vést k něčemu jkao tohle:

def foo(a: Array[Int], idx: Int) = {
  val s = a[idx]      //
  val add = idx + idx //
  val sub = idx - idx // nezávislé operace, všechny tři můžou běžet najednou

  if (s < 0) add else sub // zkompilováno jako cmov instrukce bez skoku
}

Poslední if nepředstavuje skok, ale instrukci cmov (conditional move), která na základě porovnání přesune buď add nebo sub. Nejde o větvení programu a tedy ani nehrozí žádná penalizace při špatném odhadu skoku (branch mispredict).

Nevím přesně, co myslel těmi good failed speculation. Současné x86 procesory (pokud se nemýlím) se nesnaží spekulativně provést obě větve podmínky a retire jen tu správnou.

Další příklad, který je mnohem komplikovanější než je prezentováno:

val a: Array[Array[Int]] = ...
val i = 0
while (i < n) {
  val j = 0
    while (j < n) {
      if (fast) {
        a[i][j] += a[i][j]
      } else { // slow
        a[j][i] += a[j][i]
      }
      j += 1
    }
  i += 1
}

Autor tvrdí, že rychlá verze (větev fast) byla 3× rychlejší až do příchodu Intel Skylake procesorů, které pak uvedly nějakou blíže nespecifikovanou změnu, která to změnila.

Pomalá větev může být rychlá, záleží na řadě faktorů jako například jak velká jsou data a jak jsou uspořádaná v paměti.

Jde o to, že rychlá verze přečte všechny elementy pole a[i] jeden za druhým než se posune na následující pole a[i+1]. Pomalá verze přečte první element ze všech polí a pak se posune na druhý element. Rychlá verze čte sekvenčně bloky paměti, druhá skáče z místa na místo.

Pokud je dat málo a vejdou se do cache, není moc co řešit (ale rychlá verze je stále preferovaná, protože se dá snáze vektorizovat bez scatter/gather instrukcí).

Rychlá verze funguje tak dobře, protože hardware počítá s tímto chováním. Data z paměti tahá po cache line blocích (64B na současných x86). Když se dotknu prvního intu v poli, dalších 16 jich už čeká v cache, připravené pro rychlé čtení. CPU navíc dopředu načítá data, která budou pravděpodobně potřeba (prefetch), takže sekvenční průchod je zcela ideální.

Prefetcher ale nemusí načítat jen data, která leží těsně vedle, ale dokáže detekovat kroky konstantní délky. Pokud jsou vnitřní pole malá a alokovaná sekvenčně, prefetcher rozpozná vzdálenost k dalšímu požadovanému prvku (stride) a načte ho dopředu. (Je ale méně efektivní, protože pořád musí vytáhnout celou cache line, za které použiji jen první prvek a než se dostanu k jeho sousedu, může být už vyhozená z cache).

     | -- a[0] ----- | -- a[1] ----- | -- a[2] ----- | -- a[3] -----

slow:  ^               ^               ^               ^
       |<-a[0].length->|<-a[0].length->|<-a[0].length->|

fast:  ^^^^^^^^^^^^^   ^^^^^^^^^^^^^

Pokud jsou vnitřní pole alokována různě na haldě, tak to také nemusí být problém. Prefetcher zvládne pracovat na několika místech paměti najednou (něco jako 64 různých stránek). Kdyby tedy vnější pole bylo menší než tento limit, prefetcher by stále pomohl.

I když jsou vnitřní pole rozesetá všude na haldě, ani to nemusí být konec. Záleží totiž i na použitém garbabe collectoru. Některé GC dělají kompakci haldy tak, že přesouvají objekty v pořadí ve kterém na ně narazí při procházení referencí. V tomto případě GC může narazit na pole a, zkopíruje ho na jedno místo a pak z něj začne procházet všechny reference na vnitřní pole a jedno po druhém je kopírovat vedle sebe. To povede k obnovení dobré lokality jako na schématu o něco výše.

Skylake mohl uvést větší cache, prefetch na více stránkách paměti, více paralelních přístupů do paměti, větší OOO okno. Vliv může mít také asociativita cache a cache eviction policy.

Nebudu tady teď mluvit scatter/gather SIMD instrukcích a dalších věcech, protože by to zabralo příliš místa a tenhle článek je už tak dost dlouhý.

Zjistit co je rychlejší a hlavně proč je jako vždycky komplikované.

Relevantní čtení:

0xDEADBEEF

Poznámky k výkonu