Rychlý a úsporný kód

JSH

Re:Rychlý a úsporný kód
« Odpověď #45 kdy: 19. 12. 2014, 11:05:28 »
Tak ohledně té cache, tak jste dobrý teoretikové. Samozřejmě, že sekvenční zpracovávání je dobré, ale

1) zpomalení cache versus paměť je jen lineární. Blbě zvolenej algoritmus je daleko horší zlo, protože ten prostě na větších datech nedoběhne.
Třeba takový Coppersmith-Winogradův algoritmus je nepoužitelný jen a jen kvůli tomu "nedůležitému" lineárnímu zpomalení. To lineární zpomalení bývá občas tak veliké, že jakákoliv rozumná data nejsou dost velká.
Citace
2) napsat i jen tak blbou věc jako násobení matic tak, aby se správně využila cache  je věc velmi netriviální, dobrá implementace matematický knihovny je na roky práce. Takže napsat, že každej programátor by to měl zvládat je dobrej hospodskej kec.
Neříkám, že by měl být každý programátor schopný napsat efektivní násobení matic. Ale každý programátor by měl minimálně vědět, proč by měl jednu aspoň transponovat aby nepřenášel z paměti 8x víc dat, než je třeba. Stačí ten krok od tragického k rozumnému.
[/quote]
3) Každá architektura procesorů má tu cache organizovanou trochu jinak. Takže znalosti typu rozměr cache, Xcestnost atd...., pokud neladíte program na jednu konkrétní architekturu, jsou k ničemu. A to do toho ještě dělá dost velkej binec HW prefetch, kterej dost běžnejch cache-nepravostí umí vyřešit.

4) pro normálního programátora úplně stačí, když tak nějak tuší, že sekvnenční zpracování je plus.

A to píšu jako člověk, kterej zrovna teď dává dohromady maticový výpočty, kde když se na cache kašle, tak jde výkon do kytek....
[/quote]
Já v principu souhlasím. Jde mi o ten základ. O "své" architektuře by měl programátor minimálně vědět, jak má velké řádky cache. Nějaký prefetch a spol. až tak důležitý není.


JSH

Re:Rychlý a úsporný kód
« Odpověď #46 kdy: 19. 12. 2014, 11:09:05 »
Tak to se raději ani nedívejte na správu paměti s GC nebo třeba v Erlangu, tam se cache přímo ignoruje.
Fakt? Měl jsem za to, že generační GC vypadá tak jak vypadá právě kvůli cache. První generace se přebere ještě dokud je v cache.

JSH

Re:Rychlý a úsporný kód
« Odpověď #47 kdy: 19. 12. 2014, 12:21:26 »
2all: Mě totiž připadá trochu divné či spíše směšné řešit tu nějakou procesorovou cache s její mikropamětí když matice double mohou zabrat i 10,20 a více GB v RAM. Školní příklady matice 5x5 se fakt v realitě neřeší. Nejsem vzděláním žádný elektro-informatik, takže pokud žiji v omylu tak budu rád když mě z toho vysvětlením vyvedete.
A tohle je ten zásadní problém. Pro efektivní práci s těmi 20GB je třeba zatraceně dobře využít cache, protože té je sice jen pár MB, ale je o několik řádů rychlejší než hlavní paměť. Celá myšlenka cache stojí na tom, že v praxi se obvykle v jednom okamžiku nepracuje se všemi daty, ale s jejich malým kouskem. A taky že se v těch datech nepohybujeme úplně náhodně.

Ty matice jsou takřka ideální příklad. Už blbá transpozice jedné matice před násobením srazí množství přístupů do hlavní paměti na osminu. Množství přenesených dat se sice v podstatě nezmenší, ale využije se toho, že přenos velkých bloků paměti je daleko efektivnější. Ještě lepší je kouknout se na blokové matice. Pak je z jedné veliké matice najednou spousta malých, které se už do cache vlezou a dá se toho výborně využít.

Podobné principy platí i jinde, než jenom u násobení matic. Třeba http://research.scee.net/files/presentations/gcapaustralia09/Pitfalls_of_Object_Oriented_Programming_GCAP_09.pdf to rozebírá na grafech scény pro 3D enginy.