Programmering

Gør Java hurtigt: Optimer!

Ifølge den banebrydende computerforsker Donald Knuth er "For tidlig optimering roden til alt ondt." Enhver artikel om optimering skal starte med at påpege, at der normalt er flere grunde ikke at optimere end at optimere.

  • Hvis din kode allerede fungerer, er optimering det en sikker måde at introducere nye og muligvis subtile bugs på

  • Optimering har tendens til at gøre kode sværere at forstå og vedligeholde

  • Nogle af de teknikker, der præsenteres her, øger hastigheden ved at reducere kodenes udvidelighed

  • Optimering af kode til en platform kan faktisk gøre det værre på en anden platform

  • En masse tid kan bruges til at optimere med lille gevinst i ydeevne og kan resultere i tilsløret kode

  • Hvis du er alt for besat af at optimere kode, vil folk kalde dig en nørd bag ryggen

Før du optimerer, skal du nøje overveje, om du overhovedet har brug for at optimere. Optimering i Java kan være et undvigende mål, da udførelsesmiljøerne varierer. Brug af en bedre algoritme vil sandsynligvis give en større præstationsforøgelse end nogen mængde optimeringer på lavt niveau og er mere tilbøjelige til at levere en forbedring under alle eksekveringsbetingelser. Som regel skal optimeringer på højt niveau overvejes, inden der foretages optimeringer på lavt niveau.

Så hvorfor optimere?

Hvis det er sådan en dårlig idé, hvorfor optimere overhovedet? Nå, i en ideel verden ville du ikke. Men virkeligheden er, at det største problem med et program nogle gange er, at det simpelthen kræver for mange ressourcer, og disse ressourcer (hukommelse, CPU-cyklusser, netværksbåndbredde eller en kombination) kan være begrænsede. Kodefragmenter, der forekommer flere gange i et program, er sandsynligvis størrelsesfølsomme, mens kode med mange udførelsesgentagelser kan være hastighedsfølsomme.

Gør Java hurtigt!

Som et fortolket sprog med en kompakt bytekode er hastighed eller manglen på det, der ofte dukker op som et problem i Java. Vi vil primært se på, hvordan man får Java til at køre hurtigere snarere end at få det til at passe ind i et mindre rum - selvom vi vil påpege, hvor og hvordan disse tilgange påvirker hukommelse eller netværksbåndbredde. Fokus vil være på kernesproget snarere end på Java API'erne.

Forresten, én ting vi vil ikke diskutere her er brugen af ​​native metoder skrevet i C eller samling. Selvom brug af native metoder kan give det ultimative ydeevne boost, gør det det på bekostning af Java's platform uafhængighed. Det er muligt at skrive både en Java-version af en metode og native versioner til udvalgte platforme; dette fører til øget ydeevne på nogle platforme uden at opgive muligheden for at køre på alle platforme. Men dette er alt hvad jeg vil sige om at erstatte Java med C-kode. (Se Java Tip, "Skriv native metoder" for at få flere oplysninger om dette emne.) Vores fokus i denne artikel er på, hvordan man gør Java hurtig.

90/10, 80/20, hytte, hytte, vandretur!

Som regel bruges 90 procent af et programs undtagelsestid på at udføre 10 procent af koden. (Nogle mennesker bruger 80 procent / 20 procent reglen, men min erfaring med at skrive og optimere kommercielle spil på flere sprog i de sidste 15 år har vist, at 90 procent / 10 procent formlen er typisk for præstationshungrige programmer, da få opgaver har tendens til at udføres med stor frekvens.) Optimering af de øvrige 90 procent af programmet (hvor 10 procent af udførelsestiden blev brugt) har ingen mærkbar effekt på ydeevnen. Hvis du var i stand til at få 90 procent af koden til at udføres dobbelt så hurtigt, ville programmet kun være 5 procent hurtigere. Så den første opgave med at optimere kode er at identificere de 10 procent (ofte er det mindre end dette) af programmet, der bruger det meste af udførelsestiden. Dette er ikke altid, hvor du forventer, at det skal være.

Generelle optimeringsteknikker

Der er flere almindelige optimeringsteknikker, der gælder uanset hvilket sprog der bruges. Nogle af disse teknikker, såsom global registerallokering, er sofistikerede strategier til tildeling af maskinressourcer (for eksempel CPU-registre) og gælder ikke for Java-bytecodes. Vi vil fokusere på de teknikker, der grundlæggende involverer omstruktureringskode og erstatter tilsvarende operationer inden for en metode.

Styrke reduktion

Styrkereduktion opstår, når en operation erstattes af en tilsvarende operation, der udføres hurtigere. Det mest almindelige eksempel på styrkereduktion er at bruge skifteoperatoren til at multiplicere og dele heltal med en styrke på 2. F.eks. x >> 2 kan bruges i stedet for x / 4og x << 1 erstatter x * 2.

Almindelig eliminering af subudtryk

Almindelig eliminering af subudtryk fjerner overflødige beregninger. I stedet for at skrive

dobbelt x = d * (lim / max) * sx; dobbelt y = d * (lim / max) * sy;

det fælles subudtryk beregnes en gang og bruges til begge beregninger:

dobbelt dybde = d * (lim / max); dobbelt x = dybde * sx; dobbelt y = dybde * sy;

Kode bevægelse

Kodebevægelse flytter kode, der udfører en operation eller beregner et udtryk, hvis resultat ikke ændres eller er invariant. Koden flyttes, så den kun udføres, når resultatet kan ændre sig, snarere end at udføre hver gang resultatet kræves. Dette er mest almindeligt med sløjfer, men det kan også involvere kode gentaget ved hver påkaldelse af en metode. Følgende er et eksempel på invariant kodebevægelse i en løkke:

for (int i = 0; i <x.længde; i ++) x [i] * = Math.PI * Math.cos (y); 

bliver til

dobbelt picosy = Math.PI * Math.cos (y);for (int i = 0; i <x.længde; i ++) x [i] * = picosy; 

Rulning af løkker

Udrulning af sløjfer reducerer overhead af loopkontrolkode ved at udføre mere end en operation hver gang gennem loop'en og følgelig udføre færre iterationer. Arbejder ud fra det foregående eksempel, hvis vi ved, at længden af x[] er altid et multiplum af to, kan vi omskrive løkken som:

dobbelt picosy = Math.PI * Math.cos (y);for (int i = 0; i <x.længde; i + = 2) { x [i] * = picosy; x [i + 1] * = picosy; } 

I praksis giver oprulning af sløjfer som denne - hvor værdien af ​​sløjfeindekset bruges i sløjfen og skal inkrementeres separat - ikke en mærkbar hastighedsforøgelse i fortolket Java, fordi bytekoderne mangler instruktioner til effektivt at kombinere "+1"ind i matrixindekset.

Alle optimeringstipene i denne artikel indeholder en eller flere af de generelle teknikker, der er anført ovenfor.

Sætte compileren på arbejde

Moderne C- og Fortran-compilere producerer meget optimeret kode. C ++ - kompilatorer producerer generelt mindre effektiv kode, men er stadig godt på vej til at producere optimal kode. Alle disse kompilatorer har gennemgået mange generationer under indflydelse af stærk markedskonkurrence og er blevet finpudset værktøjer til at presse hvert sidste dråbe ydeevne ud af almindelig kode. De bruger næsten helt sikkert alle de generelle optimeringsteknikker, der er præsenteret ovenfor. Men der er stadig masser af tricks tilbage for at få kompilatorer til at generere effektiv kode.

javac, JIT'er og indbyggede kodekompilatorer

Niveauet for optimering, der javac udfører, når kompilering af kode på dette tidspunkt er minimal. Det er som standard at gøre følgende:

  • Konstant foldning - kompilatoren løser ethvert konstant udtryk sådan, at i = (10 * 10) kompilerer til jeg = 100.

  • Grenfoldning (det meste af tiden) - unødvendig gå til bytekoder undgås.

  • Begrænset eliminering af død kode - der produceres ingen kode til udsagn som hvis (falsk) i = 1.

Optimeringsniveauet, som javac giver, skal forbedres, sandsynligvis dramatisk, da sproget modnes, og compiler-leverandører begynder at konkurrere for alvor på basis af kodegenerering. Java får lige nu anden generations compilere.

Derefter er der just-in-time (JIT) -compilere, der konverterer Java-bytecodes til native-kode ved kørselstid. Flere er allerede tilgængelige, og selvom de kan øge eksekveringshastigheden for dit program dramatisk, er det optimeringsniveau, de kan udføre, begrænset, fordi optimering sker på kørselstid. En JIT-kompilator er mere optaget af at generere koden hurtigt end at generere den hurtigste kode.

Indbyggede kodekompilatorer, der kompilerer Java direkte til oprindelig kode, skal tilbyde den største ydeevne, men på bekostning af platformuafhængighed. Heldigvis opnås mange af de tricks, der præsenteres her, af fremtidige compilers, men indtil videre tager det lidt arbejde at få mest muligt ud af compileren.

javac tilbyder en ydeevneindstilling, du kan aktivere: påkald af -O mulighed for at få compileren til at integrere bestemte metodekald:

javac -O MyClass

Indlejring af et metodekald indsætter koden for metoden direkte i den kode, der foretager metodekaldet. Dette eliminerer omkostningerne ved metodeopkaldet. For en lille metode kan denne omkostning repræsentere en betydelig procentdel af dens udførelsestid. Bemærk, at kun metoder er erklæret som enten privat, statisk, eller endelig kan overvejes til inline, fordi kun disse metoder løses statisk af compileren. Også, synkroniseret metoder er ikke inline. Compileren integrerer kun små metoder, der typisk kun består af en eller to linier kode.

Desværre har 1.0-versionerne af javac-kompilatoren en fejl, der genererer kode, der ikke kan passere bytecode-verifikatoren, når -O indstillingen bruges. Dette er rettet i JDK 1.1. (Bytecode-verifikatoren kontrollerer koden, før den får lov til at køre for at sikre, at den ikke overtræder nogen Java-regler.) Den vil indeholde metoder, der henviser til klassemedlemmer, der er utilgængelige for den kaldende klasse. For eksempel, hvis de følgende klasser er sammensat sammen ved hjælp af -O mulighed

klasse A {privat statisk int x = 10; offentlig statisk ugyldig getX () {return x; }} klasse B {int y = A.getX (); } 

opkaldet til A.getX () i klasse B bliver indrammet i klasse B, som om B var blevet skrevet som:

klasse B {int y = A.x; } 

Dette vil dog få genereringen af ​​bytekoder til at få adgang til den private A.x-variabel, der genereres i BS kode. Denne kode udføres fint, men da den overtræder Java's adgangsbegrænsninger, bliver den markeret af verifikatoren med en IllegalAccessError første gang koden udføres.

Denne fejl gør ikke -O mulighed ubrugelig, men du skal være forsigtig med, hvordan du bruger den. Hvis der påberåbes en enkelt klasse, kan den integrere bestemte metodekald inden for klassen uden risiko. Flere klasser kan sammenføjes, så længe der ikke er nogen potentielle adgangsbegrænsninger. Og nogle koder (såsom applikationer) er ikke underlagt bytecode-verifikatoren. Du kan ignorere fejlen, hvis du ved, at din kode kun udføres uden at blive udsat for verifikatoren. For yderligere information, se min FAQ om javac-O.

Profilere

Heldigvis leveres JDK med en indbygget profil, der hjælper med at identificere, hvor tid der bruges i et program. Det vil holde styr på tiden brugt i hver rutine og skrive oplysningerne til filen java.prof. For at køre profilen skal du bruge -prof mulighed, når man påberåber sig Java-tolken:

java -prof myClass

Eller til brug med en applet:

java -prof sun.applet.AppletViewer myApplet.html

Der er et par advarsler til brug af profilen. Profiludgangen er ikke særlig let at dechifrere. I JDK 1.0.2 afkortes det også metodens navne til 30 tegn, så det er muligvis ikke muligt at skelne mellem nogle metoder. Desværre er der på Mac ikke nogen måde at påberåbe sig profilen, så Mac-brugere er ude af lykke. Oven på alt dette inkluderer Suns Java-dokumentside (se ressourcer) ikke længere dokumentationen til -prof mulighed). Men hvis din platform understøtter -prof valgmulighed, kan enten Vladimir Bulatovs HyperProf eller Greg Whites ProfileViewer bruges til at fortolke resultaterne (se Ressourcer).

Det er også muligt at "profilere" kode ved at indsætte eksplicit timing i koden:

lang start = System.currentTimeMillis (); // gør operation, der skal tidsindstilles her lang tid = System.currentTimeMillis () - start;

System.currentTimeMillis () returnerer tid i 1/1000 sek. Nogle systemer, såsom en Windows-pc, har dog en systemtimer med mindre (meget mindre) opløsning end en 1/1000 sekund. Selv 1/1000 sekund er ikke længe nok til nøjagtigt at kunne mange operationer. I disse tilfælde eller på systemer med timere med lav opløsning kan det være nødvendigt at tage tid, hvor lang tid det tager at gentage handlingen n gange, og divider derefter den samlede tid med n for at få den aktuelle tid. Selv når profilering er tilgængelig, kan denne teknik være nyttig til timing af en bestemt opgave eller operation.

Her er et par afsluttende noter om profilering:

  • Giv altid koden tid før og efter at have foretaget ændringer for at kontrollere, at dine ændringer i det mindste på testplatformen forbedrede programmet

  • Prøv at lave hver timing test under identiske forhold

  • Hvis det er muligt, udtænk en test, der ikke er afhængig af brugerinput, da variationerne i brugersvaret kan få resultaterne til at svinge

Benchmark-appleten

Benchmark-appleten måler den tid, det tager at udføre en operation tusindvis (eller endda millioner) gange, fratrækker den tid, der er brugt til at udføre andre operationer end testen (såsom loop overhead) og bruger derefter disse oplysninger til at beregne, hvor længe hver operation tog. Den kører hver test i cirka et sekund. I et forsøg på at fjerne tilfældige forsinkelser fra andre handlinger, som computeren muligvis udfører under en test, kører den hver test tre gange og bruger det bedste resultat. Det forsøger også at eliminere affaldsindsamling som en faktor i testene. På grund af dette, jo mere hukommelse der er tilgængelig for benchmarket, jo mere nøjagtige er benchmarkresultaterne.