Optimalizace (informatika)

Optimalizace je úprava systému za účelem zlepšení jeho účinnosti. Systém může být jeden počítačový program , digitální zařízení, sbírka počítačů nebo dokonce celá síť.

Přestože cílem optimalizace je získat optimální systém, ne vždy se v procesu optimalizace dosáhne skutečně optimálního systému. Optimalizovaný systém je obvykle optimální pouze pro jeden úkol nebo skupinu uživatelů: někde může být důležitější zkrátit dobu potřebnou k dokončení práce programu , a to i za cenu větší spotřeby paměti; v aplikacích, kde je důležitější paměť, lze zvolit pomalejší algoritmy s menšími požadavky na paměť.

Navíc často neexistuje žádné univerzální řešení (fungující dobře ve všech případech), takže inženýři používají kompromisní řešení k optimalizaci pouze klíčových parametrů. Kromě toho úsilí potřebné k dosažení zcela optimálního programu, který nelze dále vylepšovat, téměř vždy převyšuje přínos, který z toho lze získat, takže proces optimalizace je zpravidla dokončen před dosažením plné optimality. Naštěstí se ve většině případů i s tímto dosáhne znatelných zlepšení.

Optimalizaci je třeba provádět opatrně. Tony Hoare nejprve řekl a Donald Knuth později často opakoval slavné rčení: „Kořenem všeho zla je předčasná optimalizace. Pro začátek je velmi důležité mít vyjádřený algoritmus a funkční prototyp.

Základy

Některé úkoly lze často provádět efektivněji. Například program v C , který sčítá všechna celá čísla od 1 do N:

int i , součet = 0 ; pro ( i = 1 ; i <= N ; i ++ ) součet += i ;

Za předpokladu, že zde nedochází k přetečení , lze tento kód přepsat následovně pomocí příslušného matematického vzorce :

int součet = ( N * ( N + 1 )) / 2 ;

Termín „optimalizace“ obvykle znamená, že si systém zachová stejnou funkčnost. Významného zlepšení výkonu však lze často dosáhnout odstraněním nadbytečných funkcí. Například za předpokladu, že program nepotřebuje podporovat více než 100 prvků na vstupu , je možné místo pomalejší dynamické alokace použít statickou alokaci .

Kompromisy

Optimalizace se zaměřuje především na dobu jednoho nebo opakovaného spuštění, využití paměti, místo na disku, šířku pásma nebo nějaký jiný zdroj. To obvykle vyžaduje kompromisy – jeden parametr je optimalizován na úkor ostatních. Například zvýšení velikosti softwarové mezipaměti něčeho zlepšuje výkon za běhu, ale také zvyšuje spotřebu paměti. Mezi další běžné kompromisy patří transparentnost kódu a výraznost, téměř vždy za cenu deoptimalizace. Složité specializované algoritmy vyžadují větší úsilí při ladění a zvyšují pravděpodobnost chyb .

Různé oblasti

V operačním výzkumu je optimalizace problémem určení vstupních hodnot funkce, pro kterou má maximální nebo minimální hodnotu. Někdy existují omezení na tyto hodnoty, taková úloha je známá jako omezená optimalizace .

V programování optimalizace obvykle znamená úpravu kódu a jeho nastavení kompilace pro danou architekturu , aby se vytvořil efektivnější software.

Typické problémy mají tolik možností, že programátoři obvykle mohou dovolit použít pouze „dost dobré“ řešení.

Úzká místa

Chcete-li optimalizovat, musíte najít úzké místo ( anglicky bottleneck - bottleneck): kritická část kódu, která je hlavním spotřebitelem potřebného zdroje. Zlepšení asi 20 % kódu někdy znamená změnu 80 % výsledků podle Paretova principu . Únik prostředků (paměti, handle atd.) může také vést k poklesu rychlosti provádění programu. K hledání takových úniků se používají speciální ladicí nástroje a profilery k detekci úzkých míst .

Architektonický návrh systému má obzvláště silný vliv na jeho výkon. Volba algoritmu ovlivňuje efektivitu více než jakýkoli jiný konstrukční prvek. Složitější algoritmy a datové struktury dokážou dobře zpracovat velké množství prvků, zatímco jednoduché algoritmy jsou dobré pro malá množství dat – režie inicializace složitějšího algoritmu může převážit výhody jeho použití.

Čím více paměti program používá, tím rychleji obvykle běží. Například program pro filtrování obvykle čte každý řádek, filtruje a vydává tento řádek přímo. Paměť tedy využívá pouze k uložení jednoho řádku, jeho výkon je však obvykle velmi špatný. Výkon lze výrazně zlepšit přečtením celého souboru a následným zápisem filtrovaného výsledku, avšak tato metoda využívá více paměti. Ukládání výsledků do mezipaměti je také efektivní, ale vyžaduje více paměti.

Nejjednodušší techniky pro optimalizaci programů z hlediska času CPU

Optimalizace z hlediska času procesoru je důležitá zejména u výpočetních programů, ve kterých mají velký podíl matematické výpočty. Zde jsou některé optimalizační techniky, které může programátor použít při psaní zdrojového kódu programu.

Inicializace datového objektu

V mnoha programech musí být některá část datových objektů inicializována , to znamená, že jim musí být přiřazeny počáteční hodnoty. Takové přiřazení se provádí buď na samém začátku programu, nebo například na konci smyčky. Správná inicializace objektu šetří cenný čas CPU. Takže například pokud jde o inicializaci polí, použití smyčky bude pravděpodobně méně efektivní než deklarování tohoto pole za přímé přiřazení.

Programování aritmetických operací

V případě, kdy je značná část času programu věnována aritmetickým výpočtům, jsou značné rezervy pro zvýšení rychlosti programu skryty ve správném programování aritmetických (a logických) výrazů. Je důležité, že různé aritmetické operace se výrazně liší v rychlosti. Na většině architektur jsou nejrychlejší operace sčítání a odčítání. Násobení je pomalejší, následuje dělení. Například výpočet hodnoty výrazu , kde je konstanta, pro argumenty s plovoucí desetinnou čárkou se provádí rychleji ve tvaru , kde je konstanta vypočtena ve fázi kompilace programu (ve skutečnosti je operace pomalého dělení nahrazena operace rychlého násobení). Pro celočíselný argument je rychlejší vypočítat výraz ve tvaru (operace násobení je nahrazena operací sčítání) nebo pomocí operace posunu doleva (která neposkytuje zisk na všech procesorech). Takové optimalizace se nazývají redukce provozní síly . Násobení celočíselných argumentů konstantou na procesorech rodiny x86 lze efektivně provést pomocí instrukcí assembleru a namísto použití instrukcí : ${\frac {x}{a))$ $A$ $x\cdot b$ $b={\frac {1}{a}}$ $X$ $2x$ $x+x$ LEASHLADDMUL/IMUL

; Zdrojový operand v registru EAX ADD EAX , EAX ; násobení 2 LEA EAX , [ EAX + 2 * EAX ] ; násobení 3 SHL EAX , 2 ; násobení 4 LEA EAX , [ 4 * EAX ] ; jiný způsob, jak implementovat násobení 4 LEA EAX , [ EAX + 4 * EAX ] ; násobení 5 LEA EAX , [ EAX + 2 * EAX ] ; vynásobte 6 ADD EAX , EAX ; atd.

Takové optimalizace jsou mikroarchitektonické a obvykle je pro programátora provádí optimalizační kompilátor transparentně.

Relativně hodně času zabere volání podprogramů (předávání parametrů na zásobníku , ukládání registrů a návratových adres, volání konstruktorů kopírování). Pokud podprogram obsahuje malý počet akcí, lze jej implementovat inline ( anglicky inline ) – všechny jeho příkazy se zkopírují do každé nové stránky volání (existuje řada omezení pro substituce v řádku: například podprogram nesmí být rekurzivní ). To eliminuje režii volání podprogramu, ale zvětšuje velikost spustitelného souboru. Samotné zvýšení velikosti spustitelného souboru není významné, v některých případech však může spustitelný kód přesahovat instrukční mezipaměť , což povede k výraznému poklesu rychlosti provádění programu. Moderní optimalizační kompilátory proto obvykle mají nastavení optimalizace pro velikost kódu a rychlost provádění.

Výkon závisí také na typu operandů. Například v jazyce Turbo Pascal se v důsledku implementace celočíselné aritmetiky operace sčítání ukazuje jako nejpomalejší pro operandy typu Bytea ShortInt: přestože proměnné zabírají jeden bajt, aritmetické operace pro ně jsou dvoubajtové a při provádění operací na těchto typech se vynuluje horní bajt registrů a operand se zkopíruje z paměti do dolního bajtu registru. To vede k dodatečným časovým nákladům.

Při programování aritmetických výrazů je třeba volit takovou formu jejich zápisu, aby se minimalizoval počet „pomalých“ operací. Uvažujme o takovém příkladu. Nechť je třeba vypočítat polynom 4. stupně:

ax^{4}+bx^{3}+cx^{2}+dx+e

Za předpokladu, že se výpočet stupně provádí násobením základu určitým počtem krát, lze snadno zjistit, že tento výraz obsahuje 10 násobení ("pomalé" operace) a 4 sčítání ("rychlé" operace). Stejný výraz lze napsat jako:

(((ax+b)x+c)x+d)x+e

Tato forma zápisu se nazývá Hornerovo schéma . Tento výraz má 4 násobení a 4 sčítání. Celkový počet operací se snížil téměř na polovinu a odpovídajícím způsobem se zkrátí i čas na výpočet polynomu. Takové optimalizace jsou algoritmické a kompilátor je obvykle neprovádí automaticky.

Cykly

Liší se také doba provádění cyklů různých typů. Doba provádění smyčky s čítačem a smyčky s postpodmínkou, jsou všechny ostatní věci stejné, smyčka s předběžnou podmínkou se provádí o něco déle (asi o 20-30%).

Při používání vnořených smyček mějte na paměti, že čas CPU strávený zpracováním takové konstrukce může záviset na pořadí vnořených smyček. Například vnořená smyčka s čítačem v Turbo Pascalu :

for j := 1 až 100000 do for k := 1 až 1000 do a := 1 ;

for j := 1 až 1000 do for k := 1 až 100000 do a := 1 ;

Cyklus v levém sloupci trvá asi o 10 % déle než v pravém sloupci.

Na první pohled, jak v prvním, tak v druhém případě, je operátor přiřazení proveden 100 000 000krát a čas strávený na něm by měl být v obou případech stejný. Ale není. To je vysvětleno skutečností, že inicializace smyčky (zpracování její hlavičky procesorem za účelem určení počátečních a konečných hodnot čítače a také krok přírůstku čítače) vyžaduje čas. V prvním případě je vnější smyčka inicializována 1krát a vnitřní smyčka je inicializována 100 000krát, tj. celkem se provede 100 001 inicializací. V druhém případě existuje pouze 1001 takových inicializací.

Vnořené smyčky s předběžnou a postpodmínkou se chovají podobně. Můžeme dojít k závěru, že při programování vnořených smyček, pokud je to možné, udělejte smyčku s nejmenším počtem opakování nejvzdálenější a smyčku s největším počtem opakování nejvnitřnější.

Pokud smyčky obsahují přístupy do paměti (obvykle při zpracování polí), pro co nejefektivnější využití mezipaměti a hardwarové přednačítání dat z paměti ( anglicky Hardware Prefetch ), by pořadí obcházení adres paměti mělo být co nejsekvenčně. Klasickým příkladem takové optimalizace je přeuspořádání vnořených smyček při provádění násobení matic .

Invariantní fragmenty kódu

Optimalizace invariantních fragmentů kódu úzce souvisí s problémem optimálního programování smyčky. Uvnitř smyčky mohou být výrazy, jejichž fragmenty nijak nezávisí na řídicí proměnné smyčky. Říká se jim invariantní fragmenty kódu. Moderní kompilátory často detekují přítomnost takových fragmentů a automaticky je optimalizují. To není vždy možné a někdy výkon programu zcela závisí na tom, jak je smyčka naprogramována. Jako příklad zvažte následující fragment programu ( jazyk Turbo Pascal ):

for i := 1 až n do begin ... for k := 1 to p do for m := 1 to q do begin a [ k , m ] := Sqrt ( x * k * m - i ) + Abs ( u * i - x * m + k ) ; b [ k , m ] := Sin ( x * k * i ) + Abs ( u * i * m + k ) ; konec ; ... jsem := 0 ; bm := 0 ; for k := 1 to p do for m := 1 to q do begin am := am + a [ k , m ] / c [ k ] ; bm := bm + b [ k , m ] / c [ k ] ; konec ; konec ;

Zde jsou invariantní fragmenty kódu součet Sin(x * k * i)v první smyčce přes proměnnou ma operace dělení prvkem pole c[k]ve druhé smyčce přes m. Hodnoty sinusu a prvku pole se ve smyčce nad proměnnou nemění m, proto v prvním případě můžete vypočítat hodnotu sinus a přiřadit ji k pomocné proměnné, která bude použita ve výrazu uvnitř smyčky. Ve druhém případě můžete provést rozdělení po skončení smyčky přes m. Tím lze výrazně snížit počet časově náročných aritmetických operací.

Viz také

Literatura

Bentley, John Louis . Psaní efektivních programů. ISBN 0-13-970251-2
Donald Knuth . Umění počítačového programování = Umění počítačového programování. - 3. vyd. - M .: Williams , 2006. - V. 1: Základní algoritmy. — 720 s. - ISBN 0-201-89683-4 .
Donald Knuth . Umění počítačového programování = Umění počítačového programování. - 3. vyd. - M .: Williams , 2007. - V. 2: Získané algoritmy. — 832 s. — ISBN 0-201-89684-2 .
Donald Knuth . Umění počítačového programování = Umění počítačového programování. - 2. vyd. — M .: Williams , 2007. — V. 3: Třídění a vyhledávání. — 824 s. - ISBN 0-201-89685-0 .
S. A. NEMNYUGIN Workshop // Turbo Pascal. - 2. vyd. - Petrohrad. : Peter, 2007. - 268 s. - ISBN 5-94723-702-4 .
Chris Kaspersky . Technika optimalizace programu. Efektivní využití paměti. - Petrohrad. : BHV-Petersburg, 2003. - 464 s. — ISBN 5-94157-232-8 .

Odkazy

Referenční příručka optimalizace architektur Intel 64 a IA-32 Archivována 2. června 2010 na Wayback Machine
Průvodce optimalizací kódu procesoru AMD Athlon x86
http://www.agner.org/optimize/#manuals Archivováno 7. prosince 2020 na Wayback Machine