Grenprediksjon i Java

1. Introduksjon

Branch Prediction er et interessant konsept innen informatikk og kan ha en dyp innvirkning på ytelsen til applikasjonene våre. Ennå det er generelt ikke godt forstått, og de fleste utviklere legger veldig liten vekt på det.

I denne artikkelen skal vi utforske nøyaktig hva det er, hvordan det påvirker programvaren vår, og hva vi kan gjøre med det.

2. Hva er instruksjonsrørledninger?

Når vi skriver et hvilket som helst dataprogram, skriver vi et sett med kommandoer som vi forventer at datamaskinen skal utføre i rekkefølge.

Tidlige datamaskiner ville kjøre disse om gangen. Dette betyr at hver kommando blir lastet inn i minnet, utført i sin helhet, og bare når den er fullført, blir den neste lastet.

Instruksjonsrørledninger er en forbedring i forhold til dette. De lar prosessoren dele arbeidet i biter og deretter utføre forskjellige deler parallelt. Dette vil da tillate prosessoren å utføre en kommando mens den lastes inn den neste, klar til bruk.

Lengre rørledninger inne i prosessoren lar ikke bare hver del forenkles, men tillater også at flere deler utføres parallelt. Dette kan forbedre den generelle ytelsen til systemet.

For eksempel kan vi ha et enkelt program:

int a = 0; a + = 1; a + = 2; a + = 3;

Dette kan behandles av en rørledning som består av henting, dekode, utføre, lagre segmenter som:

Vi kan se her hvordan den generelle kjøringen av de fire kommandoene kjøres parallelt, og dermed gjør hele sekvensen raskere.

3. Hva er farene?

Visse kommandoer som prosessoren må utføre, vil føre til problemer for rørledningen. Dette er alle kommandoer der kjøringen av en del av rørledningen er avhengig av tidligere deler, men der de tidligere delene kanskje ennå ikke har blitt utført.

Grener er en bestemt form for fare. De får henrettelsen til å gå i en av to retninger, og det er ikke mulig å vite hvilken retning før grenen er løst. Dette betyr at ethvert forsøk på å laste kommandoene forbi grenen er ikke trygt fordi vi ikke har noen måte å vite hvor vi skal laste dem fra.

La oss endre vårt enkle program for å introdusere en gren:

int a = 0; a + = 1; hvis (a <10) {a + = 2; } a + = 3;

Resultatet av dette er det samme som før, men vi har introdusert en hvis uttalelse midt i den. Datamaskinen vil se dette og vil ikke kunne laste kommandoer etter dette før den er løst. Som sådan vil flyten se ut som:

Vi kan umiddelbart se hvilken innvirkning dette har på gjennomføringen av programmet vårt, og hvor mange klokketrinn det tok for å utføre det samme resultatet.

4. Hva er grenforutsigelse?

Grenprediksjon er en forbedring av det ovennevnte, der datamaskinen vår vil prøve å forutsi hvilken vei en filial skal gå, og deretter handle deretter.

I eksemplet vårt ovenfor kan prosessoren forutsi det hvis (a <10) sannsynligvis vil være ekte, og slik vil det fungere som om instruksjonen a + = 2 var den neste som ble utført. Dette vil føre til at flyten ser ut som:

Vi kan se med en gang at dette har forbedret ytelsen til programmet vårt - Det tar nå ni flått og ikke 11, så det er 19% raskere.

Dette er imidlertid ikke uten risiko. Hvis forutsigelsen på grenen blir feil, vil den begynne å sette i kø instruksjoner som ikke skal utføres. Hvis dette skjer, må datamaskinen kaste dem og starte på nytt.

La oss snu våre betingede, slik at det er nå falsk:

int a = 0; a + = 1; hvis (a> 10) {a + = 2; } a + = 3;

Dette kan utføre noe som:

Dette er nå tregere enn den tidligere strømmen, selv om vi gjør mindre! Prosessoren spådde feilaktig at filialen skulle evaluere til ekte, begynte å stå i kø a + = 2 instruksjon, og måtte deretter forkaste den og begynne på nytt når grenen ble evaluert til falsk.

5. Virkelig innvirkning på koden

Nå som vi vet hva grenforutsigelse er og hva fordelene er, hvordan kan det påvirke oss? Tross alt, vi snakker om å miste noen prosessersykluser på høyhastighets datamaskiner, så det vil helt sikkert ikke merkes.

Og noen ganger er det sant. Men noen ganger kan det gjøre en overraskende forskjell i ytelsen til applikasjonene våre. Det avhenger mye av nøyaktig hva vi gjør. Spesielt avhenger det av hvor mye vi gjør på kort tid.

5.1. Tellelisteoppføringer

La oss prøve å telle oppføringer i en liste. Vi skal generere en liste med tall, og deretter telle hvor mange av dem som er mindre enn en viss avskjæring. Det ligner veldig på eksemplene ovenfor, men vi gjør det i en løkke i stedet for bare som en enkelt instruksjon:

Listetall = LongStream.range (0, top) .boxed () .collect (Collectors.toList ()); if (shuffle) {Collections.shuffle (numbers); } lang avskjæring = topp / 2; lang telling = 0; lang start = System.currentTimeMillis (); for (Long number: numbers) {if (number <cutoff) {++ count; }} lang ende = System.currentTimeMillis (); LOG.info ("Counted {} / {} {} numbers in {} ms", count, top, shuffle? "Shuffled": "sorted", end - start);

Merk at vi bare tar tid på løkken som teller, fordi dette er det vi er interessert i. Så, hvor lang tid tar dette?

Hvis vi genererer tilstrekkelig små lister, kjører koden så fort at den ikke kan bli tidsbestemt - en liste på størrelse 100 000 viser fremdeles en tid på 0 ms. Men når listen blir stor nok til at vi kan tidsbestemme den, kan vi se en betydelig forskjell basert på om vi har blandet listen eller ikke. For en liste med 10 000 000 tall:

  • Sortert - 44ms
  • Blandet - 221ms

Det er, Den blandede listen tar 5 ganger lengre tid å telle enn den sorterte listen, selv om de faktiske tallene som telles, er de samme.

Handlingen med å sortere listen er imidlertid betydelig dyrere enn bare å utføre tellingen. Vi bør alltid profilere koden vår og avgjøre om noen ytelsesgevinster er fordelaktige.

5.2. Orden av filialer

Etter ovenstående, det virker rimelig at rekkefølgen på grener i en hvis / annet uttalelse skal være viktig. Det vil si at vi kan forvente at følgende vil prestere bedre enn om vi bestilte filialene på nytt:

hvis (mostLikely) {// Gjør noe} annet hvis (lessLikely) {// Gjør noe} annet hvis (minst Likely) {// Gjør noe}

Derimot, moderne datamaskiner kan unngå dette problemet ved å bruke filforutsigelsesbufferen. Vi kan faktisk teste dette også:

Listetall = LongStream.range (0, top) .boxed () .collect (Collectors.toList ()); if (shuffle) {Collections.shuffle (numbers); } lang avskjæring = (lang) (topp * avskjæringProsent); lang lav = 0; lang høy = 0; lang start = System.currentTimeMillis (); for (Long number: numbers) {if (number <cutoff) {++ low; } annet {++ høyt; }} lang ende = System.currentTimeMillis (); LOG.info ("Tellte {} / {} tall i {} ms", lav, høy, slutt - start);

Denne koden kjøres omtrent samtidig - ~ 35ms for sorterte tall, ~ 200ms for blandede tall - når du teller 10.000.000 tall, uavhengig av verdien av cutoffProsent.

Dette er fordi grenprediktoren håndterer begge grenene likt og gjetter riktig hvilken vei vi skal gå for dem.

5.3. Kombinere forhold

Hva om vi har et valg mellom en eller to forhold? Det kan være mulig å omskrive logikken vår på en annen måte som har samme oppførsel, men skal vi gjøre dette?

Som et eksempel, hvis vi sammenligner to tall med 0, er en alternativ tilnærming å multiplisere dem sammen og sammenligne resultatet til 0. Dette er å erstatte en tilstand med en multiplikasjon. Men er dette verdt det?

La oss vurdere et eksempel:

long [] first = LongStream.range (0, TOP) .map (n -> Math.random () Math.random () <FRACTION? 0: n) .toArray (); lang telling = 0; lang start = System.currentTimeMillis (); for (int i = 0; i <TOP; i ++) {if (first [i]! = 0 && second [i]! = 0) {++ count; }} lang ende = System.currentTimeMillis (); LOG.info ("Counted {} / {} numbers using separate mode in {} ms", count, TOP, end-start);

Vår tilstand inne i løkken kan erstattes, som beskrevet ovenfor. Å gjøre det påvirker faktisk kjøretiden:

  • Separate forhold - 40ms
  • Flere og enkelt forhold - 22ms

Så det alternativet som bruker to forskjellige forhold tar faktisk dobbelt så lang tid å utføre.

6. Konklusjon

Vi har sett hva grenforutsigelse er og hvordan det kan ha innvirkning på programmene våre. Dette kan gi oss noen ekstra verktøy i beltet vårt for å sikre at programmene våre er så effektive som mulig.

Som alltid er tilfelle, vi må huske å profilere koden vår før vi gjør store endringer. Noen ganger kan det være tilfelle at å gjøre endringer for å hjelpe forutsigelse av grenen koster mer på andre måter.

Eksempler på tilfeller fra denne artikkelen er tilgjengelig på GitHub.


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