Понимание эффективности отраслевого прогнозирования
Я попытался измерить стоимость предсказания ветвлений, я создал небольшую программу.
Создает небольшой буфер в стеке, заполняет случайным образом 0/1. Я могу установить размер буфера с N, Код многократно вызывает ветки для одного и того же 1<<N случайные числа.
Теперь я ожидал, что если 1<<N достаточно велик (например,>100), то предиктор ветвления не будет эффективным (так как он должен предсказывать> 100 случайных чисел). Тем не менее, это результаты (на машине 5820k), а N растет, программа становится медленнее:
N time
=========
8 2.2
9 2.2
10 2.2
11 2.2
12 2.3
13 4.6
14 9.5
15 11.6
16 12.7
20 12.9
Для справки, если буфер инициализируется нулями (используйте закомментированный init) время более или менее постоянно, оно колеблется в пределах 1,5-1,7 для N 8..16.
Мой вопрос: может ли предсказатель ветвления быть эффективным для предсказания такого большого количества случайных чисел? Если нет, то что здесь происходит?
(Еще несколько объяснений: код выполняет 2^32 ветви, независимо от N, Так что я ожидал, что код работает с одинаковой скоростью, независимо от Nпотому что ветвь вообще не может быть предсказана. Но похоже, что если размер буфера меньше 4096 (N<= 12), что-то делает код быстрым. Может ли предсказание ветвления быть эффективным для 4096 случайных чисел?)
Вот код:
#include <cstdint>
#include <iostream>
volatile uint64_t init[2] = { 314159165, 27182818 };
// volatile uint64_t init[2] = { 0, 0 };
volatile uint64_t one = 1;
uint64_t next(uint64_t s[2]) {
uint64_t s1 = s[0];
uint64_t s0 = s[1];
uint64_t result = s0 + s1;
s[0] = s0;
s1 ^= s1 << 23;
s[1] = s1 ^ s0 ^ (s1 >> 18) ^ (s0 >> 5);
return result;
}
int main() {
uint64_t s[2];
s[0] = init[0];
s[1] = init[1];
uint64_t sum = 0;
#if 1
const int N = 16;
unsigned char buffer[1<<N];
for (int i=0; i<1<<N; i++) buffer[i] = next(s)&1;
for (uint64_t i=0; i<uint64_t(1)<<(32-N); i++) {
for (int j=0; j<1<<N; j++) {
if (buffer[j]) {
sum += one;
}
}
}
#else
for (uint64_t i=0; i<uint64_t(1)<<32; i++) {
if (next(s)&1) {
sum += one;
}
}
#endif
std::cout<<sum<<"\n";
}
(Код также содержит небуферизованную версию, используйте #if 0, Он работает с той же скоростью, что и буферизованная версия с N=16)
Вот разборка внутреннего цикла (скомпилирована с помощью clang. Он генерирует один и тот же код для всех N между 8..16 отличается только количество циклов. Clang развернул петлю дважды)
401270: 80 3c 0c 00 cmp BYTE PTR [rsp+rcx*1],0x0
401274: 74 07 je 40127d <main+0xad>
401276: 48 03 35 e3 2d 00 00 add rsi,QWORD PTR [rip+0x2de3] # 404060 <one>
40127d: 80 7c 0c 01 00 cmp BYTE PTR [rsp+rcx*1+0x1],0x0
401282: 74 07 je 40128b <main+0xbb>
401284: 48 03 35 d5 2d 00 00 add rsi,QWORD PTR [rip+0x2dd5] # 404060 <one>
40128b: 48 83 c1 02 add rcx,0x2
40128f: 48 81 f9 00 00 01 00 cmp rcx,0x10000
401296: 75 d8 jne 401270 <main+0xa0>
1 ответ
Прогнозирование ветвей может быть таким эффективным. Как предлагает Питер Кордес, я проверил промахи с perf stat, Вот результаты:
N time cycles branch-misses (%) approx-time
===============================================================
8 2.2 9,084,889,375 34,806 ( 0.00) 2.2
9 2.2 9,212,112,830 39,725 ( 0.00) 2.2
10 2.2 9,264,903,090 2,394,253 ( 0.06) 2.2
11 2.2 9,415,103,000 8,102,360 ( 0.19) 2.2
12 2.3 9,876,827,586 27,169,271 ( 0.63) 2.3
13 4.6 19,572,398,825 486,814,972 (11.33) 4.6
14 9.5 39,813,380,461 1,473,662,853 (34.31) 9.5
15 11.6 49,079,798,916 1,915,930,302 (44.61) 11.7
16 12.7 53,216,900,532 2,113,177,105 (49.20) 12.7
20 12.9 54,317,444,104 2,149,928,923 (50.06) 12.9
Note: branch-misses (%) is calculated for 2^32 branches
Как вы можете видеть, когда N<=12Предиктор ветвей может предсказать большинство ветвей (что удивительно: предиктор веток может запомнить результат 4096 последовательных случайных ветвей!). когда N>12, ветки промахов начинают расти. В N>=16, он может только правильно прогнозировать ~50%, что означает, что он так же эффективен, как и случайные броски монет.
Требуемое время можно приблизить, посмотрев на столбец time и промахов (%): я добавил последний столбец, approx-time, Я рассчитал это следующим образом: 2.2+(12.9-2.2)*branch-misses %/100, Как вы видете, approx-time равно time (без учета ошибки округления). Таким образом, этот эффект может быть прекрасно объяснен предсказанием ветвления.
Первоначальная цель состояла в том, чтобы рассчитать, сколько циклов обходится из-за пропущенной ветви (в данном конкретном случае - как и в других случаях это число может отличаться)
(54,317,444,104-9,084,889,375)/(2,149,928,923-34,806) = 21.039 = ~21 cycles.