Optimering (datavetenskap)

Optimering  är modifiering av ett system för att förbättra dess effektivitet. Ett system kan vara ett enda datorprogram , en digital enhet, en samling datorer eller till och med ett helt nätverk.

Även om målet med optimering är att erhålla ett optimalt system, uppnås inte alltid ett riktigt optimalt system i optimeringsprocessen. Ett optimerat system är vanligtvis optimalt för endast en uppgift eller grupp av användare: någonstans kan det vara viktigare att minska tiden som krävs för programmet att slutföra arbetet, även till priset av att förbruka mer minne; i applikationer där minnet är viktigare kan långsammare algoritmer med mindre minneskrav väljas.

Dessutom finns det ofta ingen universell lösning (fungerar bra i alla fall), så ingenjörer använder kompromisslösningar för  att optimera endast nyckelparametrar. Dessutom överstiger den ansträngning som krävs för att uppnå ett helt optimalt program som inte kan ytterligare förbättras nästan alltid den nytta som kan erhållas av detta, så som regel är optimeringsprocessen avslutad innan full optimalitet uppnås. Lyckligtvis, i de flesta fall, även med detta, uppnås märkbara förbättringar.

Optimering måste göras med försiktighet. Tony Hoare sa först, och Donald Knuth upprepade ofta senare det berömda talesättet: "För tidig optimering är roten till allt ont." Det är mycket viktigt att ha en tonande algoritm och en fungerande prototyp till att börja med.

Grunderna

Vissa uppgifter kan ofta utföras mer effektivt. Till exempel, ett C- program som summerar alla heltal från 1 till N:

int i , summa = 0 ; för ( i = 1 ; i <= N ; i ++ ) summa += i ;

Förutsatt att det inte finns något spill här , kan den här koden skrivas om enligt följande med den lämpliga matematiska formeln :

int summa = ( N * ( N + 1 )) / 2 ;

Termen "optimering" innebär vanligtvis att systemet behåller samma funktionalitet. Men betydande prestandaförbättringar kan ofta uppnås genom att ta bort redundant funktionalitet. Om man till exempel antar att programmet inte behöver stödja mer än 100 element vid inmatning är det möjligt att använda statisk allokering istället för den långsammare dynamiska allokeringen .

Avvägningar

Optimering fokuserar huvudsakligen på enstaka eller upprepade körtider, minnesanvändning, diskutrymme, bandbredd eller någon annan resurs. Detta kräver vanligtvis avvägningar – en parameter optimeras på bekostnad av andra. Att till exempel öka storleken på programvarans cache för något förbättrar körningsprestandan, men ökar också minnesförbrukningen. Andra vanliga avvägningar inkluderar kodtransparens och uttrycksfullhet, nästan alltid på bekostnad av avoptimering. Komplexa specialiserade algoritmer kräver mer felsökning och ökar risken för fel .

Olika områden

Inom operationsforskning är optimering problemet med att bestämma ingångsvärdena för en funktion för vilken den har ett max- eller minimumvärde. Ibland finns det begränsningar för dessa värden, en sådan uppgift är känd som begränsad optimering .

I programmering innebär optimering vanligtvis att modifiera koden och dess kompileringsinställningar för en given arkitektur för att producera mer effektiv programvara.

Typiska problem har så många möjligheter att programmerare vanligtvis bara kan tillåta att en "tillräckligt bra" lösning används.

Flaskhalsar

För att optimera måste du hitta en flaskhals ( engelska  bottleneck - bottleneck): en kritisk del av koden, som är huvudkonsumenten av den nödvändiga resursen. Att förbättra cirka 20 % av koden innebär ibland att 80 % av resultaten ändras, enligt Pareto-principen . Läckage av resurser (minne, handtag, etc.) kan också leda till att programmets körningshastighet minskar. För att söka efter sådana läckor används speciella felsökningsverktyg och profiler används för att upptäcka flaskhalsar .

Den arkitektoniska utformningen av ett system har ett särskilt starkt inflytande på dess prestanda. Val av algoritm påverkar effektiviteten mer än något annat designelement. Mer komplexa algoritmer och datastrukturer kan hantera ett stort antal element bra, medan enkla algoritmer är bra för små datamängder – omkostnaderna för att initiera en mer komplex algoritm kan uppväga fördelen med att använda den.

Ju mer minne ett program använder, desto snabbare körs det vanligtvis. Till exempel läser ett filterprogram vanligtvis varje rad, filtrerar och matar ut den raden direkt. Därför använder den bara minne för att lagra en rad, men dess prestanda är vanligtvis mycket dålig. Prestandan kan förbättras avsevärt genom att läsa hela filen och sedan skriva det filtrerade resultatet, men denna metod använder mer minne. Resultatcaching är också effektivt, men kräver mer minne att använda.

De enklaste teknikerna för att optimera program när det gäller CPU-tid

Optimering i termer av processortid är särskilt viktig för beräkningsprogram där matematiska beräkningar har en stor andel. Här är några optimeringstekniker som en programmerare kan använda när han skriver programkällkod.

Dataobjektinitiering

I många program måste en del av dataobjekten initieras , det vill säga de måste tilldelas initiala värden. En sådan uppgift utförs antingen i början av programmet, eller till exempel i slutet av slingan. Korrekt objektinitiering sparar värdefull CPU-tid. Så, till exempel, när det gäller att initiera arrayer, är det troligtvis mindre effektivt att använda en loop än att deklarera den arrayen som en direkt tilldelning.

Programmera aritmetiska operationer

I det fall då en betydande del av programmets tid ägnas åt aritmetiska beräkningar, döljs avsevärda reserver för att öka programmets hastighet i korrekt programmering av aritmetiska (och logiska) uttryck. Det är viktigt att olika aritmetiska operationer skiljer sig markant i hastighet. På de flesta arkitekturer är de snabbaste operationerna addition och subtraktion. Multiplikationen är långsammare, följt av division. Till exempel, beräkningen av värdet på uttrycket , där  är en konstant, för flyttalsargument utförs snabbare i formen , där  en konstant beräknas vid programkompileringsstadiet (i själva verket ersätts den långsamma divisionsoperationen med den snabba multiplikationsoperationen). För ett heltalsargument är det snabbare att beräkna uttrycket i formen (multiplikationsoperationen ersätts med additionsoperationen) eller att använda vänsterskiftsoperationen (som inte ger en förstärkning på alla processorer). Sådana optimeringar kallas driftstyrkeminskning . Att multiplicera heltalsargument med en konstant på x86- familjens processorer kan göras effektivt med hjälp av assembler- instruktioner , och istället för att använda instruktioner : LEASHLADDMUL/IMUL

; Källoperand i registret EAX ADD EAX , EAX ; multiplikation med 2 LEA EAX , [ EAX + 2 * EAX ] ; multiplikation med 3 SHL EAX , 2 ; multiplikation med 4 LEA EAX , [ 4 * EAX ] ; ett annat sätt att implementera multiplikation med 4 LEA EAX , [ EAX + 4 * EAX ] ; multiplikation med 5 LEA EAX , [ EAX + 2 * EAX ] ; multiplicera med 6 ADD EAX , EAX ; etc.

Sådana optimeringar är mikroarkitektoniska och görs vanligtvis transparent för programmeraren av den optimerande kompilatorn .

Relativt mycket tid går åt till att anropa subrutiner (att skicka parametrar på stacken , spara register och returadresser, anropa kopieringskonstruktörer). Om subrutinen innehåller ett litet antal åtgärder kan den implementeras inline ( engelska  inline ) - alla dess uttalanden kopieras till varje ny samtalsplats (det finns ett antal begränsningar för inline-ersättningar: subrutinen får till exempel inte vara rekursiv ). Detta eliminerar omkostnaderna för att anropa subrutinen, men ökar storleken på den körbara filen. I sig är ökningen av storleken på den körbara filen inte signifikant, men i vissa fall kan den körbara koden gå utöver instruktionscachen , vilket kommer att leda till en betydande minskning av programexekveringshastigheten. Därför har moderna optimeringskompilatorer vanligtvis optimeringsinställningar för kodstorlek och exekveringshastighet.

Prestandan beror också på typen av operander. Till exempel, i Turbo Pascal-språket , på grund av implementeringen av heltalsaritmetik, visar sig additionsoperationen vara den långsammaste för operander av typen Byteoch ShortInt: trots det faktum att variabler upptar en byte, är aritmetiska operationer för dem två-byte och när man utför operationer på dessa typer, återställs registrens höga byte och operanden kopieras från minnet till registrets lågbyte. Detta leder till extra tidskostnader.

När man programmerar aritmetiska uttryck bör man välja en sådan form av deras notation så att antalet "långsamma" operationer minimeras. Låt oss överväga ett sådant exempel. Låt det vara nödvändigt att beräkna ett polynom av fjärde graden:

Förutsatt att beräkningen av graden utförs genom att multiplicera basen ett visst antal gånger, är det lätt att finna att detta uttryck innehåller 10 multiplikationer ("långsamma" operationer) och 4 additioner ("snabba" operationer). Samma uttryck kan skrivas som:

Denna form av notation kallas Horners schema . Detta uttryck har 4 multiplikationer och 4 additioner. Det totala antalet operationer har minskat med nästan hälften, och tiden för beräkning av polynomet kommer också att minska i enlighet med detta. Sådana optimeringar är algoritmiska och utförs vanligtvis inte automatiskt av kompilatorn.

Cyklar

Utförandetiden för cykler av olika typer skiljer sig också åt. Exekveringstiden för en loop med en räknare och en loop med ett postcondition, allt annat lika, exekveras loopen med en precondition lite längre (med ca 20-30%).

När du använder kapslade loopar, kom ihåg att CPU-tiden som spenderas på att bearbeta en sådan konstruktion kan bero på ordningen på de kapslade looparna. Till exempel, en kapslad loop med en räknare i Turbo Pascal :

för j := 1 till 100 000 gör för k := 1 till 1000 gör a := 1 ; för j := 1 till 1000 gör för k := 1 till 100 000 gör a := 1 ;

Cykeln i den vänstra kolumnen tar cirka 10 % längre tid än i den högra kolumnen.

Vid första anblicken, både i det första och i det andra fallet, utförs uppdragsoperatören 100 000 000 gånger och tiden som spenderas på det bör vara densamma i båda fallen. Men det är inte. Detta förklaras av det faktum att loopinitiering (bearbetning av processorn av dess rubrik för att bestämma de initiala och slutliga värdena för räknaren, såväl som räknarens inkrementsteg) tar tid. I det första fallet initieras den yttre slingan 1 gång och den inre slingan initieras 100 000 gånger, det vill säga totalt 100 001 initieringar utförs. I det andra fallet finns det bara 1001 sådana initieringar.

Kapslade slingor med precondition och postcondition beter sig på liknande sätt. Vi kan dra slutsatsen att vid programmering av kapslade slingor, om möjligt, gör slingan med det minsta antalet repetitioner till den yttersta och slingan med det största antalet repetitioner till den innersta.

Om slingorna innehåller minnesåtkomster (vanligtvis vid bearbetning av arrays), för den mest effektiva användningen av cachen och hårdvaruförhämtning av data från minnet ( engelska  Hardware Prefetch ), bör ordningen för att kringgå minnesadresser vara så sekventiell som möjligt. Ett klassiskt exempel på en sådan optimering är omordning av kapslade loopar när matrismultiplikation utförs .

Invarianta kodavsnitt

Optimeringen av invarianta kodfragment är nära relaterad till problemet med optimal loopprogrammering. Inuti slingan kan det finnas uttryck vars fragment inte på något sätt beror på slingans kontrollvariabel. De kallas invarianta kodsnuttar. Moderna kompilatorer upptäcker ofta förekomsten av sådana fragment och optimerar dem automatiskt. Detta är inte alltid möjligt, och ibland beror prestandan för ett program helt på hur slingan är programmerad. Som ett exempel, betrakta följande programfragment ( Turbo Pascal-språk ):

för i := 1 till n börjar ... för k := 1 till p gör för m : = 1 till q börjar 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 ) ; slut ; ... am := 0 ; bm := 0 ; för k := 1 till p gör för m := 1 till q börjar am : = am + a [ k , m ] / c [ k ] ; bm := bm + b [ k , m ] / c [ k ] ; slut ; slut ;

Här är de invarianta kodfragmenten summan Sin(x * k * i)i den första slingan över variabeln moch operationen för division med arrayelementet c[k]i den andra slingan över m. Värdena på sinus och matriselement ändras inte i slingan över variabeln m, därför kan du i det första fallet beräkna värdet på sinus och tilldela det till en hjälpvariabel som kommer att användas i uttrycket inuti slingan. I det andra fallet kan du utföra divisionen efter slutet av slingan över m. Således kan antalet tidskrävande aritmetiska operationer reduceras avsevärt.

Se även

Litteratur

  • Bentley, John Louis . Att skriva effektiva program. ISBN 0-13-970251-2
  • Donald Knuth . Konsten att programmera = Konsten att programmera. - 3:e uppl. - M .: Williams , 2006. - V. 1: Grundläggande algoritmer. — 720 s. - ISBN 0-201-89683-4 .
  • Donald Knuth . Konsten att programmera = Konsten att programmera. - 3:e uppl. - M. : Williams , 2007. - V. 2: Erhållna algoritmer. — 832 sid. — ISBN 0-201-89684-2 .
  • Donald Knuth . Konsten att programmera = Konsten att programmera. - 2:a uppl. — M .: Williams , 2007. — V. 3: Sortering och sökning. — 824 sid. - ISBN 0-201-89685-0 .
  • S. A. NEMNYUGIN Verkstad // Turbo Pascal. - 2:a uppl. - St Petersburg. : Peter, 2007. - 268 sid. - ISBN 5-94723-702-4 .
  • Chris Kaspersky . Programoptimeringsteknik. Effektiv användning av minnet. - St Petersburg. : BHV-Petersburg, 2003. - 464 sid. — ISBN 5-94157-232-8 .

Länkar