streamalism.org

1. Úvod

Predpoveď vetvy je zaujímavý koncept v oblasti informatiky a môže mať výrazný vplyv na výkonnosť našich aplikácií. Ešte všeobecne to nie je dobre pochopené a väčšina vývojárov tomu venuje veľmi malú pozornosť.

V tomto článku sa chystáme preskúmať, čo to presne je, aký má vplyv na náš softvér a čo s tým môžeme urobiť.

2. Čo sú inštruktážne potrubia?

Keď píšeme akýkoľvek počítačový program, píšeme množinu príkazov, ktoré očakávame, že počítač vykoná postupne.

Prvé počítače ich mohli prevádzkovať naraz. To znamená, že každý príkaz sa načíta do pamäte, vykoná sa v celom rozsahu a až po dokončení sa načíta ďalší.

Inštruktážne potrubia sú v tomto smere vylepšením. Umožňujú procesoru rozdeliť prácu na kúsky a potom paralelne vykonávať rôzne časti. To by potom umožnilo procesoru vykonať jeden príkaz pri načítaní ďalšieho, pripravený na použitie.

Dlhšie potrubia vo vnútri procesora nielen umožňujú zjednodušenie každej časti, ale umožňujú aj paralelné vykonávanie viacerých jej častí. To môže zlepšiť celkový výkon systému.

Mohli by sme napríklad mať jednoduchý program:

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

To môže byť spracované kanálom obsahujúcim segmenty Fetch, Decode, Execute, Store ako:

Tu môžeme vidieť, ako prebieha celkové vykonávanie štyroch príkazov paralelne, čím sa zrýchľuje celá sekvencia.

3. Aké sú riziká?

Niektoré príkazy, ktoré procesor potrebuje na vykonanie, spôsobia problémy pri pipeline. Jedná sa o všetky príkazy, pri ktorých je vykonávanie jednej časti potrubia závislé od predchádzajúcich častí, ale pri ktorých sa tieto staršie časti ešte nemuseli vykonať.

Pobočky sú špecifickou formou nebezpečenstva. Spôsobia, že poprava pôjde jedným z dvoch smerov, a kým sa pobočka nevyrieši, nie je možné zistiť, ktorým smerom. To znamená, že akýkoľvek pokus o načítanie príkazov za vetvu nie je bezpečný, pretože nemáme spôsob, ako zistiť, odkiaľ ich načítať.

Zmeňme náš jednoduchý program a predstavme pobočku:

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

Výsledok je rovnaký ako predtým, zaviedli sme však ak uprostred neho vyhlásenie. Počítač to uvidí a nebude môcť načítať príkazy okolo tohto príkazu, kým nebude vyriešené. Tok bude vyzerať asi takto:

Okamžite vidíme dopad, ktorý to má na vykonávanie nášho programu, a koľko hodinových krokov bolo potrebných na vykonanie rovnakého výsledku.

4. Čo je Predikcia vetvy?

Predikcia vetvy je vylepšením vyššie uvedeného, ​​keď sa náš počítač pokúsi predpovedať, ktorým smerom sa bude pobočka uberať, a potom bude podľa toho konať.

V našom príklade vyššie to môže procesor predvídať ak (a <10) pravdepodobne bude pravda, a tak bude konať, akoby pokyn a + = 2 bol ďalší, kto popravil. To by potom spôsobilo, že tok bude vyzerať asi takto:

Hneď vidíme, že to zlepšilo výkonnosť nášho programu - teraz to trvá deväť kliešťov a nie 11, takže je to o 19% rýchlejšie.

Nie je to však bez rizika. Ak sa predpoveď vetvy pokazí, začne radiť pokyny, ktoré by sa nemali vykonávať. Ak sa to stane, počítač ich bude musieť vyhodiť a začať odznova.

Otočme svoje podmienené podmienky tak, aby to bolo teraz nepravdivé:

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

To by mohlo spustiť niečo ako:

Teraz je to pomalšie ako v predchádzajúcom postupe, aj keď robíme menej! Procesor nesprávne predpovedal, že pobočka vyhodnotí pravda, začal radiť do frontu a + = 2 pokyn, a potom ho musel zahodiť a začať odznova, keď sa pobočka vyhodnotila ako nepravdivé.

5. Skutočný dopad na kódex

Teraz, keď vieme, čo je predikcia odvetvia a aké sú výhody, ako nás môže ovplyvniť? Po všetkom, hovoríme o strate niekoľkých cyklov procesora na vysokorýchlostných počítačoch, takže to určite nebude badať.

A niekedy je to pravda. Ale niekedy to môže prekvapivo zmeniť výkon našich aplikácií. Veľa záleží na tom, čo presne robíme. Konkrétne to závisí od toho, koľko toho stihneme za krátky čas.

5.1. Počítanie položiek zoznamu

Skúsme spočítať položky do zoznamu. Vygenerujeme zoznam čísel a potom spočítame, koľko z nich je menej ako určitý medzný limit. Je to veľmi podobné ako v predchádzajúcich príkladoch, ale robíme to v slučke, nie iba ako jednu inštrukciu:

Zoznam čísel = LongStream.range (0, hore) .boxed () .collect (Collectors.toList ()); if (zamiešať) {Collections.shuffle (numbers); } dlhý cutoff = horný / 2; dlhý počet = 0; dlhý štart = System.currentTimeMillis (); for (Long number: numbers) {if (number <cutoff) {++ count; }} dlhý koniec = System.currentTimeMillis (); LOG.info ("Počítané {} / {} {} čísla v {} ms", počet, najvyššie, náhodne? "Zamiešané": "zoradené", koniec - začiatok);

Upozorňujeme, že načasujeme iba slučku, ktorá počíta, pretože to je to, čo nás zaujíma. Ako dlho to teda trvá?

Ak generujeme dostatočne malé zoznamy, potom kód beží tak rýchlo, že ho nie je možné načasovať - ​​zoznam s veľkosťou 100 000 stále zobrazuje čas 0 ms. Keď však bude zoznam dostatočne veľký na to, aby sme ho dokázali načasovať, môžeme vidieť výrazný rozdiel na základe toho, či sme zoznam zamiešali alebo nie. Zoznam 10 000 000 čísel:

• Zoradené - 44 ms
• Zamiešané - 221 ms

To znamená, počet zamiešaných zoznamov sa počíta päťkrát dlhšie ako zoradený zoznam, aj keď sú spočítané skutočné čísla rovnaké.

Samotné triedenie zoznamu je však podstatne nákladnejšie ako len samotné spočítanie. Náš kód by sme mali vždy profilovať a určiť, či je nejaké zvýšenie výkonnosti prospešné.

5.2. Poradie pobočiek

Na základe vyššie uvedeného zdá sa byť rozumné, aby poradie pobočiek v ako / inak vyhlásenie by malo byť dôležité. To znamená, že by sme mohli očakávať, že nasledujúce výkony budú lepšie, ako keby sme si znova objednali pobočky:

if (mostLikely) {// Urob niečo} else if (lessLikely) {// Urob niečo} else if (najmenejLikely) {// Urob niečo}

Avšak moderné počítače sa môžu vyhnúť tomuto problému pomocou medzipamäte predikcie vetiev. Môžeme to vyskúšať tiež:

Zoznam čísel = LongStream.range (0, hore) .boxed () .collect (Collectors.toList ()); if (zamiešať) {Collections.shuffle (numbers); } long cutoff = (long) (top * cutoffPercentage); long low = 0; long high = 0; dlhý štart = System.currentTimeMillis (); for (Long number: numbers) {if (number <cutoff) {++ low; } else {++ vysoky; }} dlhý koniec = System.currentTimeMillis (); LOG.info ("Počítané {} / {} čísla za {} ms", nízke, vysoké, koniec - začiatok);

Tento kód sa vykoná v rovnakom čase - ~ 35 ms pre zoradené čísla, ~ 200 ms pre zamiešané čísla - pri počítaní 10 000 000 čísel bez ohľadu na hodnotu medzná hodnota.

To je preto, že prediktor vetvy narába s oboma vetvami rovnako a správne uhádnuť, ktorou cestou sa pre nich vydáme.

5.3. Kombinované podmienky

Čo ak máme na výber medzi jednou alebo dvoma podmienkami? Je možné, že môžeme svoju logiku prepísať iným spôsobom, ktorý sa chová rovnako, ale mali by sme to urobiť?

Napríklad, ak porovnávame dve čísla s 0, alternatívnym prístupom je ich spoločné vynásobenie a porovnanie výsledku s 0. Týmto potom podmienku nahradíme násobením. Ale stojí to za to?

Uvažujme príklad:

long [] first = LongStream.range (0, TOP) .map (n -> Math.random () Math.random () <FRACTION? 0: n) .toArray (); dlhý počet = 0; dlhý štart = System.currentTimeMillis (); for (int i = 0; i <TOP; i ++) {if (first [i]! = 0 && second [i]! = 0) {++ count; }} dlhý koniec = System.currentTimeMillis (); LOG.info ("Počítané {} / {} čísla pomocou samostatného režimu v {} ms", počet, TOP, koniec - začiatok);

Náš stav vo vnútri slučky môže byť nahradený, ako je opísané vyššie. Toto skutočne ovplyvní runtime:

• Samostatné podmienky - 40ms
• Viacnásobná a jednoduchá podmienka - 22 ms

Možnosť, ktorá používa dve rôzne podmienky, sa teda v skutočnosti realizuje dvakrát tak dlho.

6. Záver

Videli sme, čo je odvetvová predpoveď a ako môže mať vplyv na naše programy. To nám môže poskytnúť niekoľko ďalších nástrojov na opasku, ktoré zabezpečia, aby boli naše programy čo najefektívnejšie.

Ako to však vždy býva, pred vykonaním zásadných zmien si musíme nezabudnúť profilovať náš kód. Niekedy sa môže stať, že vykonanie zmien, ktoré pomôžu predikcii odvetvia, stojí viac inými spôsobmi.

Príklady prípadov z tohto článku sú k dispozícii na GitHub.