Блог

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

Это создает небольшой буфер в стеке, заполняемый случайным значением 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 случайных чисел?)

Вот код:

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

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)amp;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)amp;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>
  

Предсказание ветвлений может быть таким эффективным. Как предлагает Питер Кордес, я проверил ошибки в ветвлении с помощью 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.