Varför går det snabbare att bearbeta en sorterad array än en osorterad array?
Här är ett stycke C++-kod som visar ett mycket märkligt beteende. Av någon märklig anledning gör sortering av data mirakulöst nog koden nästan sex gånger snabbare:
#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;
}- Utan
std::sort(data, data + arraySize);körs koden på 11,54 sekunder. - Med de sorterade uppgifterna körs koden på 1,93 sekunder.
Till en början trodde jag att detta bara kunde vara en språk- eller kompilatoravvikelse, så jag försökte med Java:
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);
}
}Med ett liknande men mindre extremt resultat.
Min första tanke var att sortering för in data i cacheminnet, men sedan tänkte jag att det var dumt eftersom matrisen just skapades.
- Vad är det som händer?
- Varför går det snabbare att bearbeta en sorterad array än en osorterad array?
Koden summerar några oberoende termer, så ordningen borde inte spela någon roll.
Du är ett offer för branch prediction fail.
Vad är grenförutsägelse?
Tänk på en järnvägskorsning:
[
]]3
Bild av Mecanismo, via Wikimedia Commons. Används under CC-By-SA 3.0-licensen.
Anta att vi befinner oss på 1800-talet - före långdistans- eller radiokommunikation.
Du är operatör vid en korsning och du hör ett tåg komma. Du har ingen aning om åt vilket håll det ska gå. Du stoppar tåget och frågar föraren vilken riktning han eller hon vill ha. Sedan ställer du om växeln på rätt sätt.
*Tåg är tunga och har stor tröghet. Därför tar det en evighet att starta och sakta ner.
Finns det ett bättre sätt? Du får gissa åt vilket håll tåget ska gå!
- Om du har gissat rätt fortsätter tåget.
-
Om du gissar fel stannar tågkaptenen, backar och skriker åt dig att du ska vända på växeln. Sedan kan det börja om på nytt längs den andra vägen. Om du gissar rätt varje gång behöver tåget aldrig stanna.
Om du gissar fel för ofta kommer tåget att spendera mycket tid på att stanna, backa och starta om.Konsultera en if-sats: På processorns nivå är det en greninstruktion:
Du är en processor och du ser en förgrening. Du har ingen aning om åt vilket håll den kommer att gå. Vad gör du? Du stoppar utförandet och väntar tills de tidigare instruktionerna är klara. Sedan fortsätter du på rätt väg.
*Moderna processorer är komplicerade och har långa pipelines. Så de tar evigheter att "värma upp" och "sakta ner".
Finns det ett bättre sätt? Du får gissa i vilken riktning grenen kommer att gå! - Om du gissade rätt fortsätter du att utföra.
-
Om du gissade fel måste du spola pipeline och gå tillbaka till grenen. Sedan kan du börja om på nytt längs den andra vägen. Om du gissar rätt varje gång behöver exekveringen aldrig avbrytas.
Om du gissar fel för ofta spenderar du mycket tid på att stanna upp, backa tillbaka och starta om.Det här är en grenförutsägelse. Jag medger att det inte är den bästa analogin eftersom tåget bara skulle kunna signalera riktningen med en flagga. Men i datorer vet processorn inte vilken riktning en gren kommer att gå förrän i sista stund. Så hur skulle du strategiskt gissa dig fram för att minimera antalet gånger som tåget måste backa och gå ner i den andra vägen? Du tittar på den tidigare historiken! Om tåget går till vänster 99 % av gångerna, gissar du till vänster. Om det växlar, växlar du dina gissningar. Om det går åt ett håll var tredje gång, gissar du samma sak... Med andra ord försöker man identifiera ett mönster och följa det. Det är ungefär så här som grenprediktorer fungerar. De flesta tillämpningar har välfungerande grenar. Så moderna grenprediktorer uppnår vanligtvis >90 % träfffrekvens. Men när de ställs inför oförutsägbara grenar utan igenkännbara mönster är grenprediktorer praktiskt taget värdelösa. Ytterligare läsning: "Branch predictor" artikel på Wikipedia.
Som antytts ovan är den skyldige den här if-satsen:
if (data[c] >= 128)
sum += data[c];Observera att uppgifterna är jämnt fördelade mellan 0 och 255. När data sorteras kommer ungefär den första hälften av iterationerna inte in i if-satsen. Därefter kommer alla att komma in i if-satsen. Detta är mycket vänligt för grenprediktoren eftersom grenen i följd går i samma riktning många gånger. Även en enkel mättande räknare kommer att förutsäga grenen korrekt utom för de få iterationer efter det att den byter riktning. Snabb visualisering:
T = branch taken
N = branch not taken
data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT (easy to predict)Men när data är helt slumpmässiga blir grenprediktoren oanvändbar, eftersom den inte kan förutsäga slumpmässiga data. Således kommer det troligen att finnas omkring 50 % felprediktion (inte bättre än slumpmässig gissning).
data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ...
branch = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ...
= TTNTTTTNTNNTTTN ... (completely random - hard to predict)Så vad kan man göra? Om kompilatorn inte kan optimera förgreningen till ett villkorligt drag kan du prova några hack om du är villig att offra läsbarhet för prestanda. Ersätt:
if (data[c] >= 128)
sum += data[c];med:
int t = (data[c] - 128) >> 31;
sum += ~t & data[c];Detta eliminerar grenen och ersätter den med några bitvisa operationer.
(Observera att detta hack inte är strikt likvärdigt med den ursprungliga if-satsen. Men i det här fallet är den giltig för alla ingångsvärden för data[].)
Benchmarks: Core i7 920 @ 3,5 GHz
C++ - Visual Studio 2010 - x64 Release
// Branch - Random
seconds = 11.777
// Branch - Sorted
seconds = 2.352
// Branchless - Random
seconds = 2.564
// Branchless - Sorted
seconds = 2.587Java - NetBeans 7.1.1 JDK 7 - x64
// Branch - Random
seconds = 10.93293813
// Branch - Sorted
seconds = 5.643797077
// Branchless - Random
seconds = 3.113581453
// Branchless - Sorted
seconds = 3.186068823Observationer:
- Med grenarna: Det är en stor skillnad mellan sorterade och osorterade data.
- Med Hack: Det finns ingen skillnad mellan sorterade och osorterade data.
-
I C++-fallet är hack faktiskt en aning långsammare än med gren när data är sorterade. En allmän tumregel är att undvika databeroende förgrening i kritiska slingor (som i det här exemplet).
Uppdatering:
- GCC 4.6.1 med
-O3eller-ftree-vectorizepå x64 kan generera ett villkorligt drag. Det är alltså ingen skillnad mellan sorterade och osorterade data - båda är snabba. - VC++ 2010 kan inte generera villkorliga flyttningar för den här grenen ens under
/Ox. - Intel C++ Compiler]5 (ICC) 11 gör något mirakulöst. Den byter ut de två slingorna och hissar därmed den oförutsägbara grenen till den yttre slingan. Så den är inte bara immun mot felförutsägelser, den är också dubbelt så snabb som vad VC++ och GCC kan generera! Med andra ord utnyttjade ICC testloopen för att besegra benchmarken...
- Om du ger Intel-kompilatorn den grenlösa koden, så vektoriserar den den helt enkelt... och är lika snabb som med grenen (med slingautbyte). Detta visar att även mogna moderna kompilatorer kan variera kraftigt i sin förmåga att optimera kod...
Branch prediktion.
I en sorterad matris är villkoret data[c] >= 128 först falsk för en rad värden, och blir sedan sann för alla senare värden. Det är lätt att förutsäga. Med en osorterad matris betalar du för förgreningskostnaden.
Anledningen till att prestandan förbättras drastiskt när datan är sorterad är att straffet för grenförutsägelse tas bort, vilket förklaras vackert i Mysticial's answer.
Om vi nu tittar på koden
if (data[c] >= 128)
sum += data[c];kan vi konstatera att innebörden av denna speciella "om... annars..."-gren är att lägga till något när ett villkor är uppfyllt. Denna typ av gren kan lätt omvandlas till en conditional move-anvisning, som skulle kompileras till en conditional move-instruktion: cmovl, i ett x86-system. Grenen och därmed den potentiella grenförutsägelsebestraffningen tas bort.
I C, och därmed C++, är det uttalande som skulle kompileras direkt (utan någon optimering) till den villkorliga flyttinstruktionen i x86, den ternära operatorn .... ? ... : .... Så vi skriver om ovanstående instruktion till en likvärdig instruktion:
sum += data[c] >=128 ? data[c] : 0;Samtidigt som vi behåller läsbarheten kan vi kontrollera hastighetsökningen.
På en Intel Core i7-2600K @ 3,4 GHz och Visual Studio 2010 Release Mode är riktmärket (format kopierat från Mysticial):
x86
// Branch - Random
seconds = 8.885
// Branch - Sorted
seconds = 1.528
// Branchless - Random
seconds = 3.716
// Branchless - Sorted
seconds = 3.71x64
// Branch - Random
seconds = 11.302
// Branch - Sorted
seconds = 1.830
// Branchless - Random
seconds = 2.736
// Branchless - Sorted
seconds = 2.737Resultatet är robust i flera tester. Vi får en stor ökning av hastigheten när grenresultatet är oförutsägbart, men vi lider lite när det är förutsägbart. Faktum är att när man använder ett villkorligt drag är prestandan densamma oavsett datamönster.
Låt oss nu titta närmare genom att undersöka x86-assemblen som de genererar. För enkelhetens skull använder vi två funktioner max1 och max2.
max1 använder den villkorliga grenen if... else ...:
int max1(int a, int b) {
if (a > b)
return a;
else
return b;
}max2 använder den ternära operatören ... ? ... : ...:
int max2(int a, int b) {
return a > b ? a : b;
}På en x86-64-maskin genererar GCC -S följande assemblering.
: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
retmax2 använder mycket mindre kod på grund av användningen av instruktionen cmovge. Men den verkliga vinsten är att max2 inte involverar grenhopp, jmp, vilket skulle ge en betydande prestandaförlust om det förutspådda resultatet inte är rätt.
Så varför presterar ett villkorligt drag bättre?
I en typisk x86-processor är utförandet av en instruktion uppdelat i flera steg. Grovt räknat har vi olika hårdvara för att hantera de olika stegen. Vi behöver alltså inte vänta på att en instruktion ska avslutas för att påbörja en ny. Detta kallas pipelining.
Vid en förgrening bestäms den följande instruktionen av den föregående, så vi kan inte göra pipelining. Vi måste antingen vänta eller förutsäga.
I ett fall med villkorad flyttning är den villkorade flyttningsinstruktionen uppdelad i flera steg, men de tidigare stegen som Fetch och Decode är inte beroende av resultatet av den föregående instruktionen; det är endast de senare stegen som behöver resultatet. Vi väntar alltså en bråkdel av en instruktions exekveringstid. Detta är anledningen till att den villkorliga flyttversionen är långsammare än grenversionen när det är lätt att förutsäga.
I boken Computer Systems: A Programmer's Perspective, second edition förklaras detta i detalj. Du kan läsa avsnitt 3.6.6 om Conditional Move Instructions, hela kapitel 4 om Processor Architecture och avsnitt 5.11.2 om en särskild behandling av Branch Prediction and Misprediction Penalties.
Ibland kan vissa moderna kompilatorer optimera vår kod till assembler med bättre prestanda, ibland kan vissa kompilatorer inte göra det (koden i fråga använder Visual Studio's native compiler). Att känna till prestandaskillnaden mellan grenar och villkorliga drag när de är oförutsägbara kan hjälpa oss att skriva kod med bättre prestanda när scenariot blir så komplext att kompilatorn inte kan optimera dem automatiskt.
