0xDEADBEEF

[RSS]
««« »»»

Poznámky k výkonu

28. 12. 2017

Před ně­ja­kou dobou mi twit­te­rem pro­le­těla pre­zen­tace Ad­ven­tu­res in ef­fi­ci­ency and per­for­mance (slajdy, video), kde autor mluvil o tom jak do­sáh­nout výkonu na JVM a vy­prá­věl o hard­waru. Ně­které in­for­mace mi přišly ne­do­sta­tečné, tady jsou moje po­známky.

V části „Good“ failed specu­lati­ons uvádí:

Both bran­ches will be execu­ted in pa­ral­lel, only one of them will be re­ti­red

Ukáz­kový 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 zkom­pi­lo­ván. Na jednu stranu může být pře­ve­den na com­pare+branch in­strukce, které po­ve­dou k tomu, že CPU bude dy­na­micky spe­ku­lo­vat a bude zá­le­žet na branch pre­diction. 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
}

Po­slední if ne­před­sta­vuje skok, ale in­strukci cmov (con­di­ti­o­nal move), která na zá­kladě po­rov­nání pře­sune buď add nebo sub. Nejde o vět­vení pro­gramu a tedy ani ne­hrozí žádná pe­na­li­zace při špat­ném odhadu skoku (branch mispre­dict).

Nevím přesně, co myslel těmi good failed specu­lation. Sou­časné x86 pro­ce­sory (pokud se ne­mý­lím) se ne­snaží spe­ku­la­tivně pro­vést obě větve pod­mínky a retire jen tu správ­nou.

Další pří­klad, který je mnohem kom­pli­ko­va­nější než je pre­zen­to­vá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 3x rych­lejší až do pří­chodu Intel Sky­lake pro­ce­sorů, které pak uvedly ně­ja­kou blíže ne­spe­ci­fi­ko­va­nou změnu, která to změ­nila.

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

Jde o to, že rychlá verze přečte všechny ele­menty pole a[i] jeden za druhým než se posune na ná­sle­du­jící pole a[i+1]. Pomalá verze přečte první ele­ment ze všech polí a pak se posune na druhý ele­ment. Rychlá verze čte sek­venč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 pre­fe­ro­vaná, pro­tože se dá snáze vek­to­ri­zo­vat bez scat­ter/gather in­strukcí).

Rychlá verze fun­guje tak dobře, pro­tože hard­ware počítá s tímto cho­vá­ním. Data z paměti tahá po cache line blo­cích (64B na sou­čas­ných x86). Když se dotknu prv­ního intu v poli, dal­ších 16 jich už čeká v cache, při­pra­vené pro rychlé čtení. CPU navíc do­předu načítá data, která budou prav­dě­po­dobně po­třeba (pre­fetch), takže sek­venční prů­chod je zcela ide­ální.

Pre­fet­cher ale nemusí na­čí­tat jen data, která leží těsně vedle, ale dokáže de­te­ko­vat kroky kon­stantní délky. Pokud jsou vnitřní pole malá a alo­ko­vaná sek­venčně, pre­fet­cher roz­po­zná vzdá­le­nost k dal­šímu po­ža­do­va­nému prvku (stride) a načte ho do­předu. (Je ale méně efek­tivní, pro­tože pořád musí vy­táh­nout celou cache line, za které po­u­žiji jen první prvek a než se do­stanu k jeho sou­sedu, může být už vy­ho­zená 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 alo­ko­vána různě na haldě, tak to také nemusí být pro­blém. Pre­fet­cher zvládne pra­co­vat na ně­ko­lika mís­tech paměti na­jed­nou (něco jako 64 růz­ných strá­nek). Kdyby tedy vnější pole bylo menší než tento limit, pre­fet­cher by stále pomohl.

I když jsou vnitřní pole ro­ze­setá všude na haldě, ani to nemusí být konec. Záleží totiž i na po­u­ži­tém gar­babe collec­toru. Ně­které GC dělají kom­pakci haldy tak, že pře­sou­vají ob­jekty v pořadí ve kterém na ně narazí při pro­chá­zení re­fe­rencí. V tomto pří­padě GC může na­ra­zit na pole a, zko­pí­ruje ho na jedno místo a pak z něj začne pro­chá­zet všechny re­fe­rence na vnitřní pole a jedno po druhém je ko­pí­ro­vat vedle sebe. To povede k ob­no­vení dobré lo­ka­lity jako na sché­matu o něco výše.

Sky­lake mohl uvést větší cache, pre­fetch na více strán­kách paměti, více pa­ra­lel­ních pří­stupů do paměti, větší OOO okno. Vliv může mít také aso­ci­a­ti­vita cache a cache eviction policy.

Nebudu tady teď mluvit scat­ter/gather SIMD in­struk­cích a dal­ších věcech, pro­tože by to za­bralo příliš místa a tenhle článek je už tak dost dlouhý.

Zjis­tit co je rych­lejší a hlavně proč je jako vždycky kom­pli­ko­vané.

Re­le­vantní čtení:

píše k47 (@kaja47, k47)