Ловушка профилирования

Началось всё с того, что я смотрел ролик про оптимизацию и увидел знакомый по книжкам пример кода, который демонстрирует важность успеха предсказателя ветвлений (branch predictor). Суть в том, что в функции есть ветвление и если предсказатель предскажет неверно, то будет потрачено множество тактов процессора впустую. Оптимизированная версия функции всегда рассчитывает два результата, но не имеет ветвлений.

Так вот, делать было нечего и я решил проверить как это работает на самом деле.
Для этого я взял google benchmark и составил два одинаковых теста на каждую из функций.
BM_GetProduct1 - функция с ветвлением, BM_GetProduct2 - без ветвлений (оптимизированная).

Когда я запустил программу, результаты меня сильно удивили.

Первая и (предположительно) медленная версия уверенно выигрывает у "оптимизированной" на массиве данных до 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% случаев.
Но почему же первый вариант выигрывает на малых данных, а потом резко сдаёт?

Напрашивается вывод, что это как-то зависит от длины вектора... но ведь оба варианта получают одинаковые данные...
Может быть есть накладные расходы, которые не растут линейно?

Давайте попробуем отсортировать вектор и повторить тест!

Первый вариант работает не хуже, а то и лучше "оптимизированного" варианта. Сначала функция обрабатывает все отрицательные значения (ветка 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;
    }
  }
}

А вот и результаты:

Совсем другое дело! А я уже было подумал, что для маленьких данный выгоднее вариант с ветвлением! Версия без ветвления определённо работает быстрее на данных любого размера, при условии, что данные случайны.

Приведу сравнительную таблицу, насколько могут обманывать некорректно выполненные замеры:

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