streamalism.org

1. Introduktion

Branch Prediction er et interessant koncept inden for datalogi og kan have en dybtgående indvirkning på ydeevnen af ​​vores applikationer. Endnu det er generelt ikke godt forstået, og de fleste udviklere lægger meget lidt vægt på det.

I denne artikel vil vi undersøge nøjagtigt, hvad det er, hvordan det påvirker vores software, og hvad vi kan gøre ved det.

2. Hvad er instruktionsrørledninger?

Når vi skriver et hvilket som helst computerprogram, skriver vi et sæt kommandoer, som vi forventer, at computeren udfører i rækkefølge.

Tidlige computere kørte disse ad gangen. Dette betyder, at hver kommando indlæses i hukommelsen, udføres i sin helhed, og først når den er afsluttet, bliver den næste indlæst.

Instruktionsrørledninger er en forbedring i forhold til dette. De giver processoren mulighed for at opdele arbejdet i stykker og derefter udføre forskellige dele parallelt. Dette vil derefter give processoren mulighed for at udføre en kommando, mens den indlæses den næste, klar til brug.

Længere rørledninger inde i processoren tillader ikke kun hver enkelt del at blive forenklet, men tillader også, at flere dele af den udføres parallelt. Dette kan forbedre systemets samlede ydeevne.

For eksempel kunne vi have et simpelt program:

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

Dette kan behandles af en rørledning, der består af segmenter Fetch, Decode, Execute, Store som:

Vi kan her se, hvordan den samlede udførelse af de fire kommandoer køres parallelt, hvilket gør hele sekvensen hurtigere.

3. Hvad er farerne?

Visse kommandoer, som processoren skal udføre, vil medføre problemer for rørledningen. Dette er alle kommandoer, hvor udførelsen af ​​en del af rørledningen er afhængig af tidligere dele, men hvor de tidligere dele muligvis endnu ikke er blevet udført.

Filialer er en bestemt form for fare. De får henrettelsen til at gå i en af ​​to retninger, og det er ikke muligt at vide, hvilken retning før grenen er løst. Det betyder at ethvert forsøg på at indlæse kommandoerne forbi filialen er ikke sikkert, fordi vi ikke har nogen måde at vide, hvor vi skal indlæse dem fra.

Lad os ændre vores enkle program for at introducere en gren:

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

Resultatet af dette er det samme som før, men vi har introduceret en hvis udsagn midt i det. Computeren ser dette og kan ikke indlæse kommandoer forbi dette, før det er løst. Som sådan vil strømmen se ud som:

Vi kan straks se, hvilken indvirkning dette har på udførelsen af ​​vores program, og hvor mange urtrin det tog for at udføre det samme resultat.

4. Hvad er brancheforudsigelse?

Branch Prediction er en forbedring af ovenstående, hvor vores computer vil forsøge at forudsige, hvilken vej en gren vil gå og derefter handle i overensstemmelse hermed.

I vores ovenstående eksempel kan processoren forudsige det hvis (a <10) sandsynligvis rigtigt, og så vil det fungere som om instruktionen a + = 2 var den næste til at udføre. Dette vil så få strømmen til at ligne noget som:

Vi kan straks se, at dette har forbedret præstationen af ​​vores program - det tager nu ni flåter og ikke 11, så det er 19% hurtigere.

Dette er dog ikke uden risiko. Hvis grenforudsigelsen får det forkert, begynder det at sætte instruktioner i kø, der ikke skal udføres, i kø. Hvis dette sker, skal computeren smide dem væk og starte forfra.

Lad os vende vores betingede, så det er nu falsk:

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

Dette kan udføre noget som:

Dette er nu langsommere end det tidligere flow, selvom vi gør mindre! Processoren forudsagede forkert, at filialen ville evaluere til rigtigt, startede i kø i a + = 2 instruktion, og måtte derefter kassere den og starte forfra, når grenen blev vurderet til falsk.

5. Reel indvirkning på koden

Nu hvor vi ved, hvad grenforudsigelse er, og hvad fordelene er, hvordan kan det påvirke os? Trods alt, Vi taler om at miste et par processorcyklusser på højhastighedscomputere, så det vil helt sikkert ikke mærkes.

Og nogle gange er det sandt. Men nogle gange kan det gøre en overraskende forskel i effektiviteten af ​​vores applikationer. Det afhænger meget af præcis, hvad vi laver. Specifikt afhænger det af, hvor meget vi laver på kort tid.

5.1. Optællinger med tællelister

Lad os prøve at tælle poster på en liste. Vi genererer en liste med tal og tæller derefter hvor mange af dem der er mindre end en bestemt afskæring. Det svarer meget til ovenstående eksempler, men vi gør det i en løkke i stedet for bare som en enkelt instruktion:

Listenumre = LongStream.range (0, top) .boxed () .collect (Collectors.toList ()); hvis (shuffle) {Collections.shuffle (tal); } lang cutoff = top / 2; lang optælling = 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);

Bemærk, at vi kun timer sløjfen, der tæller, for det er det, vi er interesseret i. Så hvor lang tid tager det?

Hvis vi genererer tilstrækkeligt små lister, kører koden så hurtigt, at den ikke kan tidsindstilles - en liste med størrelse 100.000 viser stadig en tid på 0 ms. Men når listen bliver stor nok til, at vi kan time den, kan vi se en betydelig forskel baseret på, om vi har blandet listen eller ej. For en liste med 10.000.000 numre:

• Sorteret - 44 ms
• Blandet - 221ms

Det er, den blandede liste tager 5 gange længere tid at tælle end den sorterede liste, selvom de faktiske tal, der tælles, er de samme.

Handlingen med at sortere listen er dog betydeligt dyrere end blot at udføre tællingen. Vi skal altid profilere vores kode og afgøre, om præstationsgevinster er gavnlige.

5.2. Orden af ​​filialer

Efter ovenstående det synes rimeligt, at rækkefølgen af ​​grene i en hvis ellers erklæring skal være vigtig. Det vil sige, vi kunne forvente, at følgende presterede bedre, end hvis vi genbestilte filialerne:

hvis (mostLikely) {// Gør noget} andet hvis (lessLikely) {// Gør noget} andet hvis (mindstLikely) {// Gør noget}

Imidlertid, moderne computere kan undgå dette problem ved hjælp af brancheforudsigelsescache. Faktisk kan vi også teste dette:

Listenumre = LongStream.range (0, top) .boxed () .collect (Collectors.toList ()); hvis (shuffle) {Collections.shuffle (tal); } lang cutoff = (lang) (top * cutoffPercentage); lang lav = 0; lang høj = 0; lang start = System.currentTimeMillis (); for (Langt tal: tal) {hvis (antal <cutoff) {++ lav; } andet {++ højt; }} lang ende = System.currentTimeMillis (); LOG.info ("Tælles {} / {} tal i {} ms", lav, høj, slutstart);

Denne kode udføres på omtrent samme tid - ~ 35 ms for sorterede numre, ~ 200 ms for blandede tal - når der tælles 10.000.000 numre, uanset værdien af cutoffProcent.

Dette er fordi grenprediktoren håndterer begge grene ens og gætte korrekt, hvilken vej vi vil gå efter dem.

5.3. Kombinerende betingelser

Hvad hvis vi har et valg mellem en eller to betingelser? Det kan være muligt at omskrive vores logik på en anden måde, der har samme adfærd, men skal vi gøre dette?

Som et eksempel, hvis vi sammenligner to tal med 0, er en alternativ tilgang at multiplicere dem sammen og sammenligne resultatet med 0. Dette erstatter derefter en tilstand med en multiplikation. Men er det umagen værd?

Lad os overveje et eksempel:

long [] first = LongStream.range (0, TOP) .map (n -> Math.random () Math.random () <FRACTION? 0: n) .toArray (); lang optælling = 0; lang start = System.currentTimeMillis (); for (int i = 0; i <TOP; i ++) {hvis (første [i]! = 0 && sekund [i]! = 0) {++ tæller; }} lang ende = System.currentTimeMillis (); LOG.info ("Counted {} / {} numbers using separate mode in {} ms", count, TOP, end-start);

Vores tilstand inde i sløjfen kan udskiftes som beskrevet ovenfor. Dette påvirker faktisk kørselstiden:

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

Så det tager to gange så lang tid at udføre den mulighed, der bruger to forskellige betingelser.

6. Konklusion

Vi har set, hvad brancheforudsigelse er, og hvordan det kan have indflydelse på vores programmer. Dette kan give os nogle ekstra værktøjer i vores bælte for at sikre, at vores programmer er så effektive som muligt.

Som altid er tilfældet, vi er nødt til at huske at profilere vores kode, før vi foretager større ændringer. Det kan nogle gange være tilfældet, at det at koste at foretage ændringer koster mere på andre måder at foretage ændringer.

Eksempler på sager fra denne artikel er tilgængelige på GitHub.