Hier is een stukje C++ code dat zeer eigenaardig gedrag vertoont. Om een of andere vreemde reden maakt het sorteren van de gegevens de code op miraculeuze wijze bijna zes keer sneller:
#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;
}
std::sort(data, data + arraySize);
, loopt de code in 11.54 seconden.In eerste instantie dacht ik dat dit misschien gewoon een taal of compiler afwijking was, dus probeerde ik 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);
}
}
Met een gelijkaardig, maar minder extreem resultaat.
Mijn eerste gedachte was dat sorteren de gegevens in de cache brengt, maar toen bedacht ik hoe dom dat was omdat de array net gegenereerd was.
De code telt een aantal onafhankelijke termen bij elkaar op, dus de volgorde zou er niet toe moeten doen.
Beschouw een spoorwegknooppunt: Afbeelding door Mecanismo, via Wikimedia Commons. Gebruikt onder de CC-By-SA 3.0 licentie. Veronderstel nu eens dat dit in de jaren 1800 is - vóór langeafstands- of radiocommunicatie. Je bent de operator van een knooppunt en je hoort een trein aankomen. Je hebt geen idee welke kant hij op moet. Je stopt de trein om de machinist te vragen welke richting hij op wil. En dan zet je de wissel op de juiste manier. *Treinen zijn zwaar en hebben veel traagheid. Dus duurt het een eeuwigheid om ze op te starten en af te remmen. Is er een betere manier? Je raadt welke kant de trein op gaat!
Overweeg een if-statement: Op processor niveau is het een branch instructie: Je bent een processor en je ziet een aftakking. Je hebt geen idee welke kant het op zal gaan. Wat doe je dan? Je stopt de uitvoering en wacht tot de vorige instructies zijn voltooid. Dan ga je verder op de juiste weg. *Moderne processoren zijn ingewikkeld en hebben lange pijplijnen. Dus duurt het een eeuwigheid om op te warmen en af te remmen. Is er een betere manier? Je raadt welke richting de tak zal gaan!
if (data[c] >= 128)
sum += data[c];
Merk op dat de gegevens gelijkmatig verdeeld zijn tussen 0 en 255. Wanneer de data gesorteerd is, zal ruwweg de eerste helft van de iteraties niet in het if-statement komen. Daarna zullen ze allemaal het if-statement binnengaan. Dit is zeer vriendelijk voor de vertakkingsvoorspeller, omdat de vertakking opeenvolgend vele malen in dezelfde richting gaat. Zelfs een eenvoudige verzadigende teller zal de tak correct voorspellen, behalve voor de paar iteraties nadat hij van richting verandert. Snelle visualisatie:
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)
Wanneer de gegevens echter volledig willekeurig zijn, is de takvoorspeller nutteloos, omdat hij geen willekeurige gegevens kan voorspellen. Dus zal er waarschijnlijk ongeveer 50% misvoorspelling zijn (niet beter dan willekeurig raden).
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)
Dus wat kan er gedaan worden? Als de compiler niet in staat is'om de tak te optimaliseren in een voorwaardelijke zet, kun je enkele hacks proberen als je bereid bent om leesbaarheid op te offeren voor prestaties. Vervangen:
if (data[c] >= 128)
sum += data[c];
door:
int t = (data[c] - 128) >> 31;
sum += ~t & data[c];
Dit elimineert de vertakking en vervangt deze door een aantal bitwise operaties.
(Merk op dat deze hack niet strikt gelijkwaardig is aan het originele if-statement. Maar in dit geval, is het geldig voor alle invoerwaarden van data[]
.)
Benchmarks: Core i7 920 @ 3,5 GHz
C++ - Visual Studio 2010 - x64 Versie
// Branch - Random
seconds = 11.777
// Branch - Sorted
seconds = 2.352
// Branchless - Random
seconds = 2.564
// Branchless - Sorted
seconds = 2.587
Java - 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.186068823
Opmerkingen:
Update:
-O3
of -ftree-vectorize
op x64 is in staat om een voorwaardelijke zet te genereren. Er is dus geen verschil tussen de gesorteerde en ongesorteerde data - beide zijn snel./Ox
.Branch prediction.
Bij een gesorteerde array is de voorwaarde data[c] >= 128
eerst valse
voor een reeks waarden, en wordt dan true
voor alle latere waarden. Dat'is gemakkelijk te voorspellen. Bij een ongesorteerde array betaal je voor de vertakkingskosten.
De reden waarom de prestaties drastisch verbeteren wanneer de gegevens gesorteerd zijn, is dat de vertakkingsvoorspellingsboete wordt opgeheven, zoals prachtig uitgelegd in Mysticial's antwoord.
Nu, als we kijken naar de code
if (data[c] >= 128)
sum += data[c];
kunnen we zien dat de betekenis van deze specifieke if... else...
tak is om iets toe te voegen wanneer aan een voorwaarde is voldaan. Dit type tak kan gemakkelijk worden omgezet in een voorwaardelijke zet instructie, die zou worden gecompileerd in een voorwaardelijke zet instructie: cmovl
, in een x86
systeem. De branch en dus de potentiële branch prediction penalty wordt verwijderd.
In C
, dus C++
, is het statement, dat direct (zonder enige optimalisatie) zou compileren tot de voorwaardelijke zet-instructie in x86
, de ternaire operator ... ? ... : ...
. Dus we herschrijven het bovenstaande statement in een equivalent statement:
sum += data[c] >=128 ? data[c] : 0;
Met behoud van leesbaarheid, kunnen we de versnellingsfactor controleren.
Op een Intel Core i7-2600K @ 3.4 GHz en Visual Studio 2010 Release Mode, is de benchmark (formaat gekopieerd van 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
Het resultaat is robuust in meerdere tests. We krijgen een grote versnelling als het vertakkingsresultaat onvoorspelbaar is, maar we lijden een beetje als het voorspelbaar is. In feite, wanneer we een voorwaardelijke zet gebruiken, is de prestatie hetzelfde, ongeacht het datapatroon.
Laten we nu eens wat nauwkeuriger kijken door de x86
assembly die ze genereren te onderzoeken. Voor de eenvoud gebruiken we twee functies max1
en max2
.
max1
gebruikt de voorwaardelijke vertakking if... else ...
:
int max1(int a, int b) {
if (a > b)
return a;
else
return b;
}
max2
gebruikt de ternaire operator ... ? ... : ...
:
int max2(int a, int b) {
return a > b ? a : b;
}
Op een x86-64 machine, genereert GCC -S
de onderstaande assembly.
: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
gebruikt veel minder code door het gebruik van de instructie cmovge
. Maar de echte winst is dat max2
geen vertakkingssprongen, jmp
, nodig heeft, die een aanzienlijk prestatieverlies zouden hebben als het voorspelde resultaat niet goed is.
Dus waarom presteert een voorwaardelijke zet beter?
In een typische x86
processor, is de uitvoering van een instructie verdeeld in verschillende stappen. Ruwweg, hebben we verschillende hardware om de verschillende stadia te behandelen. We hoeven dus niet te wachten tot een instructie klaar is om een nieuwe te starten. Dit wordt pipelining genoemd.
In het geval van een vertakking, wordt de volgende instructie bepaald door de vorige, dus kunnen we niet aan pipelining doen. We moeten of wachten of voorspellen.
In het geval van een voorwaardelijke zet, is de uitvoering van de voorwaardelijke zet-instructie verdeeld in verschillende stappen, maar de eerdere stappen zoals Fetch
en Decode
zijn niet afhankelijk van het resultaat van de vorige instructie; alleen de latere stappen hebben het resultaat nodig. Zo wachten we een fractie van de uitvoeringstijd van één instructie's. Dit is de reden waarom de voorwaardelijke zet-versie langzamer is dan de tak wanneer voorspelling gemakkelijk is.
Het boek Computer Systems: A Programmer's Perspective, second edition legt dit in detail uit. Je kunt Sectie 3.6.6 bekijken voor Conditional Move Instructies, heel Hoofdstuk 4 voor Processor Architectuur, en Sectie 5.11.2 voor een speciale behandeling voor Branch Prediction and Misprediction Penalties.
Soms kunnen sommige moderne compilers onze code optimaliseren naar assembly met betere prestaties, soms kunnen sommige compilers dat niet's (de code in kwestie gebruikt Visual Studio's native compiler). Weten wat het verschil in prestaties is tussen vertakkingen en voorwaardelijke verplaatsingen wanneer ze onvoorspelbaar zijn, kan ons helpen code te schrijven met betere prestaties wanneer het scenario zo complex wordt dat de compiler ze niet automatisch kan optimaliseren.