Ето част от код на C++, който показва много странно поведение. По някаква странна причина сортирането на данните като по чудо прави кода почти шест пъти по-бърз:
#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);
кодът се изпълнява за 11,54 секунди.Първоначално си помислих, че това може да е просто езикова или компилаторна аномалия, затова опитах с 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);
}
}
С подобен, но не толкова екстремен резултат.
Първата ми мисъл беше, че сортирането вкарва данните в кеша, но след това си помислих колко глупаво е това, защото масивът е току-що генериран.
Кодът сумира някои независими членове, така че редът не би трябвало да има значение.
Да разгледаме един железопътен възел: Image by Mecanismo, via Wikimedia Commons. Използвано под лиценза CC-By-SA 3.0. Сега, в името на аргументацията, да предположим, че това е в далечната 1800 г. - преди комуникацията на дълги разстояния или радиовръзката. Вие сте оператор на прелез и чувате, че идва влак. Нямате представа в коя посока трябва да се движи той. Спирате влака, за да попитате машиниста коя посока иска да избере. И след това настройвате стрелката по подходящ начин. Влаковете са тежки и имат голяма инерция. Затова им отнема цяла вечност да потеглят и да намалят скоростта си. Има ли по-добър начин? Отгатнете в коя посока ще се движи влакът!
Разгледайте if-изречението: На ниво процесор то е инструкция за разклоняване: Вие сте процесор и виждате разклонение. Нямате представа накъде ще тръгне. Какво ще направите? Спирате изпълнението и изчаквате, докато предишните инструкции приключат. След това продължавате по правилния път. Съвременните процесори са сложни и имат дълги конвейери. Затова им отнема цяла вечност да "загреят" и "забавят". Има ли по-добър начин? Отгатнете в коя посока ще тръгне клонът!
if (data[c] >= 128)
sum += data[c];
Забележете, че данните са равномерно разпределени между 0 и 255. Когато данните са сортирани, приблизително първата половина от итерациите няма да влезе в if-заявлението. След това всички те ще влязат в if-изречението. Това е много благоприятно за предсказващия клон, тъй като клонът последователно преминава в една и съща посока много пъти. Дори обикновен насищащ брояч ще предскаже правилно разклонението, с изключение на няколкото итерации, след като то смени посоката си. Бърза визуализация:
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)
Когато обаче данните са напълно случайни, предсказателят на разклонения се оказва безполезен, защото не може да предсказва случайни данни. По този начин вероятно ще има около 50 % грешно предсказване (не по-добро от случайното отгатване).
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)
И така, какво може да се направи? Ако компилаторът не'е в състояние да оптимизира разклонението в условен ход, можете да опитате някои хакове, ако сте готови да пожертвате четливостта в полза на производителността. Заменете:
if (data[c] >= 128)
sum += data[c];
с:
int t = (data[c] - 128) >> 31;
sum += ~t & data[c];
Това елиминира разклонението и го замества с някои битови операции.
(Имайте предвид, че този хак не е строго еквивалентен на оригиналната if-заявка. Но в този случай тя е валидна за всички входни стойности на data[]
.)
Образец: Core i7 920 @ 3,5 GHz
C++ - Visual Studio 2010 - версия x64
// 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
Наблюдения:
Актуализация:
-O3
или -ftree-vectorize
на x64 е в състояние да генерира условен ход. Така че няма разлика между сортираните и несортираните данни - и двете са бързи./Ox
.Предвиждане на клона.
При сортиран масив условието data[c] >= 128
първо е фалшиво
за поредица от стойности, а след това става истина
за всички следващи стойности. Това е лесно да се предвиди. При несортиран масив плащате за разходите за разклоняване.
Причината, поради която производителността се подобрява драстично, когато данните са сортирани, е, че се премахва наказанието за предсказване на разклонения, както е обяснено прекрасно в Mysticial's answer.
Сега, ако разгледаме кода
if (data[c] >= 128)
sum += data[c];
можем да открием, че смисълът на този конкретен клон if... else...
е да добави нещо, когато дадено условие е изпълнено. Този тип разклонение може лесно да се трансформира в условна инструкция за преместване, която би била компилирана в условна инструкция за преместване: cmovl
, в система x86
. Разклонението и по този начин потенциалното наказание за предсказване на разклонението се премахва.
В C
, а следователно и в C++
, операторът, който би се компилирал директно (без оптимизация) в инструкция за условно преместване в x86
, е тройният оператор ... ? ... : ...
. Затова преписваме горния оператор в еквивалентен:
sum += data[c] >=128 ? data[c] : 0;
Като запазваме четимостта, можем да проверим коефициента на ускорение.
На процесор Intel Core i7-2600K @ 3,4 GHz и Visual Studio 2010 Release Mode бенчмаркът е (форматът е копиран от 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
Резултатът е стабилен при многократни тестове. Получаваме голямо ускорение, когато резултатът от разклонението е непредсказуем, но страдаме малко, когато е предсказуем. Всъщност, когато използваме условен ход, производителността е една и съща, независимо от модела на данните.
Сега нека'разгледаме по-отблизо, като изследваме генерираното от тях асембли x86
. За по-голяма простота използваме две функции max1
и max2
.
max1
използва условното разклонение if... else ...
:
int max1(int a, int b) {
if (a > b)
return a;
else
return b;
}
max2
използва тройния оператор ... ? ... : ...
:
int max2(int a, int b) {
return a > b ? a : b;
}
На машина x86-64, `GCC -S`` генерира асемблито по-долу.
: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
използва много по-малко код благодарение на използването на инструкцията cmovge
. Но истинската печалба е, че max2
не включва скокове на разклонение, jmp
, които биха имали значително наказание за производителността, ако предсказаният резултат не е верен.
И така, защо условният ход се представя по-добре?
В един типичен процесор x86
изпълнението на една инструкция е разделено на няколко етапа. Приблизително имаме различен хардуер за работа с различните етапи. Така че не е необходимо да чакаме една инструкция да приключи, за да започнем нова. Това се нарича pipelining.
В случай на разклонение следващата инструкция се определя от предходната, така че не можем да направим pipelining. Трябва или да изчакаме, или да предвидим.
В случай на условно преместване изпълнението на условната инструкция за преместване е разделено на няколко етапа, но по-ранните етапи като Fetch
и Decode
не зависят от резултата на предишната инструкция; само последните етапи се нуждаят от резултата. По този начин изчакваме част от времето за изпълнение на една инструкция'. Ето защо версията с условен ход е по-бавна от разклонението, когато предсказването е лесно.
В книгата Computer Systems: A Programmer's Perspective, second edition това е обяснено подробно. Можете да проверите раздел 3.6.6 за Инструкции за условно преместване, цялата глава 4 за Архитектура на процесора и раздел 5.11.2 за специално разглеждане на Предоставяне на разклонението и наказания за неправилно предвиждане.
Понякога някои съвременни компилатори могат да оптимизират нашия код на асемблер с по-добра производителност, а понякога някои компилатори не могат (въпросният код използва родния компилатор на Visual Studio'). Познаването на разликата в производителността между разклонение и условен ход при непредсказуемост може да ни помогне да напишем код с по-добра производителност, когато сценарият стане толкова сложен, че компилаторът не може да ги оптимизира автоматично.