A műveletek költségeinek csökkentése

A műveletek költségének csökkentése a fordítóelméletben a lassú műveletek, például a szorzás és az osztás felváltása gyorsabbakkal, mint az összeadás, kivonás, eltolás. Tehát az osztás (szorzás) -val egyenértékű a bitekkel jobbra (balra) való eltolással .

Léteznek algoritmusok a tetszőleges egész számmal történő szorzási és osztási műveletek egyszerűbb műveletek sorozatává (összeadások, kivonások és eltolások) való konvertálására. Az ilyen optimalizálást általában a fordító automatikusan végzi el, és nem igényel programozói beavatkozást.

Példák

Egész szám szorzása 2-vel:

{ optimalizálás előtt (3 ciklus Core 2 Duo-n) } y := 2 * x ; { optimalizálás után } y := x + x ; // 1 óra Core 2 Duo y -n := x shl 1 ; // 1 óra a Core 2 Duo-n


Egész szám szorzása 3-mal:

{ optimalizálás előtt (3 ciklus Core 2 Duo-n) } y := 3 * x ; { optimalizálás után } y := x + x + x ; // 2 óra a Core 2 Duo-n y := x shl 1 + x ; // 2 óra a Core 2 Duo-n y := x shl 2 - x ; // 2 óra a Core 2 Duo-n


Egész szám szorzása 4-gyel:

{ optimalizálás előtt (3 ciklus Core 2 Duo-n) } y := 4 * x ; { optimalizálás után (1 ciklus Core 2 Duo-n) } y := x shl 2 ;


Egész szám szorzása 5-tel:

{ optimalizálás előtt (3 ciklus Core 2 Duo-n) } y := 5 * x ; { optimalizálás után (2 ciklus Core 2 Duo-n) } y := x shl 2 + x ;


Egész szám 6-tal:

{ optimalizálás előtt (3 ciklus Core 2 Duo-n) } y := 6 * x ; { optimalizálás után } y := ( x shl 2 - x ) shl 1 ; // 3 ciklus, szuboptimális megvalósítás y := x shl 2 + x shl 1 ; // 2 ciklus, feltéve, hogy az eltolási műveletek különböző aktuátorokba esnek, és párhuzamosan kerülnek végrehajtásra

Látható, hogy nem minden tényezőt lehet hatékonyan helyettesíteni egyszerűbb műveletekkel. Ezenkívül az ilyen cserére vonatkozó döntésnek figyelembe kell vennie a processzor mikroarchitektúra jellemzőit (legalább a műveletek végrehajtásának késleltetését), amelyhez az ilyen optimalizálást végrehajtják (például a Pentium 4 processzor eltolási műveletei sokkal tovább tartanak mint más processzorokon, amit figyelembe kell venni) [1] .

Lábjegyzetek

  1. ↑ Számos fordítóban (például Intel C ++ Compiler ) lehetőség van a parancssori opciók használatával megadni azt a processzort, amelyen a programot futtatni tervezik.

Irodalom

  • Alfred Aho, Monica Lam, Ravi Seti, Jeffrey Ullman. Fordítók: alapelvek, technikák és eszközök = Compilers : Principles, Techniques, and Tools. — 2. kiadás. - M . : "Williams", 2008. - 1184 p. - 1500 példány.  - ISBN 978-5-8459-1349-4 .
  • Allen, Francis E .; Cocke, John & Kennedy, Ken (1981), Kezelői erő csökkentése, Munchnik, Steven S. & Jones, Neil D., Program Flow Analysis: Theory and Applications , Prentice-Hall, ISBN 978-0-13-729681- egy 
  • Cocke, John & Kennedy, Ken (1977. november), Egy algoritmus a kezelői erő csökkentésére, Communications of the ACM , 20. kötet (11) 
  • Cooper, Keith; Simpson, Taylor és Vick, Christopher (1995. október), Operator Strength Reduction , Rice University , < http://softlib.rice.edu/pub/CRPC-TRs/reports/CRPC-TR95635-S.pdf > . Letöltve: 2010. április 22.