Minska kostnaderna för verksamheten

Att minska kostnaderna för operationer i kompilatorteori är att ersätta långsamma operationer, såsom multiplikation och division, med snabbare, såsom addition, subtraktion, skift. Så division (multiplikation) med är ekvivalent med en bitförskjutning åt höger (vänster).

Det finns algoritmer för att omvandla operationer av multiplikation och division med ett godtyckligt heltal till en sekvens av enklare operationer (additioner, subtraktioner och skift). Sådan optimering utförs vanligtvis automatiskt av kompilatorn och kräver ingen programmeringsingripande.

Exempel

Heltalsmultiplikation med 2:

{ före optimering (3 cykler på Core 2 Duo) } y := 2 * x ; { efter optimering } y := x + x ; // 1 klocka på Core 2 Duo y := x shl 1 ; // 1 klocka på Core 2 Duo


Heltalsmultiplikation med 3:

{ före optimering (3 cykler på Core 2 Duo) } y := 3 * x ; { efter optimering } y := x + x + x ; // 2 klockor på Core 2 Duo y := x shl 1 + x ; // 2 klockor på Core 2 Duo y := x shl 2 - x ; // 2 klockor på Core 2 Duo


Heltalsmultiplikation med 4:

{ före optimering (3 cykler på Core 2 Duo) } y := 4 * x ; { efter optimering (1 cykel på Core 2 Duo) } y := x shl 2 ;


Heltalsmultiplikation med 5:

{ före optimering (3 cykler på Core 2 Duo) } y := 5 * x ; { efter optimering (2 cykler på Core 2 Duo) } y := x shl 2 + x ;


Heltalsmultiplikation med 6:

{ före optimering (3 cykler på Core 2 Duo) } y := 6 * x ; { efter optimering } y := ( x shl 2 - x ) shl 1 ; // 3 cykler, suboptimal implementering y := x shl 2 + x shl 1 ; // 2 cykler, förutsatt att växlingsoperationerna faller in i olika ställdon och kommer att utföras parallellt

Det kan ses att inte alla faktorer effektivt kan ersättas av enklare operationer. Dessutom bör beslutet om en sådan ersättning ta hänsyn till de mikroarkitektoniska egenskaperna hos processorn (åtminstone fördröjningen av utförandet av operationer) för vilken sådan optimering utförs (till exempel tar skiftoperationer på Pentium 4-processorn mycket längre tid än på andra processorer, vilket måste beaktas) [1] .

Fotnoter

  1. ↑ I många kompilatorer (till exempel Intel C ++ Compiler ) är det möjligt att med hjälp av kommandoradsalternativ indikera för kompilatorn på vilken processor programmet är planerat att köras

Litteratur

  • Alfred Aho, Monica Lam, Ravi Seti, Jeffrey Ullman. Compilers : Principles, Techniques and Tools = Compilers: Principles, Techniques and Tools. — 2:a upplagan. - M . : "Williams", 2008. - 1184 sid. - 1500 exemplar.  - ISBN 978-5-8459-1349-4 .
  • Allen, Francis E .; Cocke, John & Kennedy, Ken (1981), Reduction of Operator Strength, i Munchnik, Steven S. & Jones, Neil D., Program Flow Analysis: Theory and Applications , Prentice-Hall, ISBN 978-0-13-729681- ett 
  • Cocke, John & Kennedy, Ken (november 1977), En algoritm för minskning av operatörsstyrka, Communications of the ACM vol 20 (11) 
  • Cooper, Keith; Simpson, Taylor & Vick, Christopher (oktober 1995), Operator Strength Reduction , Rice University , < http://softlib.rice.edu/pub/CRPC-TRs/reports/CRPC-TR95635-S.pdf > . Hämtad 22 april 2010.