Rychlý a úsporný kód

Magirus

Rychlý a úsporný kód
« kdy: 17. 12. 2014, 01:09:07 »
Fórum na rootu navštěvuji už delší dobu pouze pasivně a jsem si vědom toho, že je tu mnoho profíků z praxe. Proto se předem omlouvám za své, poněkud amatérské otázky, jelikož nejsem programátor, ale studuji VŠ strojního zaměření. Nicméně počítače mě vždy hodně zajímaly a chtěl bych do programování proniknout.

1. Vždy mě velice zajímalo, jakým způsobem se dají psát programy, které využijí HW daného počítače opravdu na maximum. Nicméně jakými způsoby se toho dá docílit. V případě výpočtových aplikací (simulací) to je zřejmě optimalizace daného matematického výpočtu a v případě klasických uživatelských aplikací vůbec netuším.

2. Jde v návaznosti na velkou rychlost kódu dělat ty programy úsporně, tzn. ve výsledku s malým obsazením operační paměti? Osobně se mi moc nelíbí dnešní trend kdy aplikace podobného nebo stejného účelu jako před 10 lety má mnohdy o dost vyšší paměťové nároky. Tím zde nemyslím třeba fyzikální simulace, kde se např. pracuje s velkými číselnými maticemi apod.

3. Může dojít díky velice rychlému kódu dokonce i k přehřátí procesoru?

4. 1-2 roky nazpět zde bylo téma, jehož název si bohužel nepamatuju, ale něco podobného na způsob rychlosti aplikací se tam řešilo. Byla tam myslím i řeč k některých matematických knihovnách typu LAPACK a někdo tam dával odkaz na projekt, myslím že to bylo nějaké americké univerzity, kde výsledkem byla asi knihovna na provádění matematických operací, která snad způsobovala, že daný program (nebo jen určité části kódu) donutily využívat CPU pouze registry po určitou delší dobu a nepřistupovat do operační paměti, čímž se radikálním způsobem zrychlil běh daného programu (výpočtu). Já jen, kdyby někdo náhodou tušil název toho vlákna.

Předpokládám, že ti co dokážou psát velice rychlý a paměťově úsporný kód, jsou prostě profíci z praxe. Nicméně byly by nějaké rady pro začátečníka ohledně třeba programovacích technik či způsobů jak se k těmto dovednostem také dopracovat?


MBig

Re:Rychlý a úsporný kód
« Odpověď #1 kdy: 17. 12. 2014, 03:28:54 »
1. Pouzivas treba specialni instrukce procesoru (ktere vykonaji rychleji casto pouzivane matematicke operace pouzivane treba u zpracovani signalu) nebo k vypoctum pouzijes grafickou kartu (napr. nVidia CUDA)

2. To neni pravidlo, jestli pouzijes nejaky graficky toolkit treba Qt, vypada to hezky, je s tim malo prace ale je to narocne... naopak kdyz napises jednoduchou textovou aplikaci, nebo treba pouzijes ncurses (grafika v terminalu), narocnost nebude tak velka. A dnesni pocitace maji vice RAM nez predtim, tak proc to nevyuzit.

3. Rychly kod? Asi myslis vypocetne intenzivni ulohu... Dneska asi tezko, procesor ma ochranu a pri vysoke teplote se vypne.

4. Tu knihovnu neznam, ale treba v C lze rict ze dana promenna bude v registru. Ale ne vzdy to kompilator tak udela, protoze to nemusi byt vzdy rychlejsi.

Velice rychly kod dneska za tebe udela kompilator, ktery dokaze delat optimalizace na ktery bezny smrtelni neprijde. Jestli chces radu, nauc se C a assembler a hraj si stim, podivej jak kompilator kompiluje, zkus si napsat program za pouziti specialnich instrukci a pak bez nich a porovnej rychlosti apod.

MBig

Re:Rychlý a úsporný kód
« Odpověď #2 kdy: 17. 12. 2014, 03:33:08 »
Dneska asi tezko, procesor ma ochranu a pri vysoke teplote se vypne.

Tady sem se trochu ukvapil, ptal ses jestli se muze prehrat - muze, kdyz nebude stihat chlazeni (napr. zaneseny chladic prachem), ale neznici se, protoze se diky ochrane vypne.

h7

Re:Rychlý a úsporný kód
« Odpověď #3 kdy: 17. 12. 2014, 04:37:23 »
1. Dříve se takové programy nebo části programů psaly v assembleru, dneska už jsou optimalizující překladače jazyků jako C apod. často "chytřejší" než programátor (nebo by to programátorovi trvalo tak dobře trvalo příliš dlouho, protože se píší pořád rozsáhlejší aplikace). Dnešní procesory mají většinou více jader, takže je třeba paralelizovat. Používání grafických nebo jiných speciálních čipů zejména pro paralelní "stejnorodé" zpracování většího množství dat.

2. Záleží na řešeném problému a algoritmu. Tím jsi limitovaný. A pak můžeš omezit balast v podobě nějakých neefektivních knihoven, běhových prostředí, operačních systémů apod. - samozřejmě ale zaplatíš ztrátou pohodlí při programování, protože ty knihovny tě odstíní od řady problémů a zjednoduší ti práci.

3. Záleží na HW. U dnešních procesorů pro PC těžko, procesory v případě počátku přehřívání automaticky zpomalí (vkládání prázdných cyklů apod.). Pokud rychlým kódem myslíš efektivní kód, tak ten ani nemusí způsobovat nějaké

4. Třeba Intel prodává různé knihovny, které řeší určité typické základní problémy a má je napsané tak, aby na jeho procesorech byly vysoce efektivní.

Z. Potřebuješ mít rozhled základní rozhled v HW (jak to obecně funguje - procesoru, paměti, instrukce apod.), algoritmech, nějaký nižší programovací jazyk - zejména C, hodí se alespoň pasivně Assembler (když to bude ladit a hledat možnosti zrychlení) atd. Obecně je dnes ale výkon počítačů poměrně levný (oproti ceně programátora), takže snažit se psát všechno efektivně nedává smysl. Optimalizovat dává smysl typicky jen nějaké malé části programu, které spotřebovávají většinu zdrojů (CPU, RAM apod.).

ahorek

Re:Rychlý a úsporný kód
« Odpověď #4 kdy: 17. 12. 2014, 05:44:06 »
Rychlost kódu dnes závisí také na délce vývoje. V komerční sféře málokdo zaplatí peníze za superoptimalizovaný kód, protože koupit lepší HW, který to utáhne je prostě většinou levnější než platit člověka, který to vytuní. Optimalizují se pouze věci, kde se to vyplatí a je to poznat - dlouhotrvající, výpočtově náročné nebo časté operace + na slabý HW jako jsou mobily, kde se navíc počítá s výdrží na baterii (rychlejší kód tolik nežere).
Větší aplikace (ne akademická dema) se obvykle píší v nějakém vyšším programovacím jazyce (např. Java) nebo frameworku a pro kritické věci se část napíše v C++ nebo assembleru (ten už dnes moc ne). Často je důležitější spolehlivost a udržovatelnost (čitelnost) kódu než nějaké lowlevel optimalizace.
Vyšší paměťová náročnost často může přinést i zrychlení programu, existují techniky např. na ukládání mezivýpočtů, cachování apod.

Příklady optimalizací?
- úprava složitosti algoritmu, tím se obvykle získá nejvíc a nezávisí to na použitém jazyce (akademický příklad - místo pomalého bubble sortu se použije quick sort)
- využití SSE/AVX instrukcí - dnes jsou kompilátory dost chytré, a aby člověk vymyslel rychlejší kód, tak většinou musí vědět co dělá, výsledek může být i pomalejší
- kompilace pro x64 - má význam pouze pokud se počítá s velkými čísly (tam je téměř 100% výkonu nahoru), u obyčejných aplikací je výkon +- stejný, někdy i nepatrně nižší. Výhodou je spíše možnost využít více ram (32bit aplikace má tuším max 2GB/proces a <4GB/systém)
- vícevláknový kód - pro výpočet se použije více procesorů, což výrazně zrychlí výpočty a využije dostupný výkon, ale ne každý algoritmus jde takto rozdělit (problém je, když jsou na sobě výpočty závislé, a také je zde větší náchylost k chybám)
- výpočet přes GPU, podobný problém jako u vícevláknového kódu (GPU si lze představit jako hodně (50-3000 dle typu) malých pomaých procesorů), když se kód správně rozloží, může být výpočet mnohonásobně rychlejší. Na serverech ale kromě vysoce specializovaných úloh GPU nebývá. Zatím se to využívá např. k akceleraci dekódování videa nebo výpočtům fyziky v hrách. Jako framework se používá Cuda (nvidia only) a Opencl (multiplatformní).
- u hrátek typu uložím si data do procesorové cache je třeba brát v úvahu, jak jsou ty cache velké, rozdílné parametry procesorů atd. Obecně platí nějaké hierarchie od nejrychlejšího k nejpomalejšímu přístupu - L1-L2..-RAM-HDD-NETWORK. Výkon se tím sice získat dá, ale kompilátor to obvykle řeší dostatečně dobře, že kromě speciálních matematických knihoven takové optimalizace v reálu nemají smysl.


Re:Rychlý a úsporný kód
« Odpověď #5 kdy: 17. 12. 2014, 07:20:24 »
Ad 1) Využijete co nejvíc vlastností daného hardware, které jde použít pro urychlení kódu. Např. pokud má procesor speciální instrukce pro nějaké výpočty, použijete je - často se o to postará správně nastavený kompilátor. Pokud můžete využít výpočet na grafické kartě, využijete ho. Pokud má procesor více jader nebo systém více procesorů, napíšete kód paralelně, aby mohl běžet ve více vláknech. Pokud máte vícevláknový kód, minimalizujete případy, kdy na sebe vlákna musejí čekat. Dále má dnešní hardware spoustu optimalizací kvůli rychlosti, takže je potřeba kód napsat tak, aby tyhle optimalizace fungovaly správně. Například predikce skoků v procesoru, nebo ukládání dat v cache procesoru (data, která bude procesor používat, umístit v paměti k sobě tak, aby se vešla do řádky cache nemusela se načítat z pomalé hlavní paměti). A tak dále.
V případě uživatelských aplikací nezáleží tolik na tom, jak je aplikace fakticky rychlá, ale na tom, jaký má z jejího používání uživatel pocit. Základní věc je to, že náročné operace se nedělají ve vláknu, které obsluhuje uživatelské rozhraní. Takže při takové operaci nemá uživatel pocit, že aplikace zamrzla, ale reaguje na jeho podněty (v takové situaci toho uživatel zpravidla stejně nemůže moc udělat, ale aspoň třeba může přerušit tu déletrvající akci). Dál už záleží na tom, co ta aplikace dělá, ale hrubý výkon málokdy hraje roli. Možná ještě u her nebo přehrávání videa. Ale jinak je často mnohem důležitější to, jak aplikace pracuje s daty - pokud pracuje se soubory na disku, zda dokáže načítat data dopředu, pokud s databází, zda používá takové dotazy, které se vyhodnotí rychle atd. A podstatné je i to, jak je navrženo ovládání aplikace - pokud se musí uživatel někam složitě proklikávat, bude aplikace nakonec pomalá, i když by byl kód velmi rychlý.

Ad 2) Nejjednodušší pravidlo je, že mezi rychlostí a použitou pamětí je nepřímá úměra - máte na výběr, zda si program nějakou hodnotu zapamatuje, nebo zda ji vypočítá. Samozřejmě z pak existuje spousta případů, kdy tohle neplatí - když se zaplní paměť nesmysly, kód to nijak neurychlí, naopak správa velkého objemu paměti má větší režii.

Ad 3) Nemělo by, procesor by měl být chlazený tak, aby zvládl pracovat i na nejvyšší výkon. Dnešní počítačové procesory mají navíc ochrany, které v případě překročení teploty umí procesor zpomalit (např. vkládáním méně náročných prázdných instrukcí).

Ad 4) Ano, to je jedna z věcí, o kterých jsem psal v 1) - uspořádat data tak, aby měl procesor co nejvíc potřebných dat co nejblíž a nemusel čekat na data z hlavní paměti nebo na zámek od jiného procesoru.

Kolemjdoucí

Re:Rychlý a úsporný kód
« Odpověď #6 kdy: 17. 12. 2014, 08:39:31 »
1. Vždy mě velice zajímalo, jakým způsobem se dají psát programy, které využijí HW daného počítače opravdu na maximum.

C/C++ a v tom kusy ASM nebo intrinsics. Ruční psaní kódu s SSE, AVX apod.

2. Jde v návaznosti na velkou rychlost kódu dělat ty programy úsporně, tzn. ve výsledku s malým obsazením operační paměti?

Paměti program spotřebuje tolik, kolik programátor uzná za vhodné. Většinou paměť žerou nenažrané multiplatformní GUI knihovny.

3. Může dojít díky velice rychlému kódu dokonce i k přehřátí procesoru?

S předepsaným chladičem naprosto vyloučeno.

Předpokládám, že ti co dokážou psát velice rychlý a paměťově úsporný kód, jsou prostě profíci z praxe. Nicméně byly by nějaké rady pro začátečníka ohledně třeba programovacích technik či způsobů jak se k těmto dovednostem také dopracovat?

Nastudovat si to tady zde:
http://www.intel.com/content/www/us/en/processors/architectures-software-developer-manuals.html

Celkově počítej s tím, že v tom strávíš tak rok času a jen těžko ti za tyto schopnosti dneska někdo zaplatí.

- využití SSE/AVX instrukcí - dnes jsou kompilátory dost chytré, a aby člověk vymyslel rychlejší kód, tak většinou musí vědět co dělá, výsledek může být i pomalejší
- kompilace pro x64 - má význam pouze pokud se počítá s velkými čísly (tam je téměř 100% výkonu nahoru), u obyčejných aplikací je výkon +- stejný, někdy i nepatrně nižší. Výhodou je spíše možnost využít více ram (32bit aplikace má tuším max 2GB/proces a <4GB/systém)

Využití SSE/AVX automaticky kompilátory je v plenkách.
x64 má k dispozici 2x tolik registrů než x86, když se to umí využít, tak je to znát očividně.

Kit

Re:Rychlý a úsporný kód
« Odpověď #7 kdy: 17. 12. 2014, 08:58:12 »
... jelikož nejsem programátor, ale studuji VŠ strojního zaměření...

1. Vždy mě velice zajímalo, jakým způsobem se dají psát programy, které využijí HW daného počítače opravdu na maximum. Nicméně jakými způsoby se toho dá docílit. V případě výpočtových aplikací (simulací) to je zřejmě optimalizace daného matematického výpočtu a v případě klasických uživatelských aplikací vůbec netuším.

Se strojním zaměřením doporučuji Matlab, jeho free alternativu Octave nebo Fortran. Céčko ani assembler nedoporučuji, Fortran se na strojírenské výpočty hodí mnohem lépe.
[/quote]

zboj

  • *****
  • 1 507
    • Zobrazit profil
    • E-mail
Re:Rychlý a úsporný kód
« Odpověď #8 kdy: 17. 12. 2014, 09:09:40 »
S rychlostí kódu dnes nebývá problém, překladače C/C++ používají sofistikované optimalizace a JIT v jazycích jako Java nebo C# (resp. cokoliv v .NET) generuje velmi rychlý kód. Assembler se v obecném případě nepoužívá, už déle platí, že překladač generuje lepší strojový kód než člověk, a dnes je navíc mnohdy žádoucí překládat stejný kód pro Intel (32 a 64-bitový) a ARM, takže těch "asemblerů" je několik (ARM pomalu prosazuje i svou 64-bitovou architekturu, takže celkem to jsou nejméně čtyři různé platformy).

Co se týče paměti, zde jde o to, jestli se použije (plnohodnotný) GC. GC má totiž řádově vyšší nároky na paměť ("high water mark") a jakmile paměť začne docházet, řádově se zpomalí. Proto se často používá "automatic reference counting" (Apple ho má všude a Microsoft ve WinRT), jež zajistí automatickou správu paměti bez nevýhod GC. Navíc v C++ využívá dobrý kód možnost alokace na zásobníku, což je ještě úspornější.

Nejlepší praktická rada tedy je zaměřit se na C++ a pochopit, jak v něm funguje správa paměti. Rychlost výsledného nativního kódu bych neřešil, překladače vesměs generují nejlepší možný kód,

Kolemjdoucí

Re:Rychlý a úsporný kód
« Odpověď #9 kdy: 17. 12. 2014, 09:35:51 »
už déle platí, že překladač generuje lepší strojový kód než člověk

Na to rychle zapomeňte, zkušený assemblerista porazí kompilátor vždy a to až o dva řády. Ve hře jsou pro vyšší jazyky zcela neznámé možnosti, jako vykonávání až 5 instrukcí jednoho vlákna paralelně v jednom čase, 2-3 paralelní přístupy jednoho vlákna do paměti v jednom čase, přímá kontrola cacheování, přednačítání dat a podobné věci. Průměrný programátor C#/Java nemá kognitivní aparát si tyto věci vůbec představit.

To nijak neovlivňuje skutečnost, že poptávka po takových lidech není a asi nemá moc smysl se tím zabývat.

Kit

Re:Rychlý a úsporný kód
« Odpověď #10 kdy: 17. 12. 2014, 09:44:49 »
už déle platí, že překladač generuje lepší strojový kód než člověk

Na to rychle zapomeňte, zkušený assemblerista porazí kompilátor vždy a to až o dva řády. Ve hře jsou pro vyšší jazyky zcela neznámé možnosti, jako vykonávání až 5 instrukcí jednoho vlákna paralelně v jednom čase, 2-3 paralelní přístupy jednoho vlákna do paměti v jednom čase, přímá kontrola cacheování, přednačítání dat a podobné věci. Průměrný programátor C#/Java nemá kognitivní aparát si tyto věci vůbec představit.

To nijak neovlivňuje skutečnost, že poptávka po takových lidech není a asi nemá moc smysl se tím zabývat.

Docela úsměvná představa, že se strojař bude hrabat v assembleru, aby ušetřil pár nanosekund.

Kolemjdoucí

Re:Rychlý a úsporný kód
« Odpověď #11 kdy: 17. 12. 2014, 09:46:38 »
Docela úsměvná představa, že se strojař bude hrabat v assembleru, aby ušetřil pár nanosekund.

Napsal jsem dostatečně jasně, že nemá smysl se tím zabývat.

Re:Rychlý a úsporný kód
« Odpověď #12 kdy: 17. 12. 2014, 10:04:58 »

Daniel Kozak

Re:Rychlý a úsporný kód
« Odpověď #13 kdy: 17. 12. 2014, 10:21:56 »
Co se týče paměti, zde jde o to, jestli se použije (plnohodnotný) GC. GC má totiž řádově vyšší nároky na paměť ("high water mark") a jakmile paměť začne docházet, řádově se zpomalí. Proto se často používá "automatic reference counting" (Apple ho má všude a Microsoft ve WinRT), jež zajistí automatickou správu paměti bez nevýhod GC.

No ono to ARC ma taky spoustu nevyhod, a ve vysledku ma vetsi reziji nez dobre napsany GC

Re:Rychlý a úsporný kód
« Odpověď #14 kdy: 17. 12. 2014, 10:29:33 »
JAVA a .net chrlí rychlý kód :) fakt jsem se hodně zasmál a pak se tu začne řešit Garbage collection jako vtip hodně dobrý.
Dneska se nevyplatí programovat dobře (nikdo to nezaplatí), proto se dělá "odpad" za málo peněz.

Ty lepší firmy primárně vytváří SW třeba na VXWorksu nebo i pod Linuxem v C++ prokládaný ASM instrukcemi.
Je to ale odporně drahé... a to železo je tak levné  ;D
„Řemeslo se naučí každý. Umění nikdo.“
„Jednoduchost je nejvyšší úroveň sofistikovanosti.“
- Leonardo Da Vinci