Programmering

Gjør Java raskt: Optimaliser!

I følge den banebrytende informatikeren Donald Knuth, "For tidlig optimalisering er roten til alt ondt." Enhver artikkel om optimalisering må starte med å påpeke at det vanligvis er flere grunner ikke å optimalisere enn å optimalisere.

  • Hvis koden din allerede fungerer, er optimalisering det en sikker måte å introdusere nye og muligens subtile feil på

  • Optimalisering har en tendens til å gjøre koden vanskeligere å forstå og vedlikeholde

  • Noen av teknikkene som presenteres her øker hastigheten ved å redusere utvidelsen av koden

  • Optimalisering av kode for en plattform kan faktisk gjøre det verre på en annen plattform

  • Mye tid kan brukes til å optimalisere, med liten gevinst i ytelse, og kan resultere i forvirret kode

  • Hvis du er altfor besatt av å optimalisere koden, vil folk kalle deg en nerd bak ryggen din

Før du optimaliserer, bør du nøye vurdere om du i det hele tatt trenger å optimalisere. Optimalisering i Java kan være et unnvikende mål siden utførelsesmiljøene varierer. Å bruke en bedre algoritme vil sannsynligvis gi en større ytelsesøkning enn noen mengde lavnivåoptimaliseringer og er mer sannsynlig å gi en forbedring under alle utførelsesforhold. Som regel bør høynivåoptimaliseringer vurderes før du gjør optimaliseringer på lavt nivå.

Så hvorfor optimalisere?

Hvis det er så dårlig, hvorfor optimalisere i det hele tatt? Vel, i en ideell verden ville du ikke. Men realiteten er at noen ganger er det største problemet med et program at det krever ganske enkelt for mange ressurser, og disse ressursene (minne, CPU-sykluser, nettverksbåndbredde eller en kombinasjon) kan være begrenset. Kodefragmenter som forekommer flere ganger i løpet av et program, vil sannsynligvis være størrelsesfølsomme, mens kode med mange utførelsesgjentakelser kan være hurtigfølsom.

Gjør Java raskt!

Som et tolket språk med en kompakt bytekode, er hastighet eller mangel på det som ofte dukker opp som et problem i Java. Vi vil først og fremst se på hvordan du kan få Java til å kjøre raskere i stedet for å få det til å passe inn i et mindre rom - selv om vi vil påpeke hvor og hvordan disse tilnærmingene påvirker minne eller nettverksbåndbredde. Fokuset vil være på kjernespråket i stedet for Java APIene.

Forresten, en ting vi vil ikke diskutere her er bruken av innfødte metoder skrevet i C eller montering. Mens bruk av innfødte metoder kan gi den ultimate ytelsesforbedringen, gjør det det på bekostning av Javas plattformuavhengighet. Det er mulig å skrive både en Java-versjon av en metode og native versjoner for utvalgte plattformer; dette fører til økt ytelse på noen plattformer uten å gi opp muligheten til å kjøre på alle plattformer. Men dette er alt jeg skal si om å erstatte Java med C-kode. (Se Java-tipset, "Skriv innfødte metoder" for mer informasjon om dette emnet.) Vårt fokus i denne artikkelen er på hvordan du kan gjøre Java raskt.

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

Som regel brukes 90 prosent av programmets unntakstid på å utføre 10 prosent av koden. (Noen bruker 80 prosent / 20 prosent-regelen, men min erfaring med å skrive og optimalisere kommersielle spill på flere språk de siste 15 årene har vist at formelen på 90 prosent / 10 prosent er typisk for ytelses-sultne programmer siden få oppgaver har en tendens til å utføres med stor frekvens.) Optimalisering av de andre 90 prosentene av programmet (hvor 10 prosent av utførelsestiden ble brukt) har ingen merkbar effekt på ytelsen. Hvis du klarte å få 90 prosent av koden til å kjøre dobbelt så raskt, ville programmet bare være 5 prosent raskere. Så den første oppgaven med å optimalisere koden er å identifisere 10 prosent (ofte er det mindre enn dette) av programmet som bruker mesteparten av utførelsestiden. Dette er ikke alltid du forventer at det skal være.

Generelle optimaliseringsteknikker

Det er flere vanlige optimaliseringsteknikker som gjelder uavhengig av hvilket språk som brukes. Noen av disse teknikkene, som global registerallokering, er sofistikerte strategier for å fordele maskinressurser (for eksempel CPU-registre) og gjelder ikke Java-bytekoder. Vi vil fokusere på teknikkene som i utgangspunktet involverer restruktureringskode og erstatter tilsvarende operasjoner innen en metode.

Styrkereduksjon

Styrkereduksjon oppstår når en operasjon erstattes av en tilsvarende operasjon som utføres raskere. Det vanligste eksemplet på styrkereduksjon er å bruke skiftoperatøren til å multiplisere og dele heltall med en styrke på 2. For eksempel, x >> 2 kan brukes i stedet for x / 4, og x << 1 erstatter x * 2.

Vanlig subuttrykk eliminering

Vanlig eliminering av subuttrykk fjerner overflødige beregninger. I stedet for å skrive

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

det vanlige underuttrykket beregnes en gang og brukes til begge beregningene:

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

Kode bevegelse

Kode bevegelse flytter kode som utfører en operasjon eller beregner et uttrykk hvis resultatet ikke endres, eller er invariant. Koden flyttes slik at den bare kjøres når resultatet kan endres, i stedet for å kjøre hver gang resultatet kreves. Dette er mest vanlig med sløyfer, men det kan også innebære at kode gjentas ved hver påkallelse av en metode. Følgende er et eksempel på invariant kodebevegelse i en løkke:

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

blir til

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

Rullende løkker

Rulling av sløyfer reduserer overhead for løkkekontrollkode ved å utføre mer enn en operasjon hver gang gjennom sløyfen, og følgelig utføre færre iterasjoner. Arbeider fra forrige eksempel, hvis vi vet at lengden på x [] er alltid et multiplum av to, kan vi skrive om løkken som:

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

I praksis gir ikke rulle sløyfer som denne - der verdien av sløyfeindeksen brukes i sløyfen og må inkrementeres separat - ikke en merkbar hastighetsøkning i tolket Java fordi bytekodene mangler instruksjoner for å effektivt kombinere+1"inn i matriseindeksen.

Alle optimaliseringstipsene i denne artikkelen innebærer en eller flere av de generelle teknikkene som er oppført ovenfor.

Sette kompilatoren på jobb

Moderne C- og Fortran-kompilatorer produserer svært optimalisert kode. C ++ - kompilatorer produserer vanligvis mindre effektiv kode, men er fremdeles godt på vei til å produsere optimal kode. Alle disse kompilatorene har gått gjennom mange generasjoner under påvirkning av sterk markedskonkurranse og har blitt finpussede verktøy for å klemme hver eneste dråpe ytelse ut av vanlig kode. De bruker nesten helt sikkert alle generelle optimaliseringsteknikker presentert ovenfor. Men det er fortsatt mange triks igjen for å få kompilatorer til å generere effektiv kode.

javac, JITs og native code compilers

Nivået på optimalisering som javac utfører når kompilering av kode på dette punktet er minimal. Det er som standard å gjøre følgende:

  • Konstant folding - kompilatoren løser konstante uttrykk slik at i = (10 * 10) kompilerer til jeg = 100.

  • Grenbretting (mesteparten av tiden) - unødvendig gå til bytekoder unngås.

  • Begrenset eliminering av død kode - ingen kode produseres for utsagn som hvis (usann) i = 1.

Nivået på optimalisering som javac gir, bør forbedres, sannsynligvis dramatisk, ettersom språket modnes og kompilatorleverandører begynner å konkurrere for alvor på grunnlag av kodegenerering. Java får akkurat nå andre generasjons kompilatorer.

Deretter er det just-in-time (JIT) kompilatorer som konverterer Java-bykoder til naturlig kode på kjøretid. Flere er allerede tilgjengelige, og mens de kan øke kjøringshastigheten til programmet ditt dramatisk, er optimaliseringsnivået de kan utføre begrenset fordi optimalisering skjer på kjøretid. En JIT-kompilator er mer opptatt av å generere koden raskt enn å generere den raskeste koden.

Innfødte kodekompilatorer som kompilerer Java direkte til opprinnelig kode, bør tilby størst ytelse, men på bekostning av plattformuavhengighet. Heldigvis vil mange av triksene som presenteres her oppnås av fremtidige kompilatorer, men foreløpig tar det litt arbeid å få mest mulig ut av kompilatoren.

javac tilbyr ett ytelsesalternativ du kan aktivere: påkalle -O alternativ for å få kompilatoren til å integrere visse metodeanrop:

javac -O MyClass

Innføring av en metodeanrop setter inn koden for metoden direkte i koden som gjør metoden. Dette eliminerer overhead for metodeanropet. For en liten metode kan denne overhead utgjøre en betydelig prosentandel av gjennomføringstiden. Merk at bare metoder deklarert som en av dem privat, statisk, eller endelig kan vurderes for inlining, fordi bare disse metodene løses statisk av kompilatoren. Også, synkronisert metoder vil ikke være inline. Kompilatoren vil bare integrere små metoder som vanligvis bare består av en eller to kodelinjer.

Dessverre har 1.0-versjonene av javac-kompilatoren en feil som genererer kode som ikke kan passere bytekodeverifisereren når -O alternativet brukes. Dette er løst i JDK 1.1. (Bytecode-verifisereren sjekker koden før den får lov til å kjøre for å sikre at den ikke bryter med noen Java-regler.) Den vil inkludere metoder som refererer til klassemedlemmer som er utilgjengelige for den anropende klassen. For eksempel, hvis følgende klasser er samlet sammen ved hjelp av -O alternativ

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

anropet til A.getX () i klasse B vil bli inline i klasse B som om B hadde blitt skrevet som:

klasse B {int y = A.x; } 

Dette vil imidlertid føre til at generering av bytekoder får tilgang til den private A.x-variabelen som vil bli generert i BS kode. Denne koden vil fungere bra, men siden den bryter Java-tilgangsbegrensningene, vil den bli markert av bekrefteren med en IllegalAccessError første gang koden kjøres.

Denne feilen gjør ikke -O alternativet ubrukelig, men du må være forsiktig med hvordan du bruker den. Hvis påkalt på en enkelt klasse, kan den integrere visse metodeanrop i klassen uten risiko. Flere klasser kan trekkes sammen så lenge det ikke er noen potensielle tilgangsbegrensninger. Og noen koder (for eksempel applikasjoner) blir ikke utsatt for bytecode-verifisereren. Du kan ignorere feilen hvis du vet at koden din bare vil kjøres uten å bli utsatt for bekrefteren. For mer informasjon, se FAQ om javac-O.

Profilere

Heldigvis kommer JDK med en innebygd profil for å identifisere hvor tiden blir brukt i et program. Det vil holde oversikt over tiden som er brukt i hver rutine og skrive informasjonen til filen java.prof. For å kjøre profilen, bruk -prof alternativ når du påkaller Java-tolken:

java -prof myClass

Eller for bruk med en applet:

java -prof sun.applet.AppletViewer myApplet.html

Det er noen advarsler for bruk av profilen. Profilutgangen er ikke spesielt lett å tyde. I JDK 1.0.2 avkortes det også metodenavnene til 30 tegn, så det er kanskje ikke mulig å skille noen metoder. Dessverre, med Mac er det ingen måte å påkalle profilen, så Mac-brukere er ute av hell. På toppen av alt dette inkluderer ikke Suns Java-dokumentside (se Ressurser) lenger dokumentasjonen for -prof alternativ). Imidlertid, hvis plattformen din støtter -prof enten Vladimir Bulatovs HyperProf eller Greg Whites ProfileViewer kan brukes til å tolke resultatene (se Ressurser).

Det er også mulig å "profilere" koden ved å sette inn eksplisitt timing i koden:

lang start = System.currentTimeMillis (); // gjør operasjonen for å bli tidsbestemt her lenge = System.currentTimeMillis () - start;

System.currentTimeMillis () returnerer tiden på 1/1000 sek. Noen systemer, for eksempel en Windows-PC, har imidlertid en systemtidsur med mindre (mye mindre) oppløsning enn 1/1000 sekund. Selv 1/1000 sekund er ikke lang nok til å presisere mange operasjoner. I disse tilfellene, eller på systemer med tidtakere med lav oppløsning, kan det være nødvendig å tidse hvor lang tid det tar å gjenta operasjonen n ganger og del deretter den totale tiden med n for å få den faktiske tiden. Selv når profilering er tilgjengelig, kan denne teknikken være nyttig for timing av en bestemt oppgave eller operasjon.

Her er noen avsluttende notater om profilering:

  • Tidsbestem koden alltid før og etter endringer for å bekrefte at endringene dine forbedret programmet, i det minste på testplattformen

  • Prøv å gjøre hver timing test under identiske forhold

  • Hvis mulig, konstruer en test som ikke er avhengig av noen brukerinngang, da variasjonene i brukerresponsen kan føre til at resultatene svinger

Referanseappleten

Benchmark-appleten måler tiden det tar å utføre en operasjon tusenvis (eller til og med millioner) ganger, trekker fra tiden som er brukt til å utføre andre operasjoner enn testen (for eksempel løkkeoverhead), og bruker deretter denne informasjonen til å beregne hvor lenge hver operasjon tok. Den kjører hver test i omtrent ett sekund. I et forsøk på å eliminere tilfeldige forsinkelser fra andre operasjoner datamaskinen kan utføre under en test, kjører den hver test tre ganger og bruker det beste resultatet. Den prøver også å eliminere søppeloppsamling som en faktor i testene. På grunn av dette, jo mer minne tilgjengelig for referansen, jo mer nøyaktige er resultatene.

$config[zx-auto] not found$config[zx-overlay] not found