Rychlý a úsporný kód

Kit

Re:Rychlý a úsporný kód
« Odpověď #15 kdy: 17. 12. 2014, 10:37:52 »
Dneska se nevyplatí programovat dobře (nikdo to nezaplatí), proto se dělá "odpad" za málo peněz.

Nevyplatí se ani programovat bez chyb - vždy můžeme zákazníkovi slíbit, že v další verzi budou chyby odstraněny.


wheel inventor

Re:Rychlý a úsporný kód
« Odpověď #16 kdy: 17. 12. 2014, 10:43:40 »
me prijdou usmevne ty reci o koupi rychlejsiho hw, kdyz uz 10 let procesory stagnuji...

Re:Rychlý a úsporný kód
« Odpověď #17 kdy: 17. 12. 2014, 10:49:58 »
Dneska se nevyplatí programovat dobře (nikdo to nezaplatí), proto se dělá "odpad" za málo peněz.

Nevyplatí se ani programovat bez chyb - vždy můžeme zákazníkovi slíbit, že v další verzi budou chyby odstraněny.

Neoplaca sa ani naprogramovat to cele - vzdy mozes zvysok predat ako dlc

lobo

Re:Rychlý a úsporný kód
« Odpověď #18 kdy: 17. 12. 2014, 12:03:46 »
za umenie sa plati...

vacsinou je v poziadavkach definovana nejaka casova odozva

mozes mat program ktory ti spocita X za 6 minut, co je dostatocne
potom mozes mat program ktory ti spocita X za 28 sekund

takze je na tebe sa rozhodnut ci si pockas 6 minut, alebo na tom budu pracovat 2 programatori a tester 2 tyzdne aby to zrychlili na 28 sekund (a pridat ku cene $28.700)

Kolemjdoucí

Re:Rychlý a úsporný kód
« Odpověď #19 kdy: 17. 12. 2014, 12:29:02 »
me prijdou usmevne ty reci o koupi rychlejsiho hw, kdyz uz 10 let procesory stagnuji...

Stagnuje frekvence, nikoliv výkon. To co před deseti lety řešilo deset serverů s Xeon Irwindale dnes řeší server jediný s Xeon Haswell a ještě se mírně fláká.


Re:Rychlý a úsporný kód
« Odpověď #20 kdy: 17. 12. 2014, 12:38:39 »
Dnes je najdrahsia vec cas. jednoducho radsej sa kupi drahsi hw, a nasadi sa neoptimalizovany sw hned, alebo sa mesiac bude optimalizovat a firma pride o viac penazi, ako by ju stal ten hw.
Vsetko je dnes spotrebny material, aj sw. malokto dnes ladi hotovy sw, jednoducho ked to funguje nechaj tak.

Kit

Re:Rychlý a úsporný kód
« Odpověď #21 kdy: 17. 12. 2014, 13:09:07 »
Dnes je najdrahsia vec cas. jednoducho radsej sa kupi drahsi hw, a nasadi sa neoptimalizovany sw hned, alebo sa mesiac bude optimalizovat a firma pride o viac penazi, ako by ju stal ten hw.
Vsetko je dnes spotrebny material, aj sw. malokto dnes ladi hotovy sw, jednoducho ked to funguje nechaj tak.
Pokud se jedná o algoritmy se složitostí O(1) nebo O(log(n)), tak je fakt lepší to dohnat hardwarem. Pokud je ta složitost O(n) nebo horší, je nutné změnit software.

zboj

  • *****
  • 1 507
    • Zobrazit profil
    • E-mail
Re:Rychlý a úsporný kód
« Odpověď #22 kdy: 17. 12. 2014, 13:15:47 »
Dnes je najdrahsia vec cas. jednoducho radsej sa kupi drahsi hw, a nasadi sa neoptimalizovany sw hned, alebo sa mesiac bude optimalizovat a firma pride o viac penazi, ako by ju stal ten hw.
Vsetko je dnes spotrebny material, aj sw. malokto dnes ladi hotovy sw, jednoducho ked to funguje nechaj tak.
Pokud se jedná o algoritmy se složitostí O(1) nebo O(log(n)), tak je fakt lepší to dohnat hardwarem. Pokud je ta složitost O(n) nebo horší, je nutné změnit software.

A co teprve NP-úplné nebo ještě horší algoritmy... Tam už se vyplatí najmout si "profíka".

...

Re:Rychlý a úsporný kód
« Odpověď #23 kdy: 17. 12. 2014, 15:07:43 »
Dnes je najdrahsia vec cas. jednoducho radsej sa kupi drahsi hw, a nasadi sa neoptimalizovany sw hned, alebo sa mesiac bude optimalizovat a firma pride o viac penazi, ako by ju stal ten hw.
Vsetko je dnes spotrebny material, aj sw. malokto dnes ladi hotovy sw, jednoducho ked to funguje nechaj tak.
Pokud se jedná o algoritmy se složitostí O(1) nebo O(log(n)), tak je fakt lepší to dohnat hardwarem. Pokud je ta složitost O(n) nebo horší, je nutné změnit software.
zakaznik/uzivatel/zadavatel ale obvykle nema sanci poznat, ze provozuje suboptimalni algoritmus. obvykle ani nic takoveho nechce, neoceni a zamitne uz pri naceneni..

Karel (jiný)

Re:Rychlý a úsporný kód
« Odpověď #24 kdy: 17. 12. 2014, 16:22:39 »
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.
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?

1. Jako strojaři vám doporučím příměr k automobilu. Využít HW počítače naplno je jako využít výkon auta naplno. Za určitých podmínek to lze, ale je to nepraktické a nebezpečné. Dokud byla auta slabá, tak se dala využít naplno tím, že jste prostě najel na silnici, sešlápl plyn až na podlahu a se smrtí v očích jste vyrazil rychlostí 40km/h. Na víc ten motor neměl. V zatáčkách jste ani nemusel brzdit, motor při sebemenším pohybu volantu ztrácel výkon sám o sobě. První počítače (a i dnes ty velmi slabé) na tom byly stejně. Dal jste tomu program a ony ho chroustaly vším svým výkonem. Ony to tak dělají dodnes, ale co dříve trvalo 5 minut mají dnes za 3 sekundy. A pak je to jak s auty - sice máte pod kapotou více než 100 koní a motor utáhne i 230km/h, ale vy tak rychle nejedete a ten výkon využijete jen na pár sekund při rozjezdu na křižovatce. Po zbytek doby nevyužijete výkon ani počítače, ani auta.

Tak a stejně jako existují závodní auta, tak existují i "závodní počítače". Ty jsou nasazovány pro úlohy, které využijí maximum výkonu po delší dobu. Přičemž i u těch počítačů jde vlastně o rychlost. Tedy za jak dlouho zpracuje zadanou úlohu.

2. Tady je to zase jak Lego. Dnes se programy staví z prefabrikátů, pomocí nástrojů, které vytváří unifikované "kostky". Jako Lego. Dříve (a i dnes ve specializovaných případech) se spíše používala technologie "vstřikování plastů". Výsledek byl mnohem lepší, úspornější, ale dražší a zdlouhavější. A zatímco z Lega vám něco poskládá i 10leté dítě, tak navrhnout, vyrobit a použít formu pro vstřikolis chce odborníka s praxí. A pokud zjistíte, že tam máte něco špatně, tak to Lego upravíte snáze než výlisek.

Máte pravdu v tom, že programy lze psát úsporně. Není důvod, aby jednoduchá věc musela dělat obrovskou binárku a pak zabrat desítky nebo stovky MB v paměti. Řada programů se tak dodnes píše. Jenže ono je jednodušší použít už předpřipravené kusy programů (knihovny), které bývají univerzální včetně všech negativních důsledků (prostě ssebou všude nosíte kompletní 900 stránkové Strojnické tabulky, když ve skutečnosti v nich čtete jen třídy nástrojové oceli. No a vytrhnout jen těch pár stránek nejde). Tím, jak se vyvíjí a rozšiřují tyhle knihovny, tak roste i prostorová a paměťová náročnost. Ale i dnes se dá najít dost "lightweight" knihoven na kde co, které dělají jen malou množinu věcí a neplácají tak zbytečně místo něčím, co nepotřebujete. Na webu jsou celkem v oblibě, ale v případě "větších programů" se spíš setkáte s těmi obrovskými knihovnami, programem co má 250MB a ihned po spuštění zabere 400MB paměti aniž by vlastně vůbec začal něco dělat.

3. To je jak se stroji :-) Počítačový HW je stroj jako každý jiný. Místo pohyblivých částí generujících teplo třením obsahuje miliardy součástek, kde vzniká teplo průchodem proudu a přechodovými jevy. Samotný průchod proudu nebývá problém, protože to jsou velmi malé proudy. Jenže přechodové jevy už jsou docela potvora. Nábojové pumpy, impedance a podobné legrace generují teplo kdykoliv se nabíjí/vybíjí nebo se v nich mění velikost proudu. Bývají to poměrně krátké pulsy, takže to také není samo o sobě problém. Jenže když těch pulsů začne být více, tak to teplo vzniká častěji. Obecně platí, že čím vyšší frekvence, tím více tepla vzniká. A to se musí odvádět. U obvodů s malou spotřebou (=nízké proudy) a malou frekvencí úplně stačí chlazení pouzdrem. Pokud jsou ale proudy větší, nebo roste frekvence, tak už je potřeba nějaký větší chladič, případně aktivní chlazení. Výrobce součástek měří vznikající teplo a dává doporučení na montáž i chlazení. Jednodušší součástky snesou montáž jakoukoliv, složitější už třebas vyžadují několik cm nad povrchem poudra volných, jiné proudící vzduch, jiné vyžadují chladič atd.

A rozuzlení otázky pak spočívá v dodržení doporučení výrobce součástky a pokročilými technologiemi správy spotřeby. Když dodržíte doporučení výrobce na chlazení, tak součástku neupečete. Bohužel řada výrobců HW toto nedodrží (šetří na chladiči nebo na místě, případně nezvládnou údržbu a chladící kanály se ucpou atd.) A pak záleží na těch technologiích správy spotřeby. Řada složitějších obvodů, kam patří třebas mikroprocesory, dokáží nějakým způsobem analyzovat zátěž a dokáží na to reagovat. Měří třebas "wait stavy" (kdy nebyly instrukce ke zpracování) a podle toho snižuje frekvenci. Nebo rovnou odpojuje části obvodů, jako jsou dodatečná jádra apod. To je na jednu stranu fajn, ale je to vražedná kombinace s "poddimenzovaným chlazením". Protože vám taková součástka v daném zařízení může měsíce i roky pracovat bez problémů, ale pak přijde najednou úloha, která té součástce "sedne" a ta začne aktivovat všechny části obvodu a zvyšovat frekvenci na nominální. A najednou zjistíte, že to ten chladič neuchladí a máte problém. Naštěstí v mikroprocesorech bývá senzor teploty, který ho odpojí. Ale nemusí fungovat včas nebo dobře. Například se vám přehřeje a spálí část, která je daleko od senzoru, případně se přehřála rychleji, než to senzor odpojil.

Takže ano, pokud je zařízení špatně zkonstruováno, tak můžete "vhodně napsaným programem" způsobit přehřátí a nějakou část zařízení poškodit. Je to ale důsledek chyby konstrukce, kdy chladič nedokáže uchladit "špičkový ztrátový výkon". Ten je výrobcem součástek specifikován a přes něj se programově nedostanete. Čili vhodně napsaným programem se k tomuto mezníku můžete přiblížit, ale přes něj to nejde, protože procesor už víc nezrychlí a ani nemá nic dalšího co zapnout. A tady ještě zmíním "overclocking". To dělají lidé, kteří chtějí zvýšit výkon zařízení tím, že nějak donutí ho pracovat na vyšší než nominální frekvenci. Procesory a základní desky na to dnes běžně nabízejí podporu. Zvednou tím "maximální možnou rychlost", ale v důsledku toho i "generované teplo". A jsme zpátky u toho, zda to zvládnou uchladit. Proto běžně kupují lepší chladiče, chladí vodou, kupují větší počítačové skříně s dodatečnými větráky atd. U procesorů, pamětí apod. "naštěstí" platí, že přestanou fungovat dříve, než shoří. Prostě když se procesor přehřeje, tak se počítač zasekne nebo sám restartuje. Po ochlazení zase začnou fungovat. Pokud to ale někdo hodně přežene, případně si pomůže zvýšením napětí, tak to pořád spálit může. Pokud se přidá porucha chlazení, tak je to riziko dost velké.

4. Tak o tomhle konkrétně nevím.

Technik jak psát rychlé programy je mraky. Není žádný jeden univerzální návod. A ani přístup není jednotný. Pro některé typy úloh je vhodné jít na nejnižší úroveň a psát přímo v assembleru (minimum ztrát zbytečnostmi), jindy je vhodné použít knihovnu někoho "chytrého" (správně napsaný komplexní algoritmus, třebas pro řazení nebo složité matematické operace). Ve většině případů je to ale jedno, protože úloha je provedena v tak krátké době, že to zrychlení nestojí za to. Jestli se vám stránka načítá 235ms nebo 17ms vás až tak trápit nebude, přestože je to rozdíl ve výkonu o celý řád. Na složitější úlohy jsou lepší již hotové knihovny. Kupříkladu napsat si správně merge sort dalo práci a i tak jsem byl pomalejší než knihovna, protože její autor použil i pár triků, o kterých jsem dříve neslyšel (ale fakt, že moje verze byla bez ohledu na velikost dat vždy jen cca 3x pomalejší mě potěšil, protože to byl důkaz, že v zásadě jsem to měl správně). Pokud programujete něco, co není algoritmicky složité, ale máte omezené prostředky (slabý HW nebo málo času), tak se vyplatí jít do něčeho na nižší úrovni (nemusí to být nutně assembler). Ale nic z toho co jsem napsal není zcela univerzálně platné. Vždy je to o zvážení možností a priorit. Ale s tím se jako strojař setkáváte často. Titan je sice fajn materiál, ale někdy kvůli ceně, jindy zase kvůli náročnosti na opracování, prostě použijete ocel. A pak po pár letech zjistíte, že jste ten titan nepoužil nikdy, ačkoliv z hlediska vlastnostní byl skoro vždy ideální.

j

Re:Rychlý a úsporný kód
« Odpověď #25 kdy: 17. 12. 2014, 17:20:01 »
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.

Jina vec je, jestli to nekdo zaplati, ale o tom uz rec byla.

Dneska se nevyplatí programovat dobře (nikdo to nezaplatí), proto se dělá "odpad" za málo peněz.

Nevyplatí se ani programovat bez chyb - vždy můžeme zákazníkovi slíbit, že v další verzi budou chyby odstraněny.
Hlavne se mu pak da prodat maintenance. Kdo by to platil, kdyz mu vse funguje, ze.

me prijdou usmevne ty reci o koupi rychlejsiho hw, kdyz uz 10 let procesory stagnuji...
Usmevny ti to prijit muze, ale rozhlidni se kolem. 99% uloh ktery se resej jsou naprosto primitivni veci. Spocitani vejplat, spocitani ceny, ... z pohledu CPU trivialni operace scitani/odecitani/nasobeni/deleni. A pak se poinformuj, jak se to delalo pred 10ti, 15ti, 20ti lety. Zjistis, ze naprosto totez v naprosto stejnem rozsahu zvladal o 3-5 radu pomalejsi HW. Jak je to mozny? Co myslis, zvlad by dneska Z80 vejplaty? Ja myslim ze s prstem v nose. Jenze zvlad by to pro nej nekdo naprogramovat? Vzdyt jen otevrit dialog "spocitat ano/ne" by takovych CPu potreboval 100.

wheel inventor

Re:Rychlý a úsporný kód
« Odpověď #26 kdy: 17. 12. 2014, 18:34:59 »
me prijdou usmevne ty reci o koupi rychlejsiho hw, kdyz uz 10 let procesory stagnuji...
Usmevny ti to prijit muze, ale rozhlidni se kolem. 99% uloh ktery se resej jsou naprosto primitivni veci. Spocitani vejplat, spocitani ceny, ... z pohledu CPU trivialni operace scitani/odecitani/nasobeni/deleni. A pak se poinformuj, jak se to delalo pred 10ti, 15ti, 20ti lety. Zjistis, ze naprosto totez v naprosto stejnem rozsahu zvladal o 3-5 radu pomalejsi HW. Jak je to mozny? Co myslis, zvlad by dneska Z80 vejplaty? Ja myslim ze s prstem v nose. Jenze zvlad by to pro nej nekdo naprogramovat? Vzdyt jen otevrit dialog "spocitat ano/ne" by takovych CPu potreboval 100.

Nevim jakou to ma spojitost s tim co jsem psal...

Casto vidim ze lidi si justifikujou prasacky programovani tim, ze se na to nasadi silnejsi hw, jenze silnejsi hw neni a v blizky dobe asi ani nebude...

JSH

Re:Rychlý a úsporný kód
« Odpověď #27 kdy: 17. 12. 2014, 20:59:52 »
Tak k tomuhle seznamu bych měl pár výhrad...
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)
Asymptotická složitost je dost abstraktní věc a překvapivě často má smysl vzít algoritmus s teoreticky horší složitostí, ale rychlejší v praxi. Bývá rychlejší přidávat prvky doprostřed pole (rozumné velikosti), než místo toho použít spojový seznam, protože lepší složitost dokonale přebije tragické využití cache spojovým seznamem. A to ještě ani nemluvím o té zanedbané konstantě. Nechci říct, že je složitost k ničemu, ale rozhodně to není nějaký spolehlivý ukazatel toho, jak rychle kód pojede.
Citace
- 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ší
SSE, AVX a v podstatě i GPU se hodí jen na určitou třídu úloh. Pokud to nejsou nějaké jednoduché iterace přes pole, tak bývá problém. Další věc je, že pokud se hodně nepočítá nad malými oblastmi paměti, tak je úzké hrdlo stejně sběrnice.
Citace
...
- 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.
Tak tady bych zatraceně nesouhlasil. Jestli je jedna věc, kterou by _každý_ programátor měl znát, tak je to funkce cache. Momentálně je to to nejužší hrdlo prakticky v _každém_ programu. V generování kódu překladač strčí do kapsy tak 90% programátorů, ale se zprasenýma datovýma strukturama neudělá ani ň. 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.

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í. Doporučím článekhttp://www.akkadia.org/drepper/cpumemory.pdf. Název "What Every Programmer Should Know About Memory" není vůbec nadsazený.

Re:Rychlý a úsporný kód
« Odpověď #28 kdy: 17. 12. 2014, 21:20:20 »
Tak tady bych zatraceně nesouhlasil. Jestli je jedna věc, kterou by _každý_ programátor měl znát, tak je to funkce cache. Momentálně je to to nejužší hrdlo prakticky v _každém_ programu. V generování kódu překladač strčí do kapsy tak 90% programátorů, ale se zprasenýma datovýma strukturama neudělá ani ň. 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.
Naprostý souhlas. Nejvíc se zoptimalizuje změnou způsobu práce, pak změnou algoritmu. A když už na tom není co vylepšovat, pokračoval bych právě optimalizací vzhledem k cache, speciální instrukce až potom, ty budou mít obvykle menší vliv. Pokud to není nějaký matematický výpočet, použije se těch speciálních instrukcí pár. Oproti tomu když v nějaké smyčce při každé iteraci budu muset data načítat z hlavní paměti místo z cache, promrhám tím mnohem víc času.
Kompilátor nějakého vysokoúrovňového jazyka by datové struktury teoreticky mohl optimalizovat, ale C kompilátor vám rozhodně nemůže přeskládat prvky ve struct, ze spojového seznamu udělat pole a z pole pointerů udělat pole struct.

Logik

  • *****
  • 1 031
    • Zobrazit profil
    • E-mail
Re:Rychlý a úsporný kód
« Odpověď #29 kdy: 17. 12. 2014, 22:34:31 »
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.

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.

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