Vestigingsvoorspelling in Java

1. Inleiding

Branch Prediction is een interessant concept in de informatica en kan een grote invloed hebben op de prestaties van onze applicaties. Nog het wordt over het algemeen niet goed begrepen en de meeste ontwikkelaars besteden er weinig aandacht aan.

In dit artikel gaan we onderzoeken wat het precies is, hoe het onze software beïnvloedt en wat we eraan kunnen doen.

2. Wat zijn instructiepijpleidingen?

Wanneer we een computerprogramma schrijven, schrijven we een reeks opdrachten waarvan we verwachten dat de computer deze achtereenvolgens uitvoert.

Vroege computers zouden deze een voor een draaien. Dit betekent dat elke opdracht in het geheugen wordt geladen, in zijn geheel wordt uitgevoerd, en pas wanneer deze is voltooid, wordt de volgende geladen.

Instructiepijpleidingen zijn hier een verbetering ten opzichte van. Ze stellen de processor in staat om het werk in stukken te splitsen en vervolgens verschillende onderdelen parallel uit te voeren. Hierdoor kan de processor de ene opdracht uitvoeren terwijl de volgende wordt geladen, klaar voor gebruik.

Langere pijpleidingen in de processor maken het niet alleen mogelijk om elk onderdeel te vereenvoudigen, maar ook om meer onderdelen parallel uit te voeren. Dit kan de algehele prestaties van het systeem verbeteren.

We zouden bijvoorbeeld een eenvoudig programma kunnen hebben:

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

Dit kan worden verwerkt door een pijplijn die bestaat uit Fetch, Decode, Execute, Store-segmenten als:

We kunnen hier zien hoe de algehele uitvoering van de vier opdrachten parallel wordt uitgevoerd, waardoor de hele reeks sneller wordt.

3. Wat zijn de gevaren?

Bepaalde opdrachten die de processor moet uitvoeren, zullen problemen veroorzaken voor de pipelining. Dit zijn alle opdrachten waarbij de uitvoering van een deel van de pijplijn afhankelijk is van eerdere delen, maar waarbij die eerdere delen mogelijk nog niet zijn uitgevoerd.

Takken zijn een specifieke vorm van gevaar. Ze zorgen ervoor dat de uitvoering in een van de twee richtingen gaat en het is niet mogelijk om te weten in welke richting totdat de vertakking is opgelost. Dit betekent dat elke poging om de commando's voorbij de branch te laden, is niet veilig omdat we niet kunnen weten vanwaar we ze moeten laden.

Laten we ons eenvoudige programma veranderen om een ​​branch te introduceren:

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

Het resultaat hiervan is hetzelfde als voorheen, maar we hebben een als verklaring in het midden ervan. De computer zal dit zien en kan geen opdrachten meer laden totdat het is opgelost. Als zodanig ziet de stroom er ongeveer zo uit:

We kunnen meteen zien welke impact dit heeft op de uitvoering van ons programma, en hoeveel klokstappen er nodig waren om hetzelfde resultaat uit te voeren.

4. Wat is branchevoorspelling?

Branch Prediction is een verbetering van het bovenstaande, waarbij onze computer zal proberen te voorspellen welke kant een branch zal gaan en dan dienovereenkomstig zal handelen.

In ons bovenstaande voorbeeld kan de processor dat voorspellen if (a <10) is waarschijnlijk waar, en zo zal het werken alsof de instructie een + = 2 was de volgende die werd uitgevoerd. Dit zou er dan voor zorgen dat de stroom er ongeveer zo uitziet:

We kunnen meteen zien dat dit de prestaties van ons programma heeft verbeterd - het kost nu negen teken en niet 11, dus het is 19% sneller.

Dit is echter niet zonder risico. Als de vertakkingsvoorspelling het verkeerd doet, begint het instructies in de wachtrij te plaatsen die niet zouden moeten worden uitgevoerd. Als dit gebeurt, moet de computer ze weggooien en opnieuw beginnen.

Laten we onze voorwaardelijke voorwaarden omdraaien, zodat het nu is false:

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

Dit zou iets kunnen uitvoeren als:

Dit is nu langzamer dan de eerdere stroom, ook al doen we minder! De processor heeft ten onrechte voorspeld dat de branche zou evalueren waar, begon in de rij te staan een + = 2 instructie, en moest het vervolgens weggooien en opnieuw beginnen wanneer de branch geëvalueerd naar false.

5. Echte impact op code

Nu we weten wat branchevoorspelling is en wat de voordelen zijn, hoe kan dit op ons van invloed zijn? Ten slotte, we hebben het over het verliezen van een paar processorcycli op supersnelle computers, dus het zal zeker niet merkbaar zijn.

En soms is dat waar. Maar soms kan het een verrassend verschil maken voor de prestaties van onze applicaties. Het hangt sterk af van wat we precies doen. Concreet hangt het af van hoeveel we in korte tijd doen.

5.1. Lijstitems tellen

Laten we proberen om items in een lijst te tellen. We gaan een lijst met getallen genereren en tellen hoeveel daarvan minder zijn dan een bepaalde grenswaarde. Dat lijkt erg op de bovenstaande voorbeelden, maar we doen het in een lus in plaats van slechts als een enkele instructie:

Lijstnummers = LongStream.range (0, bovenaan) .boxed () .collect (Collectors.toList ()); if (shuffle) {Collections.shuffle (nummers); } lange cutoff = top / 2; lange telling = 0; lange start = System.currentTimeMillis (); for (Long number: numbers) {if (number <cutoff) {++ count; }} long end = System.currentTimeMillis (); LOG.info ("Getelde {} / {} {} getallen in {} ms", count, top, shuffle? "Shuffled": "gesorteerd", end - start);

Merk op dat we alleen de lus timen die het tellen doet, omdat dit is waar we in geïnteresseerd zijn. Dus, hoe lang duurt dit?

Als we voldoende kleine lijsten genereren, werkt de code zo snel dat deze niet kan worden getimed - een lijst met een grootte van 100.000 geeft nog steeds een tijd van 0 ms weer. Wanneer de lijst echter groot genoeg wordt om te timen, kunnen we een significant verschil zien op basis van het feit of we de lijst hebben geschud of niet. Voor een lijst met 10.000.000 nummers:

  • Gesorteerd - 44ms
  • Geschud - 221 ms

Dat is, het tellen van de geschudde lijst duurt 5x langer dan het tellen van de gesorteerde lijst, ook al zijn de werkelijke getelde nummers hetzelfde.

Het sorteren van de lijst is echter aanzienlijk duurder dan alleen het tellen. We moeten onze code altijd profileren en bepalen of prestatieverbeteringen gunstig zijn.

5.2. Orde van takken

Volgend op het bovenstaande, het lijkt redelijk dat de volgorde van takken in een als / anders verklaring zou belangrijk moeten zijn. Dat wil zeggen dat we kunnen verwachten dat het volgende beter presteert dan wanneer we de branches opnieuw zouden ordenen:

if (mostLikely) {// Doe iets} anders if (lessLikely) {// Doe iets} anders if (leastLikely) {// Doe iets}

Echter, moderne computers kunnen dit probleem voorkomen door de branchevoorspellingscache te gebruiken. We kunnen dit inderdaad ook testen:

Lijstnummers = LongStream.range (0, bovenaan) .boxed () .collect (Collectors.toList ()); if (shuffle) {Collections.shuffle (nummers); } lange cutoff = (long) (top * cutoffPercentage); lang laag = 0; lang hoog = 0; lange start = System.currentTimeMillis (); for (Long number: numbers) {if (number <cutoff) {++ low; } else {++ hoog; }} long end = System.currentTimeMillis (); LOG.info ("Getelde {} / {} getallen in {} ms", laag, hoog, eind - begin);

Deze code wordt in ongeveer dezelfde tijd uitgevoerd - ~ 35 ms voor gesorteerde nummers, ~ 200 ms voor willekeurige nummers - bij het tellen van 10.000.000 nummers, ongeacht de waarde van cutoffPercentage.

Dit is zo omdat de vertakkingsvoorspeller behandelt beide vertakkingen gelijk en correct raden welke kant we voor ze op gaan.

5.3. Combineren van voorwaarden

Wat als we de keuze hebben tussen een of twee voorwaarden? Het is misschien mogelijk om onze logica op een andere manier te herschrijven met hetzelfde gedrag, maar moeten we dit doen?

Als we bijvoorbeeld twee getallen vergelijken met 0, is een alternatieve benadering om ze met elkaar te vermenigvuldigen en het resultaat te vergelijken met 0. Dit is dan een voorwaarde vervangen door een vermenigvuldiging. Maar is dit de moeite waard?

Laten we een voorbeeld bekijken:

long [] first = LongStream.range (0, TOP) .map (n -> Math.random () Math.random () <FRACTION? 0: n) .toArray (); lange telling = 0; lange start = System.currentTimeMillis (); for (int i = 0; i <TOP; i ++) {if (first [i]! = 0 && second [i]! = 0) {++ count; }} long end = System.currentTimeMillis (); LOG.info ("Getelde {} / {} getallen in aparte modus in {} ms", count, TOP, end - start);

Onze toestand binnen de lus kan worden vervangen, zoals hierboven beschreven. Dit heeft in feite invloed op de runtime:

  • Afzonderlijke voorwaarden - 40ms
  • Meerdere en enkele voorwaarde - 22 ms

Dus de optie die twee verschillende voorwaarden gebruikt, duurt eigenlijk twee keer zo lang om uit te voeren.

6. Conclusie

We hebben gezien wat branchevoorspelling is en hoe dit een impact kan hebben op onze programma's. Dit kan ons wat extra tools geven om ervoor te zorgen dat onze programma's zo efficiënt mogelijk zijn.

Echter, zoals altijd het geval is, we moeten eraan denken onze code te profileren voordat we grote wijzigingen aanbrengen. Het kan soms zo zijn dat het aanbrengen van wijzigingen om de voorspelling van vestigingen te helpen op andere manieren meer kost.

Voorbeelden van de cases uit dit artikel zijn beschikbaar op GitHub.