Началось всё с того, что я смотрел ролик про оптимизацию и увидел знакомый по книжкам пример кода, который демонстрирует важность успеха предсказателя ветвлений (branch predictor). Суть в том, что в функции есть ветвление и если предсказатель предскажет неверно, то будет потрачено множество тактов процессора впустую. Оптимизированная версия функции всегда рассчитывает два результата, но не имеет ветвлений.
Так вот, делать было нечего и я решил проверить как это работает на самом деле.
Для этого я взял google benchmark и составил два одинаковых теста на каждую из функций.
BM_GetProduct1 - функция с ветвлением, BM_GetProduct2 - без ветвлений (оптимизированная).
Когда я запустил программу, результаты меня сильно удивили.
---------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------
BM_GetProduct1/16 9.12 ns 9.11 ns 62193800
BM_GetProduct1/64 36.6 ns 36.5 ns 19171034
BM_GetProduct1/512 418 ns 417 ns 1682832
BM_GetProduct1/4096 3605 ns 3598 ns 196197
BM_GetProduct1/32768 104858 ns 104677 ns 6754
BM_GetProduct1/65536 211673 ns 211332 ns 3209
BM_GetProduct2/16 9.22 ns 9.21 ns 75412476
BM_GetProduct2/64 44.7 ns 44.7 ns 15766219
BM_GetProduct2/512 437 ns 437 ns 1613444
BM_GetProduct2/4096 3592 ns 3587 ns 195040
BM_GetProduct2/32768 28929 ns 28882 ns 24380
BM_GetProduct2/65536 57684 ns 57610 ns 12128
Первая и (предположительно) медленная версия уверенно выигрывает у "оптимизированной" на массиве данных до 4096 элементов включительно! Но почему?
Давайте разбираться!
Код функции с ветвлением:
double get_product1(std::span<const double> input, double threshold) {
double p = 1.0;
for (auto i : input) {
if (i < threshold) {
p *= 2 * i;
} else {
p *= 1.5 * i;
}
}
return p;
}
Функция без ветвления всегда рассчитывает два результата (и это её недостаток), но зато конвейер процессора не ломается — нет условного перехода, который нужно предсказывать.
double get_product2(std::span<const double> input, double threshold) {
double p = 1.0;
for (auto i : input) {
std::array arr = {1.5 * i, 2.0 * i};
p *= arr[i < threshold];
}
return p;
}
Сами тесты выглядят одинаково для обеих функций, так что я приведу только один вариант:
static void BM_GetProduct1(benchmark::State &state) {
const auto size = state.range(0);
auto data = generateData(size);
double p = 0.0;
for (auto _ : state) {
benchmark::ClobberMemory();
benchmark::DoNotOptimize(p += get_product1(data, 0.0));
}
}
BENCHMARK(BM_GetProduct1)->Range(16, 16 * 4096);
Данные генерируются случайным образом: половина данных больше нуля, а половина - меньше.
std::vector<double> generateData(int size) {
std::random_device rd;
std::mt19937_64 gen(rd());
std::uniform_real_distribution<double> dist(-1000.0, 1000.0);
std::vector<double> data;
data.resize(size);
for (auto &d : data) {
d = dist(gen);
}
return data;
}
Итак, get_product1 получает набор случайных данных и так как они случайные, то предсказатель переходов угадывает лишь в 50% случаев.
Но почему же первый вариант выигрывает на малых данных, а потом резко сдаёт?
Напрашивается вывод, что это как-то зависит от длины вектора... но ведь оба варианта получают одинаковые данные...
Может быть есть накладные расходы, которые не растут линейно?
Давайте попробуем отсортировать вектор и повторить тест!
---------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------
BM_GetProduct1/16 8.96 ns 8.94 ns 80669588
BM_GetProduct1/64 35.8 ns 35.7 ns 19709667
BM_GetProduct1/512 422 ns 422 ns 1388010
BM_GetProduct1/4096 3563 ns 3559 ns 196867
BM_GetProduct1/32768 28644 ns 28614 ns 24503
BM_GetProduct1/65536 57497 ns 57432 ns 12093
BM_GetProduct2/16 9.04 ns 9.03 ns 76644990
BM_GetProduct2/64 44.4 ns 44.3 ns 15828673
BM_GetProduct2/512 433 ns 433 ns 1613180
BM_GetProduct2/4096 3578 ns 3574 ns 196333
BM_GetProduct2/32768 28688 ns 28650 ns 24450
BM_GetProduct2/65536 57435 ns 57345 ns 12213
Первый вариант работает не хуже, а то и лучше "оптимизированного" варианта. Сначала функция обрабатывает все отрицательные значения (ветка if), потом все положительные (ветка else), и предсказатель ошибается только один раз — в точке перехода.
Но почему же в случае неотсортированных и случайных данных get_product1 всё равно побеждает при размере данных меньше 4К?
Разгадка
Вспомним, как устроен предсказатель переходов. У него есть память, в которую он запоминает предыдущие переходы и выявляет паттерны.
Например, что всегда условие истинное или, например, шаблон истинно-истинно-ложно.
Но в нашем случае у нас точно нет паттернов, так как данные случайные!
Или всё-таки паттерны есть?
Ответ заключается в том, что google benchmark производит множество повторений вызовов get_product с одними и теми же данными, так что предсказатель переходов эти просто выучивает и они данные перестают быть случайными! Когда мы делаем очередную итерацию, он "узнаёт" эту последовательность и начинает выбирать правильную ветку исходя из своего "опыта". Но если последовательность оказывается слишком длинной, то он не может её запомнить и данные опять становятся для него случайными.
Чтобы проверить и убедиться, что эта гипотеза верна, сделаем так, чтобы короткие последовательности не повторялись для новой итерации:
static void BM_GetProduct1(benchmark::State &state) {
auto data = generateData(max_data_size);
const auto size = state.range(0);
std::vector<std::span<double>> sets;
for (int i = 0; i + size <= max_data_size; i += size) {
sets.push_back(std::span(&data[i], size));
}
double p = 0.0;
int i = 0;
for (auto _ : state) {
benchmark::ClobberMemory();
benchmark::DoNotOptimize(p += get_product1(sets[i], 0.0));
if (++i >= sets.size()) {
i = 0;
}
}
}
А вот и результаты:
---------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------
BM_GetProduct1/16 58.1 ns 57.9 ns 11410584
BM_GetProduct1/64 214 ns 214 ns 3277196
BM_GetProduct1/512 1649 ns 1646 ns 419308
BM_GetProduct1/4096 13133 ns 13118 ns 52947
BM_GetProduct1/32768 104506 ns 104381 ns 6656
BM_GetProduct1/65536 208442 ns 208213 ns 3307
BM_GetProduct2/16 11.0 ns 11.0 ns 63463067
BM_GetProduct2/64 46.4 ns 46.3 ns 15161975
BM_GetProduct2/512 438 ns 438 ns 1608315
BM_GetProduct2/4096 3589 ns 3584 ns 195693
BM_GetProduct2/32768 28825 ns 28785 ns 24373
BM_GetProduct2/65536 57613 ns 57544 ns 12100
Совсем другое дело! А я уже было подумал, что для маленьких данный выгоднее вариант с ветвлением! Версия без ветвления определённо работает быстрее на данных любого размера, при условии, что данные случайны.
Приведу сравнительную таблицу, насколько могут обманывать некорректно выполненные замеры:
Размер | казалось | на самом деле | Ошибка |
|---|---|---|---|
16 | 9.12 ns | 58.1 ns | 6.4x |
64 | 36.6 ns | 214 ns | 5.8x |
512 | 418 ns | 1649 ns | 3.9x |
4096 | 3605 ns | 13133 ns | 3.6x |
32768 | 104858 ns | 104506 ns | ~1x |
65536 | 211673 ns | 208442 ns | ~1x |
Итак, с результатами замеров надо быть крайне осторожным и не спешить с выводами — особенности тестирования могут значительно исказить картину.
