Snížení nákladů na provoz

Snížení nákladů na operace v teorii překladače spočívá v nahrazení pomalých operací, jako je násobení a dělení, rychlejšími, jako je sčítání, odčítání, posun. Takže dělení (násobení) podle je ekvivalentní posunu po bitech doprava (doleva).

Existují algoritmy pro převod operací násobení a dělení libovolným celým číslem na posloupnost jednodušších operací (sčítání, odčítání a posuny). Takovou optimalizaci obvykle provádí automaticky kompilátor a nevyžaduje zásah programátora.

Příklady

Násobení celého čísla 2:

{ před optimalizací (3 cykly na Core 2 Duo) } y := 2 * x ; { po optimalizaci } y := x + x ; // 1 hodiny na Core 2 Duo y := x shl 1 ; // 1 hodina na Core 2 Duo


Násobení celého čísla 3:

{ před optimalizací (3 cykly na Core 2 Duo) } y := 3 * x ; { po optimalizaci } y := x + x + x ; // 2 hodiny na Core 2 Duo y := x shl 1 + x ; // 2 hodiny na Core 2 Duo y := x shl 2 - x ; // 2 hodiny na Core 2 Duo


Násobení celého čísla 4:

{ před optimalizací (3 cykly na Core 2 Duo) } y := 4 * x ; { po optimalizaci (1 cyklus na Core 2 Duo) } y := x shl 2 ;


Násobení celého čísla 5:

{ před optimalizací (3 cykly na Core 2 Duo) } y := 5 * x ; { po optimalizaci (2 cykly na Core 2 Duo) } y := x shl 2 + x ;


Násobení celého čísla 6:

{ před optimalizací (3 cykly na Core 2 Duo) } y := 6 * x ; { po optimalizaci } y := ( x shl 2 - x ) shl 1 ; // 3 cykly, suboptimální implementace y := x shl 2 + x shl 1 ; // 2 cykly, za předpokladu, že operace řazení budou spadat do různých pohonů a budou prováděny paralelně

Je vidět, že ne všechny faktory lze efektivně nahradit jednoduššími operacemi. Kromě toho by rozhodnutí o takové výměně mělo zohledňovat mikroarchitektonické vlastnosti procesoru (alespoň latenci provádění operací), pro které se taková optimalizace provádí (například operace posunu na procesoru Pentium 4 trvají mnohem déle než na jiných zpracovatelích, s čímž je nutno počítat) [1] .

Poznámky pod čarou

  1. ↑ V mnoha kompilátorech (například Intel C ++ Compiler ) je možné pomocí možností příkazového řádku sdělit kompilátoru procesor, na kterém je plánováno spuštění programu.

Literatura

  • Alfred Aho, Monica Lam, Ravi Seti, Jeffrey Ullman. Kompilátory : Principy, techniky a nástroje = Kompilátory: Principy, techniky a nástroje. — 2. vydání. - M .: "Williams", 2008. - 1184 s. - 1500 výtisků.  - ISBN 978-5-8459-1349-4 .
  • Allen, Francis E .; Cocke, John & Kennedy, Ken (1981), Snížení síly operátora, v Munchnik, Steven S. & Jones, Neil D., Analýza toku programu: Teorie a aplikace , Prentice-Hall, ISBN 978-0-13-729681- jeden 
  • Cocke, John & Kennedy, Ken (listopad 1977), Algoritmus pro snížení síly operátora, Communications of the ACM vol . 20 (11) 
  • Cooper, Keith; Simpson, Taylor & Vick, Christopher (říjen 1995), Operator Strength Reduction , Rice University , < http://softlib.rice.edu/pub/CRPC-TRs/reports/CRPC-TR95635-S.pdf > . Staženo 22. dubna 2010.