Понимание эффективности отраслевого прогнозирования

Question

Я пытался измерить стоимость предсказания ветвлений, я создал небольшую программу.

Создает небольшой буфер в стеке, заполняется случайным образом 0/1. Я могу установить размер буфера с помощью N. Код многократно вызывает ответвления для одинаковых 1<<N случайных чисел.

Теперь я ожидал, что если 1<<N достаточно велико (например,> 100), то предсказатель ветвления не будет эффективным (так как он должен предсказывать> 100 случайных чисел). Тем не менее, это результаты (на машине 5820 КБ): с ростом 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 случайных чисел?) </p>

Вот код:

#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>

Answer 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%, что означает, что он так же эффективен, как случайные броски монет.

Требуемое время можно приблизить, посмотрев на столбец времени и пропущенных переходов (%): я добавил последний столбец, 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.