it-swarm-eu.dev

Proč je rychlejší zpracovávat tříděné pole než netříděné pole?

Zde je kus kódu C++, který se zdá být velmi zvláštní. Z nějakého zvláštního důvodu zázračně roztřídí data kód téměř šestkrát rychleji.

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::Rand() % 256;

    // !!! With this, the next loop runs faster
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}
  • Bez std::sort(data, data + arraySize); se kód spustí v 11,54 sekundách.
  • S roztříděnými daty se kód spustí za 1,93 sekundy.

Zpočátku jsem si myslel, že to může být jen jazyk nebo komplikace. Tak jsem to zkusil v Javě.

import Java.util.Arrays;
import Java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // Generate data
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c)
            data[c] = rnd.nextInt() % 256;

        // !!! With this, the next loop runs faster
        Arrays.sort(data);

        // Test
        long start = System.nanoTime();
        long sum = 0;

        for (int i = 0; i < 100000; ++i)
        {
            // Primary loop
            for (int c = 0; c < arraySize; ++c)
            {
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

S poněkud podobným, ale méně extrémním výsledkem.


Moje první myšlenka byla, že třídění přináší data do mezipaměti, ale pak jsem si myslel, jak je to hloupé, protože pole bylo právě vygenerováno.

  • Co se děje?
  • Proč je rychlejší zpracovávat tříděné pole než netříděné pole?
  • Kód sčítá některé nezávislé výrazy a pořadí by nemělo být důležité.
22968
GManNickG

Předikce oboru.

Se tříděným polem je podmínka data[c] >= 128 první false pro pruh hodnot, pak se stane true pro všechny pozdější hodnoty. To je snadné předvídat. S netříděným polem zaplatíte za rozvětvení cenu.

3879
Daniel Fischer

Důvodem, proč se výkon při zjišťování dat výrazně zvyšuje, je to, že věta o předpovědi trestu je odstraněna, jak je krásně vysvětleno v odpovědi Mysticial odpověď.

Když se podíváme na kód

if (data[c] >= 128)
    sum += data[c];

můžeme zjistit, že význam této věty if... else... je přidat něco, když je podmínka splněna. Tento typ větve lze snadno transformovat na podmíněný tah příkaz, který by byl zkompilován do podmíněné instrukce pohybu: cmovl, v systému x86. Větev a tím potenciální trest předpovědi větve je odstraněn.

V C, tedy C++, je příkaz, který by kompiloval přímo (bez jakékoli optimalizace) do instrukce podmíněného pohybu v x86, ternárním operátorem ... ? ... : .... Výše uvedené prohlášení přepíšeme na ekvivalentní:

sum += data[c] >=128 ? data[c] : 0;

Při zachování čitelnosti můžeme kontrolovat faktor zrychlení.

Na Intel Core i7 2600K @ 3.4 GHz a Visual Studio 2010 Release Mode je měřítkem (formát zkopírovaný z Mysticial):

x86

//  Branch - Random
seconds = 8.885

//  Branch - Sorted
seconds = 1.528

//  Branchless - Random
seconds = 3.716

//  Branchless - Sorted
seconds = 3.71

x64

//  Branch - Random
seconds = 11.302

//  Branch - Sorted
 seconds = 1.830

//  Branchless - Random
seconds = 2.736

//  Branchless - Sorted
seconds = 2.737

Výsledek je robustní ve více testech. Dostáváme velké zrychlení, když výsledek pobočky je nepředvídatelný, ale trpíme trochu, když je předvídatelný. Ve skutečnosti, když používáte podmíněný pohyb, výkon je stejný bez ohledu na datový vzor.

Podívejme se nyní podrobněji zkoumáním x86 shromáždění, které generují. Pro jednoduchost používáme dvě funkce max1 a max2.

max1 používá podmíněnou větev if... else ...:

int max1(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}

max2 používá ternární operátor ... ? ... : ...:

int max2(int a, int b) {
    return a > b ? a : b;
}

Na počítači x86-64 GCC -S vygeneruje sestavu níže.

:max1
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    -8(%rbp), %eax
    jle     .L2
    movl    -4(%rbp), %eax
    movl    %eax, -12(%rbp)
    jmp     .L4
.L2:
    movl    -8(%rbp), %eax
    movl    %eax, -12(%rbp)
.L4:
    movl    -12(%rbp), %eax
    leave
    ret

:max2
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    %eax, -8(%rbp)
    cmovge  -8(%rbp), %eax
    leave
    ret

max2 používá mnohem méně kódu z důvodu použití instrukce cmovge. Ale skutečný zisk je, že max2 nezahrnuje skoky větví, jmp, které by měly významný výkonový trest, pokud by předpovídaný výsledek nebyl správný.

Tak proč je podmíněný pohyb lepší?

V typickém procesoru x86 je provedení instrukce rozděleno do několika fází. Hrubě, máme různé hardware pro řešení různých fází. Takže nemusíme čekat, až jeden pokyn dokončí nový. Toto se nazývápipelining.

V případě pobočky je následující instrukce určena předcházející, takže nemůžeme provádět pipelining. Musíme buď čekat, nebo předvídat.

V případě podmíněného přesunu je příkaz k provedení podmíněného přesunu rozdělen do několika fází, ale dřívější fáze jako Fetch a Decode nezávisí na výsledku předchozí instrukce; pouze poslední fáze potřebují výsledek. Čekáme tedy zlomek času provedení jedné instrukce. Proto je verze podmíněného přesunu pomalejší než větev, když je predikce snadná.

Kniha Počítačové systémy: Perspektiva programátora, druhé vydání to podrobně vysvětluje. Oddíl 3.6.6 pro instrukce pro podmíněné přesuny, celou kapitolu 4 pro architekturu procesoru a oddíl 5.11.2 můžete zkontrolovat pro speciální ošetření pro predikce poboček a sankce predikce.

Někdy mohou některé moderní kompilátory optimalizovat náš kód na Assembly s lepším výkonem, někdy některé kompilátory nemohou (daný kód používá nativní kompilátor Visual Studio). Znalost rozdílu výkonu mezi větvemi a podmíněným pohybem, když je nepředvídatelný, nám může pomoci zapsat kód s lepším výkonem, když se scénář dostane tak složitě, že jej kompilátor nemůže automaticky optimalizovat.

3125
WiSaGaN

Pokud vás zajímá ještě více optimalizací, které lze v tomto kódu provést, zvažte následující:

Počínaje původní smyčkou:

for (unsigned i = 0; i < 100000; ++i)
{
    for (unsigned j = 0; j < arraySize; ++j)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

Se smyčkovou výměnou můžeme tuto smyčku bezpečně změnit na:

for (unsigned j = 0; j < arraySize; ++j)
{
    for (unsigned i = 0; i < 100000; ++i)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

Pak můžete vidět, že if podmíněné je konstantní během provádění smyčky i, takže můžete if vypnout:

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        for (unsigned i = 0; i < 100000; ++i)
        {
            sum += data[j];
        }
    }
}

Pak vidíte, že vnitřní smyčka může být sbalena do jediného výrazu, za předpokladu, že to umožňuje model s plovoucí desetinnou čárkou (/ fp: fast je například vyvolán)

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        sum += data[j] * 100000;
    }
}

Ten je 100 000x rychlejší než dříve

2143
vulcan raven

Někteří z nás by se nepochybně zajímali o způsoby identifikace kódu, který je problematický pro prediktor větví CPU. Nástroj Valgrind cachegrind má simulátor předpovědi větví, který je povolen pomocí příznaku --branch-sim=yes. Spuštění těchto příkladů v této otázce s počtem vnějších smyček snížených na 10000 a kompilací s g++ dává tyto výsledky:

Řazeno:

==32551== Branches:        656,645,130  (  656,609,208 cond +    35,922 ind)
==32551== Mispredicts:         169,556  (      169,095 cond +       461 ind)
==32551== Mispred rate:            0.0% (          0.0%     +       1.2%   )

Nezařazeno:

==32555== Branches:        655,996,082  (  655,960,160 cond +  35,922 ind)
==32555== Mispredicts:     164,073,152  (  164,072,692 cond +     460 ind)
==32555== Mispred rate:           25.0% (         25.0%     +     1.2%   )

Vrtání do výstupu line-by-line vytvořeného pomocí cg_annotate, které vidíme pro danou smyčku:

Řazeno:

          Bc    Bcm Bi Bim
      10,001      4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .      .  .   .      {
           .      .  .   .          // primary loop
 327,690,000 10,016  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .      .  .   .          {
 327,680,000 10,006  0   0              if (data[c] >= 128)
           0      0  0   0                  sum += data[c];
           .      .  .   .          }
           .      .  .   .      }

Nezařazeno:

          Bc         Bcm Bi Bim
      10,001           4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .           .  .   .      {
           .           .  .   .          // primary loop
 327,690,000      10,038  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .           .  .   .          {
 327,680,000 164,050,007  0   0              if (data[c] >= 128)
           0           0  0   0                  sum += data[c];
           .           .  .   .          }
           .           .  .   .      }

To vám umožní snadno identifikovat problematickou linku - v netříděné verzi způsobí řádek if (data[c] >= 128) 164,050,007 nepředvídaných podmíněných větví (Bcm) pod modelem prediktoru větev cachegrind, zatímco v tříděné verzi způsobuje pouze 10 006.


Alternativně můžete v Linuxu použít podsystém čítačů výkonu k provedení stejného úkolu, ale s nativním výkonem pomocí čítačů CPU.

perf stat ./sumtest_sorted

Řazeno:

 Performance counter stats for './sumtest_sorted':

  11808.095776 task-clock                #    0.998 CPUs utilized          
         1,062 context-switches          #    0.090 K/sec                  
            14 CPU-migrations            #    0.001 K/sec                  
           337 page-faults               #    0.029 K/sec                  
26,487,882,764 cycles                    #    2.243 GHz                    
41,025,654,322 instructions              #    1.55  insns per cycle        
 6,558,871,379 branches                  #  555.455 M/sec                  
       567,204 branch-misses             #    0.01% of all branches        

  11.827228330 seconds time elapsed

Nezařazeno:

 Performance counter stats for './sumtest_unsorted':

  28877.954344 task-clock                #    0.998 CPUs utilized          
         2,584 context-switches          #    0.089 K/sec                  
            18 CPU-migrations            #    0.001 K/sec                  
           335 page-faults               #    0.012 K/sec                  
65,076,127,595 cycles                    #    2.253 GHz                    
41,032,528,741 instructions              #    0.63  insns per cycle        
 6,560,579,013 branches                  #  227.183 M/sec                  
 1,646,394,749 branch-misses             #   25.10% of all branches        

  28.935500947 seconds time elapsed

To může také dělat anotaci zdrojového kódu s disassembly.

perf record -e branch-misses ./sumtest_unsorted
perf annotate -d sumtest_unsorted
 Percent |      Source code & Disassembly of sumtest_unsorted
------------------------------------------------
...
         :                      sum += data[c];
    0.00 :        400a1a:       mov    -0x14(%rbp),%eax
   39.97 :        400a1d:       mov    %eax,%eax
    5.31 :        400a1f:       mov    -0x20040(%rbp,%rax,4),%eax
    4.60 :        400a26:       cltq   
    0.00 :        400a28:       add    %rax,-0x30(%rbp)
...

Další informace naleznete v tématu návod k výkonu .

1784
caf

Prostě jsem si přečetl tuto otázku a její odpovědi a cítím, že chybí odpověď.

Běžným způsobem, jak eliminovat predikci poboček, které fungují zvláště dobře ve spravovaných jazycích, je vyhledávání v tabulce namísto použití pobočky (i když jsem to v tomto případě netestovala).

Tento přístup funguje obecně, pokud:

  1. je to malý stůl a je pravděpodobné, že bude v mezipaměti v procesoru a
  2. spouštíte věci v poměrně těsné smyčce a/nebo procesor může načíst data.

Souvislosti a proč

Z pohledu procesoru je paměť pomalá. Pro vyrovnání rozdílu v rychlosti je do procesoru zabudováno několik vyrovnávacích pamětí (vyrovnávací paměť L1/L2). Představte si, že děláte své Nice výpočty a zjistíte, že potřebujete kus paměti. Procesor dostane svou operaci „načtení“ a načte paměť do vyrovnávací paměti - a pak použije mezipaměť k provedení dalších výpočtů. Protože paměť je poměrně pomalá, toto 'zatížení' zpomalí váš program.

Stejně jako predikce poboček, bylo to optimalizováno v procesoru Pentium: procesor předpovídá, že potřebuje načíst data a pokusí se je načíst do mezipaměti dříve, než operace skutečně udeří do mezipaměti. Jak jsme již viděli, předpovědi poboček se někdy dějí strašně špatně - v nejhorším případě je třeba se vrátit a skutečně čekat na paměťovou zátěž, která bude trvat věčně ( jinými slovy: selhání predikce pobočky je špatná, zatížení paměti po selhání předpovědi větve je prostě hrozné! ).

Naštěstí pro nás, pokud je přístup k paměti předvídatelný, procesor jej načte do své rychlé vyrovnávací paměti a vše je v pořádku.

První věc, kterou potřebujeme vědět, je to, co je malé ? Zatímco menší je obecně lepší, pravidlem je držet se vyhledávacích tabulek o velikosti <= 4096 bytů. Jako horní limit: pokud je vaše vyhledávací tabulka větší než 64 kB, pravděpodobně stojí za to znovu zvážit.

Sestavení tabulky

Takže jsme zjistili, že můžeme vytvořit malý stůl. Další věc, kterou musíte udělat, je získat vyhledávací funkci na místě. Funkce vyhledávání jsou obvykle malé funkce, které používají několik základních celočíselných operací (a, nebo, xor, posun, přidání, odstranění a možná násobení). Chcete, aby váš vstup byl přeložen vyhledávací funkcí do nějakého „jedinečného klíče“ ve vašem stole, který vám pak jednoduše dá odpověď na veškerou práci, kterou jste chtěli udělat.

V tomto případě:> = 128 znamená, že můžeme udržet hodnotu, <128 znamená, že se toho zbavíme. Nejjednodušší způsob, jak to udělat, je pomocí 'AND': pokud si to ponecháme, my A s 7FFFFFFF; chceme-li se ho zbavit, my A to s 0. Všimněte si také, že 128 je síla 2 - takže můžeme jít dopředu a vytvořit tabulku 32768/128 celých čísel a vyplnit ji jednou nula a hodně 7FFFFFFFFF je.

Spravované jazyky

Možná se divíte, proč to funguje dobře v řízených jazycích. Nakonec, řízené jazyky kontrolují hranice polí s pobočkou, aby bylo zajištěno, že se nepořádáte ...

No, ne přesně ... :-)

Došlo k určité práci na odstranění této větve pro řízené jazyky. Například:

for (int i = 0; i < array.Length; ++i)
{
   // Use array[i]
}

V tomto případě je kompilátoru zřejmé, že hraniční podmínka nebude nikdy zasažena. Přinejmenším kompilátor Microsoft JIT (ale předpokládám, že Java dělá podobné věci) si toho všimne a odstraní šek. WOW, to znamená žádná větev. Stejně tak se bude zabývat dalšími zřejmými případy.

Pokud narazíte na potíže s vyhledáváním ve spravovaných jazycích - klíčem je přidat & 0x[something]FFF do vyhledávací funkce, aby bylo možné předvídat hraniční kontrolu - a sledovat, jak rychleji běží.

Výsledek tohoto případu

// Generate data
int arraySize = 32768;
int[] data = new int[arraySize];

Random random = new Random(0);
for (int c = 0; c < arraySize; ++c)
{
    data[c] = random.Next(256);
}

/*To keep the spirit of the code intact, I'll make a separate lookup table
(I assume we cannot modify 'data' or the number of loops)*/

int[] lookup = new int[256];

for (int c = 0; c < 256; ++c)
{
    lookup[c] = (c >= 128) ? c : 0;
}

// Test
DateTime startTime = System.DateTime.Now;
long sum = 0;

for (int i = 0; i < 100000; ++i)
{
    // Primary loop
    for (int j = 0; j < arraySize; ++j)
    {
        /* Here you basically want to use simple operations - so no
        random branches, but things like &, |, *, -, +, etc. are fine. */
        sum += lookup[data[j]];
    }
}

DateTime endTime = System.DateTime.Now;
Console.WriteLine(endTime - startTime);
Console.WriteLine("sum = " + sum);
Console.ReadLine();
1247
atlaste

Jak jsou data rozdělena mezi 0 a 255, když je pole tříděno, kolem první poloviny iterací nebude zadán příkaz if- (příkaz if je sdílen níže).

if (data[c] >= 128)
    sum += data[c];

Otázka zní: Co dělá výše uvedené prohlášení v určitých případech neprovedené jako v případě tříděných dat? Zde přichází "prediktor větví". Prediktor větve je digitální obvod, který se snaží odhadnout, jakým způsobem bude větev (např. Struktura if-then-else) jít dříve, než je to známo. Účelem prediktoru poboček je zlepšit tok v instrukčním potrubí. Věkové prediktory hrají rozhodující roli při dosahování vysokého efektivního výkonu!

Pojďme udělat nějaké lavičkové značení, abychom to lépe pochopili

Výkon if-výkazu závisí na tom, zda má jeho stav předvídatelný vzor. Je-li podmínka vždy pravdivá nebo vždy nepravdivá, logika predikce větve v procesoru bude vzorek odebírat. Na druhou stranu, pokud je vzor nepředvídatelný, příkaz if- bude mnohem dražší.

Změřte výkon této smyčky s různými podmínkami:

for (int i = 0; i < max; i++)
    if (condition)
        sum++;

Zde jsou časy smyčky s různými pravdivými vzory:

Condition                Pattern             Time (ms)
-------------------------------------------------------
(i & 0×80000000) == 0    T repeated          322

(i & 0xffffffff) == 0    F repeated          276

(i & 1) == 0             TF alternating      760

(i & 3) == 0             TFFFTFFF…           513

(i & 2) == 0             TTFFTTFF…           1675

(i & 4) == 0             TTTTFFFFTTTTFFFF…   1275

(i & 8) == 0             8T 8F 8T 8F …       752

(i & 16) == 0            16T 16F 16T 16F …   490

" špatný " pravdivý vzor může vytvořit if- prohlášení až šestkrát pomalejší než " dobrý " vzor! Samozřejmě, který vzor je dobrý a který je špatný, závisí na přesných pokynech generovaných kompilátorem a na konkrétním procesoru.

Není tedy pochyb o dopadu predikce odvětví na výkon!

1118
Saqlain

Jedním ze způsobů, jak se vyhnout chybám predikce větve, je vytvořit vyhledávací tabulku a indexovat ji pomocí dat. Stefan de Bruijn o tom hovořil ve své odpovědi.

Ale v tomto případě víme, že hodnoty jsou v rozsahu [0, 255] a my se staráme pouze o hodnoty> = 128. To znamená, že můžeme snadno extrahovat jeden bit, který nám řekne, zda chceme hodnotu, nebo ne: posunem data napravo 7 bitů, zůstali jsme s 0 bitem nebo 1 bitem a chceme přidat pouze hodnotu, když máme 1 bit. Zavolejme tento bit "rozhodovací bit".

Použitím hodnoty 0/1 rozhodovacího bitu jako indexu do pole můžeme vytvořit kód, který bude stejně rychlý, ať už jsou data tříděna nebo neusazena. Náš kód bude vždy přidávat hodnotu, ale když rozhodovací bit je 0, přidáme hodnotu někde, na čem nám nezáleží. Zde je kód:

// Test
clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];

Tento kód plýtvá polovinou přidání, ale nikdy nemá selhání předpovědi větve. Je to ohromně rychlejší na náhodných datech než verze se skutečným if.

Ale v mém testování byla explicitní vyhledávací tabulka o něco rychlejší, pravděpodobně proto, že indexování do vyhledávací tabulky bylo o něco rychlejší než posun bitů. To ukazuje, jak můj kód nastavuje a používá vyhledávací tabulku (unimaginatively nazývá lut pro "LookUp tabulka" v kódu). Zde je kód C++:

// declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

V tomto případě byla vyhledávací tabulka pouze 256 bytů, takže se dobře vejde do mezipaměti a vše bylo rychlé. Tato technika by nefungovala dobře, kdyby data byla 24bitová a my jsme chtěli jen polovinu z nich ... vyhledávací tabulka by byla příliš velká, než aby byla praktická. Na druhou stranu můžeme kombinovat obě výše uvedené techniky: nejprve přesunout bity, pak indexovat vyhledávací tabulku. Pro 24bitovou hodnotu, kterou chceme pouze pro horní poloviční hodnotu, bychom mohli potenciálně posunout data vpravo o 12 bitů a ponechat 12bitovou hodnotu pro tabulkový index. 12bitový tabulkový index předpokládá tabulku 4096 hodnot, což může být praktické.

Technika indexování do pole, namísto použití příkazu if, může být použita pro rozhodování, který ukazatel použít. Viděl jsem knihovnu, která implementovala binární stromy, a místo toho, aby měl dva pojmenované ukazatele (pLeft a pRight nebo cokoliv), měl délku-2 pole ukazatelů a použil techniku ​​"rozhodovacího bit", aby se rozhodl, který z nich bude následovat. Například místo:

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;

tato knihovna by udělala něco jako:

i = (x < node->value);
node = node->link[i];

Zde je odkaz na tento kód: Red Black Trees , Eternally Confuzzled

1039
steveha

V roztříděném případě můžete udělat lépe, než se spoléhat na úspěšnou předpovědi větví nebo jakýkoli trik pro porovnání bez větví: pobočku zcela odstranit.

Pole je totiž rozděleno do sousední zóny pomocí data < 128 a další s data >= 128. Měli byste tedy najít bod rozdělení pomocí dichotomického vyhledávání (pomocí Lg(arraySize) = 15 srovnání), pak proveďte přímou akumulaci z tohoto bodu.

Něco jako (nezaškrtnuté)

int i= 0, j, k= arraySize;
while (i < k)
{
  j= (i + k) >> 1;
  if (data[j] >= 128)
    k= j;
  else
    i= j;
}
sum= 0;
for (; i < arraySize; i++)
  sum+= data[i];

nebo mírně zmatenější

int i, k, j= (i + k) >> 1;
for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
  j= (i + k) >> 1;
for (sum= 0; i < arraySize; i++)
  sum+= data[i];

Ještě rychlejší přístup, který dává přibližný řešení pro tříděný nebo netříděný je: sum= 3137536; (za předpokladu, že je skutečně jednotné rozdělení, 16384 vzorků s očekávanou hodnotou 191,5) :-)

942
Yves Daoust

Výše uvedené chování se děje kvůli Branch predikci.

K pochopení predikce vět je třeba nejprve porozumět instrukční potrubí :

Každá instrukce je rozdělena do posloupnosti kroků tak, aby mohly být paralelně prováděny různé kroky. Tato technika je známá jako instrukce pipeline a to se používá ke zvýšení propustnosti v moderních procesorech. Abyste to pochopili lépe, podívejte se na toto příklad na Wikipedii .

Obecně platí, že moderní procesory mají poměrně dlouhá potrubí, ale pro snadné uvažujme pouze tyto 4 kroky.

  1. IF - Načtení instrukce z paměti
  2. ID - Dekódování instrukce
  3. EX - Proveďte instrukci
  4. WB - Zápis zpět do registru CPU

4-stupňové potrubí obecně pro 2 instrukce. 4-stage pipeline in general

Vraťme se zpět k výše uvedené otázce.

                        A) if (data[c] >= 128)
                                /\
                               /  \
                              /    \
                        true /      \ false
                            /        \
                           /          \
                          /            \
                         /              \
              B) sum += data[c];          C) for loop or print().

Bez predikce větve by nastalo následující:

Pro provedení instrukce B nebo instrukce C bude procesor muset počkat, dokud instrukce A nedosáhne do fáze EX v potrubí, protože rozhodnutí jít do instrukce B nebo instrukce C závisí na výsledku instrukce A. Takže potrubí bude vypadat takto.

když podmínka vrátí hodnotu true: enter image description here

Pokud podmínka vrátí hodnotu false: enter image description here

V důsledku čekání na výsledek instrukce A, celkové cykly CPU strávené ve výše uvedeném případě (bez predikce větve, pro oba true a false) je 7.

Tak co je to věta predikce?

Branch prediktor se pokusí odhadnout, jakým způsobem bude větev (struktura if-then-else) jít dříve, než je to známo. Nebude čekat, až instrukce A dosáhne fáze EX potrubí, ale bude hádat rozhodnutí a jít na instrukci (B nebo C v případě našeho příkladu).

V případě správného odhadu, potrubí vypadá něco takového: enter image description here

Pokud je později zjištěno, že odhad byl chybný, částečně provedené instrukce jsou vyřazeny a potrubí začíná přes správnou větev, což způsobuje zpoždění. Čas, který je promarněn v případě chybné předpovědi větve, se rovná počtu fází v potrubí od fáze načítání do fáze spuštění. Moderní mikroprocesory mají tendenci mít poměrně dlouhé potrubí, takže zpoždění předpovědi je mezi 10 a 20 hodinovými cykly. Čím delší je potrubí, tím větší je potřeba dobrý pobočkový prediktor .

V kódu OP poprvé, když je podmíněný, nemá pobočkový prediktor žádné informace, které by umožnily zakládat predikci, takže při prvním výběru náhodně vybere další instrukci. Později ve smyčce for může vycházet z predikce historie. Pro pole seřazené vzestupně existují tři možnosti:

  1. Všechny prvky jsou menší než 128
  2. Všechny prvky jsou větší než 128
  3. Některé nové nové prvky jsou menší než 128 a později větší než 128

Předpokládejme, že prediktor bude vždy předpokládat skutečnou větev na prvním běhu.

Takže v prvním případě bude vždy trvat věrné odvětví, protože historicky jsou všechny jeho předpovědi správné. Ve druhém případě bude zpočátku předpovídat špatně, ale po několika iteracích bude správně předpovídat. Ve třetím případě bude zpočátku správně předpovídat, dokud elementy nebudou menší než 128. Po kterém bude po určitou dobu neúspěšný a správný, když uvidí selhání predikce větve v historii.

Ve všech těchto případech bude počet selhání příliš menší a v důsledku toho bude nutné několikrát zrušit částečně provedené instrukce a začít znovu se správnou větví, což vede k menšímu počtu cyklů CPU.

V případě náhodného netříděného pole však bude muset predikce většinu času zrušit částečně provedené instrukce a začít se správnou větví a mít za následek více cyklů CPU ve srovnání s tříděným polem.

765
Harsh Sharma

Oficiální odpověď by byla od

  1. Intel - Vyhnout se nákladům na nepředvídatelnost poboček
  2. Reorganizace poboček a smyček společnosti Intel pro prevenci nepředvídaných událostí
  3. Vědecké práce - obor predikce počítačové architektury
  4. Knihy: J.L. Hennessy, D.A. Patterson: Počítačová architektura: kvantitativní přístup
  5. Články ve vědeckých publikacích: T.Y. Yeh, Y.N. Patt z nich udělal hodně na předpovědích větví.

Můžete také vidět z tohoto krásného diagramu proč se větev prediktor dostane zmatený.

 2-bit state diagram

Každý prvek v původním kódu je náhodná hodnota

data[c] = std::Rand() % 256;

prediktor tak změní strany jako ránu std::Rand().

Na druhé straně, jakmile je to roztříděno, bude se prediktor nejprve přemístit do stavu, kdy se nebere v úvahu, a když se hodnoty změní na vysokou hodnotu, prediktor se ve třech cyklech změní přes celou cestu od silně nepřijatých.


669
Surt

V téže linii (myslím, že to nebyla nějaká odpověď zvýrazněna) je dobré zmínit se, že někdy (zejména v softwaru, kde je důležitý výkon - jako v jádře Linuxu) můžete najít některé příkazy, například následující:

if (likely( everything_is_ok ))
{
    /* Do something */
}

nebo podobně:

if (unlikely(very_improbable_condition))
{
    /* Do something */    
}

Jak likely(), tak unlikely() jsou ve skutečnosti makra, která jsou definována pomocí něčeho jako __builtin_expect GCC, aby pomohla kompilátoru vložit predikční kód, který zvýhodní podmínku s ohledem na informace poskytnuté uživatelem. GCC podporuje další vestavěné moduly, které by mohly změnit chování běžícího programu nebo vydávat instrukce s nízkou úrovní, například vymazání mezipaměti atd. Viz tato dokumentace která prochází dostupnými vestavěnými moduly GCC.

Normálně se tento druh optimalizací nachází hlavně v aplikacích s pevným reálným časem nebo vestavěných systémech, kde je důležitá doba provedení a je kritická. Například, pokud kontrolujete nějakou chybovou podmínku, která se stane pouze 1/10000000 krát, pak proč neinformovat kompilátor o tom? Tímto způsobem by ve výchozím nastavení předpokládalo, že podmínka je nepravdivá.

634
rkachach

Často používané booleovské operace v C++ produkují mnoho vět v kompilovaném programu. Pokud jsou tyto větve uvnitř smyček a je těžké je předpovědět, mohou významně zpomalit provádění. Boolean proměnné jsou uloženy jako 8-bitová celá čísla s hodnotou 0 pro false a 1 pro true.

Boolean proměnné jsou overdetermined v tom smyslu, že všichni operátoři, kteří mají Boolean proměnné jako vstup zkontrolují jestliže vstupy mají nějakou jinou hodnotu než 0 nebo 1, ale operátoři, kteří mají Booleans jako výstup mohou produkovat žádnou jinou hodnotu než 0 nebo 1. Díky tomu jsou operace s logickými proměnnými méně efektivní než vstupy. Zvažte příklad:

bool a, b, c, d;
c = a && b;
d = a || b;

Kompilátor je obvykle implementován následujícím způsobem:

bool a, b, c, d;
if (a != 0) {
    if (b != 0) {
        c = 1;
    }
    else {
        goto CFALSE;
    }
}
else {
    CFALSE:
    c = 0;
}
if (a == 0) {
    if (b == 0) {
        d = 0;
    }
    else {
        goto DTRUE;
    }
}
else {
    DTRUE:
    d = 1;
}

Tento kód není zdaleka optimální. Pobočky mohou v případě předvídání trvat dlouho. Booleovské operace mohou být mnohem efektivnější, pokud je s jistotou známo, že operandy nemají jiné hodnoty než 0 a 1. Důvod, proč kompilátor nepředpokládá takový předpoklad, je, že proměnné mohou mít jiné hodnoty, pokud jsou neinicializované nebo pocházejí z neznámých zdrojů. Výše uvedený kód lze optimalizovat, pokud a a b byly inicializovány na platné hodnoty nebo pokud pocházejí od operátorů, kteří produkují logický výstup. Optimalizovaný kód vypadá takto:

char a = 0, b = 1, c, d;
c = a & b;
d = a | b;

char se používá místo bool, aby bylo možné použít bitové operátory (& a |) namísto logických operátorů (&& a ||). Operátory bitů jsou jednotlivé instrukce, které zabírají pouze jeden hodinový cyklus. Operátor OR (|) pracuje, i když mají a a b jiné hodnoty než 0 nebo 1. Operátor AND (&) a operátor EXCLUSIVE OR (^) mohou dát nekonzistentní výsledky, pokud operandy mají jiné hodnoty než 0 a 1.

~ nelze použít pro NOT. Místo toho můžete vytvořit proměnnou, která je známa jako 0 nebo 1 pomocí XOR'ing, pomocí proměnné 1:

bool a, b;
b = !a;

lze optimalizovat na:

char a = 0, b;
b = a ^ 1;

a && b nelze nahradit a & b pokud je b výraz, který by neměl být vyhodnocen, pokud a je false (&& nebude vyhodnocovat b, & bude). Podobně, a || b nemůže být nahrazený a | b jestliže b je výraz, který by neměl být vyhodnocen jestliže a je true.

Použití bitových operátorů je výhodnější, pokud operandy jsou proměnné, než kdyby operandy byly porovnány:

bool a; double x, y, z;
a = x > y && z < 5.0;

je ve většině případů optimální (pokud očekáváte, že výraz && vygeneruje mnoho chybných odhadů větví).

603
Maciej

To je jisté!...

Branchová predikce dělá logiku pomalejší, kvůli přepínání, které se děje ve vašem kódu! Je to jako když jdete rovnou ulicí nebo ulicí se spoustou zatáček, jistě, že rovný bude rychlejší! ...

Je-li pole tříděno, je váš stav v prvním kroku nepravdivý: data[c] >= 128, pak se stane skutečnou hodnotou pro celou cestu na konec ulice. To je, jak se dostanete na konec logiky rychleji. Na druhou stranu, s použitím netříděného pole, budete potřebovat hodně soustružení a zpracování, které váš kód běží pomaleji ...

Podívejte se na obrázek, který jsem pro vás vytvořil níže. Která ulice bude dokončena rychleji?

 Branch Prediction

Takže programově predikce větve způsobí, že proces bude pomalejší ...

Také na konci je dobré vědět, že máme dva druhy předpovědí vět, z nichž každý ovlivní váš kód jinak:

1. Statické

2. Dynamické

 Branch Prediction

Predikce statické větve je využívána mikroprocesorem při prvním výskytu podmíněné větve a pro úspěšné provádění podmíněného kódu větve je použita dynamická predikce větve.

Chcete-li efektivně napsat svůj kód, abyste mohli využít těchto pravidel, když zapisujete if-else nebo switch commands, nejdříve zkontrolujte nejčastější případy a postupně pracujte na nejběžnějších případech. Smyčky nutně nevyžadují žádné speciální objednání kódu pro statickou predikci větev, protože se obvykle používá pouze stav iterátoru smyčky.

280
Alireza

Tato otázka byla již mnohokrát zodpovězena. Ještě bych rád upozornil skupinu na další zajímavou analýzu.

V poslední době byl tento příklad (velmi mírně upraven) také použit jako způsob, jak ukázat, jak lze kus kódu profilovat v rámci samotného programu ve Windows. Po cestě autor také ukazuje, jak výsledky využít k určení, kde kód tráví většinu času v tříděném i netříděném případě. Nakonec tento článek také ukazuje, jak používat málo známou funkci HAL (Hardware Abstraction Layer) k určení toho, jak moc se nepředvídaná větev děje v netříděném případě.

Odkaz je zde: http://www.geoffchappell.com/studies/windows/km/ntoskrnl/api/ex/profile/demo.htm

262
ForeverLearning

Jak to, co již jiní zmínili, to, co stojí za záhadou, je Branch Predictor .

Nesnažím se něco přidat, ale vysvětlit tento koncept jiným způsobem. Na wiki je stručný úvod, který obsahuje text a diagram. Líbí se mi vysvětlení níže, které využívá diagramu k intuitivnímu zpracování předpovědi poboček.

V architektuře počítače je prediktorem větví digitální obvod, který se snaží odhadnout, jakým způsobem bude větev (např. Struktura if-then-else) jít dříve, než je to známo. Účelem prediktoru poboček je zlepšit tok v instrukčním potrubí. Branchové prediktory hrají rozhodující roli v dosahování vysokého efektivního výkonu v mnoha moderních architekturách s mikroprocesorem, jako je x86.

Obousměrné větvení je obvykle implementováno s instrukcí podmíněného skoku. Podmíněný skok může být buď "neberou" a pokračuje v provádění s první větou kódu, která následuje bezprostředně po podmíněném skoku, nebo může být "převzata" a skočit na jiné místo v paměti programu, kde je druhá větev kódu. uloženy. Není známo, zda bude podmíněný skok proveden nebo neproveden, dokud nebude podmínka vypočtena a podmíněný skok neprošel prováděcí fází v instrukčním potrubí (viz obr. 1).

 figure 1

Na základě popsaného scénáře jsem napsal ukázku animace, která ukazuje, jak jsou instrukce prováděny v potrubí v různých situacích.

  1. Bez předpovědi pobočky.

Bez predikce větve by procesor musel počkat, dokud instrukce podmíněného skoku projde fází spuštění, než další instrukce může vstoupit do fáze načítání v potrubí.

Příklad obsahuje tři instrukce a první je instrukce podmíněného skoku. Poslední dva instrukce mohou jít do potrubí, dokud není provedena instrukce podmíněného skoku.

 without branch predictor

Bude trvat 9 hodinových cyklů pro dokončení 3 instrukcí.

  1. Použijte Branch Predictor a neberte podmíněný skok. Předpokládejme, že predikce je ne beroucí podmíněný skok.

 enter image description here

Bude trvat 7 hodinových cyklů pro dokončení 3 instrukcí.

  1. Použijte Prediktor větve a proveďte podmíněný skok. Předpokládejme, že predikce je ne beroucí podmíněný skok.

 enter image description here

Bude trvat 9 hodinových cyklů pro dokončení 3 instrukcí.

Čas, který je promarněn v případě chybné předpovědi větve, se rovná počtu fází v potrubí od fáze načítání do fáze spuštění. Moderní mikroprocesory mají tendenci mít poměrně dlouhé potrubí, takže zpoždění předpovědi je mezi 10 a 20 hodinovými cykly. Výsledkem je, že delší potrubí zvyšuje potřebu pokročilejšího prediktoru poboček.

Jak vidíte, zdá se, že nemáme důvod nepoužívat Branch Predictor.

Je to docela jednoduché demo, které objasňuje základní část Branch Predictor. Pokud jsou tyto gify nepříjemné, neváhejte je odstranit z odpovědí a návštěvníci mohou také získat demo z git

176
Gearon

Zisk předpovědi poboček!

Je důležité pochopit, že nepředvídatelnost odvětví nezpomaluje programy. Náklady na zmeškanou predikci jsou stejné, jako kdyby neexistovala větev a čekali jste na vyhodnocení výrazu, který kód má spustit (další vysvětlení v následujícím odstavci).

if (expression)
{
    // Run 1
} else {
    // Run 2
}

Kdykoliv existuje příkaz if-else\switch, musí být výraz vyhodnocen, aby se určilo, který blok má být proveden. V kódu sestavy generovaném překladačem se vloží podmíněné větve instrukce.

Instrukce větve může způsobit, že počítač začne provádět jinou posloupnost instrukcí, a tak se odchýlí od svého výchozího chování provádění instrukcí v pořadí (tj. Pokud je výraz nepravdivý, program přeskočí kód bloku if) v závislosti na nějaké podmínce, která je hodnocení výrazu v našem případě.

Jak již bylo řečeno, kompilátor se snaží předpovědět výsledek před tím, než bude skutečně vyhodnocen. To přinese instrukce od if bloku, a jestliže výraz se ukáže být pravdivý, pak báječný! Získali jsme čas, který jsme potřebovali na jeho zhodnocení a pokroky v kodexu; pokud ne, pak jsme spustili nesprávný kód, potrubí je proplachováno a je spuštěn správný blok.

Vizualizace:

Řekněme, že je třeba vybrat trasu 1 nebo trasu 2. Čekání na partnera, aby si mapu zkontroloval, zastavili jste na ## a čekali, nebo jste si mohli vybrat pouze trasu 1 a pokud jste měli štěstí (trasa 1 je správná trasa), pak skvělé, že jste nemuseli čekat, až váš partner zkontroluje mapu (ušetřili jste čas, který by mu trvalo, než zkontroluje mapu), jinak se budete prostě zase vrátit.

Zatímco spláchnutí potrubí je super rychlé, v dnešní době se tento hazard vyplatí. Predikce tříděných dat nebo dat, která se mění pomalu, je vždy snazší a lepší než předvídání rychlých změn.

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------
168
Tony Tannous

Jde o předpověď pobočky. Co je to?

  • Odvětvový prediktor je jednou ze starodávných technik zlepšování výkonu, které stále nacházejí význam pro moderní architektury. Zatímco jednoduché predikční techniky poskytují rychlé vyhledávání a energetickou účinnost, trpí vysokou mírou nepředvídatelnosti.

  • Na druhou stranu, komplexní předpovědi odvětví - buď neurální, nebo varianty dvouúrovňové predikce větví - poskytují lepší přesnost predikce, ale spotřebovávají více síly a složitost exponenciálně roste.

  • Kromě toho, v komplexních technikách predikce je čas potřebný k předpovědi větví sám o sobě velmi vysoký –nařízení 2 až 5 cyklů - což je srovnatelné s časem provedení skutečných větví.

  • Predikce pobočky je v podstatě optimalizační (minimalizační) problém, kdy je kladen důraz na dosažení nejnižší možné míry chyb, nízké spotřeby energie a nízké složitosti s minimálními zdroji.

Existují tři různé druhy poboček:

Forward podmíněné větve - založené na podmínce run-time, PC (čítač programů) se změní tak, aby ukazoval na adresu vpřed v toku instrukcí.

Zpětné podmíněné větve - PC je změněno tak, aby směřovalo zpět v toku instrukcí. Větev je založena na nějaké podmínce, jako je rozvětvení zpět na začátek smyčky programu, když test na konci smyčky uvádí, že smyčka by měla být provedena znovu.

Nepodmíněné větve - to zahrnuje skoky, volání procedur a návraty, které nemají žádnou specifickou podmínku. Například instrukce bezpodmínečného skoku může být kódována v jazyce Assembly jako jednoduše "jmp" a tok instrukcí musí být okamžitě nasměrován na cílové umístění, na které odkazuje instrukce skoku, zatímco podmíněný skok, který může být kódován jako "jmpne" by přesměrování proudu instrukce pouze v případě, že výsledek porovnání dvou hodnot v předchozích instrukcích "porovnání" zobrazí hodnoty, které nebudou stejné. (Segmentované schéma adresování používané architekturou x86 přidává další složitost, protože skoky mohou být buď "blízko" (uvnitř segmentu) nebo "daleko" (mimo segment).

Statická/dynamická predikce větve : Mikrocesor používá predikci statické větve při prvním výskytu podmíněné větve a pro následné provádění kódu podmíněné větve se používá predikce dynamických větví.

Reference:

113
Farhad

Kromě toho, že vás predikce pobočky může zpomalit, má seřazené pole další výhodu:

Můžete mít podmínku zastavení namísto pouze kontrolu hodnoty, tímto způsobem budete pouze smyčku přes relevantní data, a ignorovat zbytek.
Predikce větve bude chybět pouze jednou.

 // sort backwards (higher values first), may be in some other part of the code
 std::sort(data, data + arraySize, std::greater<int>());

 for (unsigned c = 0; c < arraySize; ++c) {
       if (data[c] < 128) {
              break;
       }
       sum += data[c];               
 }
107
Yochai Timmer

Na ARM není potřeba žádná větev, protože každá instrukce má 4bitové stavové pole, které je testováno při nulových nákladech. To eliminuje potřebu krátkých větví a nedojde k žádnému zásahu do větve. Tříděná verze by proto byla spuštěna pomaleji než netříděná verze v modulu ARM, a to z důvodu nadměrné režie třídění. Vnitřní smyčka bude vypadat takto:

MOV R0, #0     // R0 = sum = 0
MOV R1, #0     // R1 = c = 0
ADR R2, data   // R2 = addr of data array (put this instruction outside outer loop)
.inner_loop    // Inner loop branch label
    LDRB R3, [R2, R1]     // R3 = data[c]
    CMP R3, #128          // compare R3 to 128
    ADDGE R0, R0, R3      // if R3 >= 128, then sum += data[c] -- no branch needed!
    ADD R1, R1, #1        // c++
    CMP R1, #arraySize    // compare c to arraySize
    BLT inner_loop        // Branch to inner_loop if c < arraySize
103
Luke Hutchison

Tříděná pole jsou zpracovávána rychleji než netříděná pole kvůli jevům nazývaným predikce větví.

Branch forecastor je digitální obvod (v počítačové architektuře), který se snaží předpovědět, jakým způsobem bude pobočka probíhat, což zlepšuje tok v instrukčním potrubí. Obvod/počítač předpovídá další krok a provede jej.

Dělat nesprávnou předpověď vede k návratu k předchozímu kroku a vykonávání s jinou predikcí. Za předpokladu, že předpověď je správná, bude kód pokračovat dalším krokem. Chybná predikce vede k opakování stejného kroku, dokud nedojde k správné predikci.

Odpověď na vaši otázku je velmi jednoduchá.

V netříděném poli počítač provede více předpovědí, což vede ke zvýšené pravděpodobnosti chyb. Vzhledem k tomu, že počítač třídí, předpovídá snížení pravděpodobnosti chyb. Více predikce vyžaduje více času.

Řazené pole: Straight Road

____________________________________________________________________________________
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

Nezařazené pole: Zakřivená cesta

______   ________
|     |__|

Predikce pobočky: Hádání/předpovídání, která silnice je přímá a následuje ji bez kontroly

___________________________________________ Straight road
 |_________________________________________|Longer road

I když obě silnice směřují do stejného cíle, přímá silnice je kratší a druhá delší. Pokud si pak vyberete jinou omylem, není zpětné otáčení, takže pokud si zvolíte delší silnici, budete ztrácet čas navíc. To je podobné tomu, co se děje v počítači, a doufám, že vám to pomohlo lépe porozumět.


Také chci citovat @Simon_Weaver z komentářů:

Neprovádí méně předpovědí - činí méně nesprávných předpovědí. Stále musí předvídat každou dobu smyčkou.

92
Omkaar.K

Předpoklad jiných odpovědí, že je třeba údaje třídit, není správný.

Následující kód neřídí celé pole, ale pouze jeho 200 segmentů, a tím běží nejrychleji.

Třídění pouze úseků elementů k dokončuje předběžné zpracování namísto n.log(n).

#include <algorithm>
#include <ctime>
#include <iostream>

int main() {
    int data[32768]; const int l = sizeof data / sizeof data[0];

    for (unsigned c = 0; c < l; ++c)
        data[c] = std::Rand() % 256;

    // sort 200-element segments, not the whole array
    for (unsigned c = 0; c + 200 <= l; c += 200)
        std::sort(&data[c], &data[c + 200]);

    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i) {
        for (unsigned c = 0; c < sizeof data / sizeof(int); ++c) {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    std::cout << static_cast<double>(clock() - start) / CLOCKS_PER_SEC << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

Toto také “dokazuje” že to nemá nic společného s nějakým algoritmickým problémem takový jako řazení, a to je opravdu větev předpověď.

14
user2297550

Protože je to tříděno!

Je snadné načíst a manipulovat s objednanými daty, než neuspořádané.

Stejně jako to, jak si vybírám oděvy z obchodů (objednané) a ze skříně (pokazené).

0
Arun Joshla