Rychlý a úsporný kód

[Filip Jirsák]

Nevím, jak často programátoři programují násobení matic. Dost programátorů ale programuje webové aplikace, které jsou přirozeně vícevláknové, a kde může mít uspořádání sdílených dat vliv právě na to, jak se bude pracovat s cache.
Jinak bylo řečeno, že algoritmus je daleko podstatnější, než cache, na druhou stranu cache je většinou podstatnější, než použití speciálních instrukcí nebo než ruční optimalizace strojového kódu.

[Reklama]

[technomaniak]

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....

A co konkrétně s nimi děláš? 

[Kolemjdoucí]

Pro rozumné využití cache ani není třeba vědět, jak je velká. Je jen třeba tušit velikost řádků cache a co nejvíc se držet sekvenčního průchodu pamětí.

Dnešní přístup do pamětí je už natolik složitý, že už ani tvrzení o sekvenčním průchodu pamětí není neotřesitelné. Když se ví jak na to, tak právě speciálním nesekvenčním přístupem se dosáhne zvýšení výkonu na dvojnásobek a možná víc. Problematika je na několik hodin vysvětlování.

Tohle se navíc skvěle kombinuje s naivním přístupem k objektovému programováním, kdy se cache používá dost strašným způsobem.

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.

[Ondra Satai Nekola]

Nebudu tvrdit, ze podceneni cache nemuze byt casty problem. Ale urcite neni jediny, jakekoli IO je daleko brutalnejsi: http://blog.codinghorror.com/the-infinite-space-between-words/

Dalsi oblibena potiz, je trebas blokovani UI threadu nejakou netrivialni cinnosti (coz je castym duvodem vnimane pomalosti Javy/Swingu).

A podobnych potencialnich problemu, jakymi lze zabit vykonost, urcite najdeme jeste vic. Nebylo dobre to omezit jen na jeden.

[Logik]

technomaniak:
Adaptuju řešiče tak, aby řešili speciální případ problému vlastních čísel. Teda sem spíš uživatel, ale např. rozdíl mezi jednotlivejma implementacema Blasu (nebo když se vezme referenční od netlibu) dost jasně cejtim a patřičně si vážim lidí, který jsou schopný napsat takový "šílenosti", jako GotoBLAS.

filip: Ale to už vůbec není záležitost cache a její organizace, ale multivláknového psaní. A tam jsou daleko větší problémy, jako správná distribuce práce, zamykání (když se dva hádaj o data, tak je to daleko větší problém než vyhazování z cache) a synchronizace, vůbec i volba algoritmu (zpravidla ten nejefektivnější není efektivně paralelizovatelnej, čili člověk musí volit podle nasazení mezi jednothreadovým a multithreadovým výkonem) atd....
Správné multithread programování je celé vyšší dívčí (multiprocesové pak vysoká dívčí) a redukovat jeho problémy na cache je dosti mimo. A naopak - multivláknové programy se sdílením dat, kde záleží na výkonu (teda ne nějaké odbavování webové aplikačky s pár konkurentníma přístupama) píše jen pár procent programátorů, možná ani to ne, takže proč by to měl znát každý programátor?

[Reklama]

[Logik]

Ondra: IO - naprostej souhlas. V okamžiku, kdy se čeká na IO, je jakákoli cache úplně jedno. Proto se také DB algoritmy měří na počty načtenejch DB stránek.

UI - to je problém ne až tak výkonu, jako latence. Z principu jdou tydle dvě věci proti sobě: buď mám kód výkonej (dělá věci postupně) nebo s nízkou latencí (často střídám úlohy se všemi z toho plynoucími nevýhodami). Samozřejmě napsat kód tak, aby byl pomalej a ještě měl velký latence jde samozřejmě taky :-)

[Filip Jirsák]

Logik: řešení (ne)zamykání považuju za algoritmus. Distribuce práce je přesně ten případ, kdy se někdy vyplatí myslet na cache - někdy se vyplatí počkat na jádro, které už má data v cache, než práci nacpat prvnímu volnému procesorovému jádru.
Netvrdím, že o procesorové cache potřebuje vědět každý programátor, ale pokud už někdo chce optimalizovat kód na téhle úrovni, ve většině případů mu daleko víc pomůže optimalizace práce s cache než používání speciálních instrukcí a přepis do strojového kódu.

Latence UI je přesně to, co uživatel subjektivně vyhodnotí jako "pomalý program".

[Ondra Satai Nekola]

@Logik

Tomu, cemu rikas vykon se u nas rikala propustnost a vykon byl neco obecnejsiho. Ale az na rozdil v terminologii s tebou samozrejme souhlasim.

[Logik]

Filip: Jo, takže všechno je algoritmus, jen řešení cache algoritmus není. Blbina - k efektívnímu využití cache se dělají speciální algoritmy úplně stejně, jako k minimalizaci počtu nutnejch zamykání. Je to problém na úplně stejný úrovni jako minimalizace počtu IO nebo minimalizace počtu nutnejch synchronizací - nejde nejprve vyřešit to a pak začít řešit cache. A oproti zmíněnejm věcem méně důležitá, protože zpomalení oproti špatně napsanému programu tu je řádově menší. A až na dodržování pár "good practice" to moc pro praktické programování nemá význam znát - nikdo to nezaplatí.

Ondra: Jo, souhlas. On výkon je defakto něco nedefinovatelnýho - někdo chce latenci, někdo propustnost. Když se to ale nespecifikuje, tak si osobně pod tím představím propustnost, ale to je asi dost tím, že toho UI moc nedělám (max ve webovejch apkách, kde zas se výkon z principu moc neřeší, protože to nikdo nezaplatí).

[nikokotvanocni]

stejně, jako k minimalizaci počtu nutnejch zamykání. Je to problém na úplně stejný úrovni jako minimalizace počtu IO nebo minimalizace počtu nutnejch synchronizací - nejde nejprve vyřešit to a pak začít řešit cache.

on se jeste najde nekdo, kdo by minimalizoval pocet zamku? tohle se razilo nekdy kolem roku 1998. prvin a posledni implementacni detaily + tuning databaze jsem videl az kolik let pote a slo o sybase ase dost do detailu rozepsany zmeny mezi releasy / verzemi databaze. jestli a proc upgradovat a jak nastavit tuningovy parametry a kde ocekavat uzky hrdlo. zadouci uz tehdy bylo neminimalizovat zamikani, ale vyvazit fragmentaci a zamykani fragmentu.

[pw]

zakaznik/uzivatel/zadavatel ale obvykle nema sanci poznat, ze provozuje suboptimalni algoritmus. obvykle ani nic takoveho nechce, neoceni a zamitne uz pri naceneni..

Ma sanci, i kdyz ta suboptimalita vypada ruzne. Z praxe SW na evidenci lidi zvladal jako blesk demo s 15 lidmi, s 500 lidmi to bylo na starsim HW citelne pomale a s 1000 lidmi to bylo i na novem HW temer nepouzitelne, nebot kazda operace trvala nekolik sekund.
Je treba vedet, kdy optimalizovat. 50us vs 100ms na jednu akci nikdo nepozna i kdyz jde o vice nez 3 rady. 100ms a 5s pri kazde operaci uz je poradny rozdil, i kdyz to nejsou ani 2 rady.

už déle platí, že překladač generuje lepší strojový kód než člověk,

Sem se skoro pokecal ...

cece, si uvedom, ze prekladac NEVI a vedet nemuze, co ten kod ma delat. VZDY, ve 100% pripadu pak dela zcela obecny preklad. Jinak receno, musi brat v potaz vsechny moznosti. Programator ovsem VI (nebo by mel), co ze ten kod ma delat, a tudiz muze (a prave v tom spociva drtiva vetsina optimalizaci) znacnou cast jednoduse vynechat.

A co priklad takoveho kodu pro GCC nebo Intelovsky kompilator se zapnutymi optimalizacemi? (myslim i optimalizace jako -ffast-math, pouzivani unsigned kde treba, -march=native)

Druha pricina prednosti prekladace je citelnost. Muzu volat funkce a(), b() a prekladac je inline-uje a tak nechutne poprehazuje instrukce mezi nimi (kvuli vyuziti pipeline), ze se v tom nikdo na prvni pohled nevyzna. To nebude nikdo cist a udrzovat.
Naproti tomu, kdyz vam programator napise vysoce optimalizovany kod prekladajici 10 cinnosti do jedne, tak bude jedina mozna oprava bugu komplet prepis. Uprava muze znamenat jeste horsi vyuziti pipeline nez neoptimalizovany kod.

Zjistis, ze naprosto totez v naprosto stejnem rozsahu zvladal o 3-5 radu pomalejsi HW.

Nebylo to naprosto totez. Kdysi se pocitali vyplaty tak, ze se nacetl kus vstupu (nebo cely) do pameti, tam se to ponasobilo v jednom cyklu a vysledek se nekam vypsal.

Ted se pocitaji vyplaty tak, ze se spusti behove prostredi, v tom se nacte 20 000 trid, spusti se 10 vlaken na GUI, GC, RMI, vsechno je to treba synchronizovat, nektere tridy se zacinaji po nekolika volanich JITovat, co znamena neoptimalni vyuziti instrukcni cache a to mame jenom prostredi. Uzivatel vyuziva nejaky framework, ktery natahne dalsich 1 000 trid, ktere jsou natolik obecne, ze zvladnou prakticky vse. Uzivatel zavola vypocet vyplaty pro kazdeho zamestnance zvlast a program ceka na data pro lazy init stub. Ten sestavi SQL query. Udela se spojeni s DB (kdyz uz neni), SQL query se zapouzdri do paketu a posle se to do DB. DB rozparsuje query a v lepsim pripade podle indexu vyhleda zaznam. Zaznam se zapouzdri tak, aby se mohl poslat, odesle se do programu. Program ze sestaveneho paketu vytahne data, precte metadata a data nacpe do objektu. Toto vsechno vyhodilo z cachi, co se vlastne melo pocitat a tak se to znova natahne. Vynasobi se 2 hodnoty, ulozi se do objektu a je to treba persistovat. Tak se zjisti, co se vlastne zmenilo a to se posila do DB (opakuje se ten cirkus). Neco jako uvolnovani pameti programator nedela a GC musi prochazet reference vzdy kdyz proto dojde pamet.
A aby se nezapomelo, cele to bezi v okynku, ktere ma pruhledne pozadi a dela pekne efekty, ktere se daji porovnat s prvnimi simulacemi vybuchu atomove bomby.

Kdyz se k tomu prida vice urovni ruznych frameworku, pro jistotu nejaka ta bezpecnost a osetrovani chyb, ktere predtim nemohli nastat, tak mame zdroj problemu. Dnesni PC nepocitaji to same. Pocitaji zbytecnosti.

[...]

zakaznik/uzivatel/zadavatel ale obvykle nema sanci poznat, ze provozuje suboptimalni algoritmus. obvykle ani nic takoveho nechce, neoceni a zamitne uz pri naceneni..

Ma sanci, i kdyz ta suboptimalita vypada ruzne. Z praxe SW na evidenci lidi zvladal jako blesk demo s 15 lidmi, s 500 lidmi to bylo na starsim HW citelne pomale a s 1000 lidmi to bylo i na novem HW temer nepouzitelne, nebot kazda operace trvala nekolik sekund.
Je treba vedet, kdy optimalizovat. 50us vs 100ms na jednu akci nikdo nepozna i kdyz jde o vice nez 3 rady. 100ms a 5s pri kazde operaci uz je poradny rozdil, i kdyz to nejsou ani 2 rady.

nema sanci. zakaznik neni koncovy uzivatel. koncovy uzivatel takove aplikace nema znalosti aby provedl popsanou analyzu a zadavatel zakaznik je od pouzivani dostatecne vzdalen a obvykle nevidi aplikaci s 500 lidmi, protoze uz po tom demu prohlasi hotovo a nechce platit zadne testy s realnou zatezi a optimalizace a rovnou to necha zavest do provozu a v provozu zase pro zmenu nevideli jak se chova demo s 15 lidmi, tak maji referencni latku chovani s 500 lidmi.

[r23]

U nás - C, C++, některé věci v ASM, a snaha část problémů přenášet a počítat na HW (FPGA).

[technomaniak]

technomaniak:
Adaptuju řešiče tak, aby řešili speciální případ problému vlastních čísel. Teda sem spíš uživatel, ale např. rozdíl mezi jednotlivejma implementacema Blasu (nebo když se vezme referenční od netlibu) dost jasně cejtim a patřičně si vážim lidí, který jsou schopný napsat takový "šílenosti", jako GotoBLAS.

Vlastní čísla matice jsou hezký problémek, taky jsem si jeden program na to napsal. A ten tvůj je pro symetrické nebo nesymetrické okolo diagonály? Jak velké ty matice obvykle máš?

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.

[j]

2technomaniak: V realu se resi daleko primitivnejsi ulohy nez matice a presto to nefunguje ani zdaleka tak, aby o tom uzivatel moh prohlasit, ze je to svizne. Naopak, pokud se resi nejaka algoritmicky narocna uloha, byva aplikaci prevazne "nehezka", ale zcela fukcni.