PV168/Optimalizace

Z FI WIKI
Verze z 18. 2. 2011, 17:14; Xadamek2 (diskuse | příspěvky)

(rozdíl) ← Starší verze | zobrazit aktuální verzi (rozdíl) | Novější verze → (rozdíl)
Přejít na: navigace, hledání

Zpět na PV168

Motivační citáty

Rules of Optimization: Rule 1: Don't do it. Rule 2 (for experts only): Don't do it yet. -- M.A. Jackson

"More computing sins are committed in the name of efficiency (without necessarily achieving it) than for any other single reason - including blind stupidity." -- W.A. Wulf

"We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil." -- Donald Knuth

"The best is the enemy of the good." -- Voltaire

"Always make it work correctly before you make it work fast." -- Unknown


ALE!

  • všechny naše programy vytváříme v prostředí s omezenými zdroji (CPU-čas, šířka síťového pásma, paměťové nároky...)
  • což se může stát životně důležitou otázkou (úzkým hrdlem, bottleneck) aplikace
  • Výše uvedené pravidlo 1 (Don't do it!) nesmí být výmluvou pro to, že neznáme optimální řešení.
  • Princip by měl být takový: Vím, jak se to dá udělat efektivněji, ale nedělám to, protože by program byl nečitelný (příp. proto, že by vývoj trval příliš dlouho).

Možnosti optimalizace

  • Různé metodiky optimalizace, stojící proti sobě
    • pro zpracovatelnost, znovupoužitelnost
      • využití kódovacích pravidel, dokumentace, využití standardních API...
    • pro rychlost
      • využití nativních metod, paměťově efektivní algoritmy, objekty...
    • velikost...

Naším úkolem je nalézt takový kompromis mezi čitelností a efektivitou, který nám bude vyhovovat.

Spouštění Java-programů

  • JVM - Java Virtual Machine - virtuální počítač pracující se zásobníkem, s vlastní instrukční sadou a správou paměti. javac kompiluje zdrojové kódy do bytekódu, což je strojový kód JVM.
    • na wikipedii přehled implementací
  • původní JVM bytekód čistě interpretovalo - pomalé
    • kompilace přímo do strojového kódu - AOT ahead of time kompilátory - stojí proti základní idei Javy
    • volání nativních metod zrychlí některé části aplikace, ne celou: JNI
  • JIT - just in time kompilace - ve chvíli, kdy se bytekód provádí, je přeložen do strojového nativního kódu (bez ukládání do cache)
    • takto vytvořený kód je rychlejší (prý až 40x vedle interpretovaného), v určitých případech (aritmetika) skoro stejně rychle jako obdobný program v C.
    • vytvořit JIT překladač z bytekódu je relativně jednoduché, nemůže docházet k velkým optimalizacím (kompilace co nejrychlejší)
    • optimalizace: např. kontroly null, kontroly mezi poli, zrychlení alokace registrů, přetypování, identifikace idiomů v bytekódu, použití inline metod (tato optimalizace je možná provést použitím parametru -o - ovšem takto je možné optimalizovat jen private, static a final metody)...
  • HotSpot - technologie využitá v moderních JIT kompilátorech, založená na adaptivní optimalizaci - v kódu jsou identifikovány oblasti, které jsou více používány, a tedy je stojí za to optimalizovat, překládat (většinou heuristika - nejčastěji volané, nejdéle běžící metody).
    • Také název aktuálního JVM firmy Sun (v SDK) - od roku 1999
    • HotSpotVM - varianty Client (důležitější rychlé spuštění programu - pro klientské aplikace) a Server(důležitější optimalizace)
  • I s JIT možné optimalizační problémy - paměťové nároky (celá aplikace nahrána do paměti, optimalizuje se, spustí se...)
  • Tyto optimalizace, celé JIT se dá vypnout pomocí přepínače -Xint - pak se bude kód jen interpretovat.
    • Javové aplikace mezi sebou nesdílí své VM, ani jiný kód, navíc je možné třídy donahrávat později

Další zdroje

Garbage Collector

  • o paměť se nestará programátor (jako v C, C++...), ale JVM
  • cyklicky se spustí vlákno, projde objekty, a zjistí, které nejsou používány
    • čili na ně nikdo neodkazuje
  • GC v Javě je (viz Wikipedia)
    • Stop-the-world (ve chvíli jeho práce se zastaví celá aplikace a čeká)
    • paralelně pracující
  • existuje explicitní volání System.gc()
    • automatické volání JVM je produktivnější, provede se kdy je potřeba, vybere se odpovídající implementace...
  • chceme-li explicitně označit odkazy, které jsou méně důležité, můžeme využít WeakReference, ty je ale potom nutné kontrolovat na null.
    • pro spolupráci s GC jsou třídy z balíku java.lang.ref

Další zdroje

Optimalizace

  • optimalizace - vylepšení vlastností kódu vs. možný zdroj dalších, i kritických chyb
  • snižuje často čitelnost kódu
  • optimalizace na jedné platformě může zhoršit výkon na jiných
  • u javy - interpretovaný jazyk - hlavní optimalizace rychlosti
  • Pravidlo 80/20 - 20% programu - ta nejdůležitější část - trvá naprogramovat 80% času. Podobně je cca 20% programu zdrojově náročných tak, že spotřebuje 80% zdrojů.
    • při optimalizaci se pak můžeme zaměřit na tyto oblasti (možnou optimalizací jiných částí programu nedostaneme odpovídající zlepšení)

Průběh optimalizace

  1. identifikace optimalizovatelných bloků
  2. optimalizace algoritmů
  3. optimalizace při překladu
    • JIT, HotSpot
      • optimalizace omezená – až při spuštění (spíš rychle generuje než generuje rychlé)
    • i nejstarší JVM provádělo některé základní optimalizační techniky - jako například eliminace mrtvého kódu, skládání konstant apod.
  4. Benchmarky
    • zjištění výkonu - porovnání různých implementací JVM/JIT kompilátorů, výkonostních charakteristik základních entit

Profiler

  • nástroj umožňující identifikovat kolik která část programu zabrala zdrojů a času. (tyto informace pak můžeme využít)
    • přímo v JVM - JVMPI (Java virtual machine profiler interface)
    • toto rozhraní pak umožňuje získaná data dále zpracovávat
      • buď pomocí použití jednoduchého konzolového profileru hprof příkazem java -Xrunhprof ToBeProfiledClass - jeho výstup je ale omezen na konzoli a tedy celkem nepřehledný (výstup v java.hprof.txt).
      • od verze JDK 1.6.0_23 je přímo součástí JDK příkaz jvisualvm integrující různá sledování včetně profileru
      • nebo různé jiné, mnohdy GUI nástroje:
    • jednoduché kontroly např. časové náročnosti lze provádět i jen kontrolou času mezi začátkem a koncem kontrolovaného kódu
  • další nástroje - kontrola zásobníku

Optimalizace algoritmu

  • mnohým problémům se zdroji programu je možné předejít
  • například rady v knize Java efektivně... 57 rad, se týkají i efektivnosti generovaného kódu
    • využití návrhových vzorů, neduplikování objektů
    • využívání tříd z Java API, správné překrývání metod, další požadavky z přednášky o OOP návrhu
    • větší využití statických či finálních konstrukcí (ty lze jednodušeji automaticky optimalizovat)
    • co největší použití privátních metod a členů
    • dobrý objektový návrh zjednodušuje i optimalizaci - lze vyměnit třídu za optimálnější bez dopadu na zbytek aplikace
    • využívání znalostí o implementaci standardních typů
      • např. využití StringBufferu místo Stringu (String se neupravuje, při jakékoli úpravě se vytváří nový objekt), či bufferovaných vstupních, výstupních proudů
    • Redukce síly (strength reduction) – nahrazení operátorů rychlejšími (x<<1 je rychlejší než x*2, dává stejný výsledek)
    • Rušení totožných podvýrazů (při matematických výpočtech)
    • Identifikace invariantů v cyklech (a jejich vypočtení jen jednou) a jiné optimalizace cyklů

Optimalizace bytekódu

  • nějakou provádí už JIT
  • jiný - např optimalizační framework Soot
  • "optimalizací" lze nazvat i různé obfuscatory, tj. nástroje, které mění bytekód tak, aby při zachování stejné funkčnosti nebylo možné z nich (pomocí javap -c) získat (skoro) původní zdrojový kód.

Další zdroje