Безопасно ли переводить __builtin_expect во встроенную функцию?

Оставайтесь с проверенными и надежными макросами, даже если мы все знаем, что макросов вообще следует избегать. Функции inline просто не работают. В качестве альтернативы — особенно если вы используете GCC — вообще забудьте __builtin_expect и вместо этого используйте оптимизацию на основе профиля (PGO) с фактическими данными профилирования.

__builtin_expect совершенно особенный в том, что он на самом деле ничего не "делает", а просто намекает компилятору, какая ветвь, скорее всего, будет выбрана. Если вы используете встроенный в контексте, который не является условием ветвления, компилятору придется распространять эту информацию вместе со значением. Интуитивно я ожидал, что это произойдет. Интересно, что документация GCC и Clang не очень подробно говорит об этом. Однако мои эксперименты показывают, что Clang явно не распространяет эту информацию. Что касается GCC, мне еще нужно найти программу, где она действительно обращает внимание на встроенную, поэтому я не могу сказать наверняка. (Или, другими словами, это все равно не имеет значения.)

Я протестировал следующую функцию.

std::size_t
do_computation(std::vector<int>& numbers,
               const int base_threshold,
               const int margin,
               std::mt19937& rndeng,
               std::size_t *const hitsptr)
{
  assert(base_threshold >= margin && base_threshold <= INT_MAX - margin);
  assert(margin > 0);
  benchmark::clobber_memory(numbers.data());
  const auto jitter = make_jitter(margin - 1, rndeng);
  const auto threshold = base_threshold + jitter;
  auto count = std::size_t {};
  for (auto& x : numbers)
    {
      if (LIKELY(x > threshold))
        {
          ++count;
        }
      else
        {
          x += (1 - (x & 2));
        }
    }
  benchmark::clobber_memory(numbers.data());
  // My benchmarking framework swallows the return value so this trick with
  // the pointer was needed to get out the result.  It should have no effect
  // on the measurement.
  if (hitsptr != nullptr)
    *hitsptr += count;
  return count;
}

make_jitter просто returns случайное целое число в диапазоне [m, m], где m — его первый аргумент.

int
make_jitter(const int margin, std::mt19937& rndeng)
{
  auto rnddist = std::uniform_int_distribution<int> {-margin, margin};
  return rnddist(rndeng);
}

benchmark::clobber_memory — это no-op, который запрещает компилятору оптимизировать модификации векторных данных. Это реализовано так.

inline void
clobber_memory(void *const p) noexcept
{
  asm volatile ("" : : "rm"(p) : "memory");
}

Объявление do_computation было снабжено аннотацией __attribute__ ((hot)). Оказалось, что это влияет на то, сколько оптимизаций компилятор применяет много.

Код для do_computation был разработан таким образом, чтобы обе ветви имели сопоставимую стоимость, что несколько увеличивало стоимость в случае, когда ожидания не оправдались. Также было удостоверено, что компилятор не будет генерировать векторизованный цикл, для которого ветвление не имеет значения.

Для эталона вектор numbers из 100000000 случайных целых чисел из диапазона [0, INT_MAX] и случайное base_threshold из интервала [0, INT_MAX margin] (с margin установленным на 100) был сгенерирован с недетерминированным псевдо генератор случайных чисел. do_computation(numbers, base_threshold, margin, …) (составленный в отдельной единице трансляции) вызывался четыре раза и измерялось время выполнения для каждого прогона. Результат первого запуска был отброшен, чтобы устранить эффекты холодного кэширования. Среднее значение и стандартное отклонение оставшихся запусков были нанесены на график в зависимости от частоты попаданий (относительная частота, с которой аннотация LIKELY была правильной). «Дрожание» было добавлено для того, чтобы результаты четырех прогонов не были одинаковыми (иначе я бы боялся слишком умных компиляторов), при этом сохраняя по существу фиксированную частоту попаданий. Таким образом было собрано 100 точек данных.

Я скомпилировал три разные версии программы с GCC 5.3.0 и Clang 3.7.0, передав им флаги -DNDEBUG, -O3 и -std=c++14. Версии отличаются только способом определения LIKELY.

// 1st version
#define LIKELY(X) static_cast<bool>(X)

// 2nd version
#define LIKELY(X) __builtin_expect(static_cast<bool>(X), true)

// 3rd version
inline bool
LIKELY(const bool x) noexcept
{
  return __builtin_expect(x, true);
}

Хотя концептуально это три разные версии, я сравнил 1^st со 2^nd и 1^st с 3^rd. Таким образом, данные для 1^st собирались дважды. 2^nd и 3^rd упоминаются на графиках как «намеченные».

Горизонтальная ось следующих графиков показывает частоту совпадений для аннотации LIKELY, а вертикальная ось показывает среднее время ЦП на итерацию цикла.

Вот график для 1^st и 2^nd.

Как видите, GCC эффективно игнорирует подсказку, создавая одинаково эффективный код независимо от того, была дана подсказка или нет. Clang, с другой стороны, явно обращает внимание на подсказку. Если частота попаданий падает (т. е. подсказка была неправильной), код наказывается, но при высоких показателях попаданий (т. е. подсказка была хорошей) код превосходит код, сгенерированный GCC.

В случае, если вас интересует характер кривой в форме холма: это аппаратный предсказатель ветвления в действии! Это не имеет никакого отношения к компилятору. Также обратите внимание, что этот эффект полностью затмевает эффекты __builtin_expect, что может быть причиной того, что не следует слишком беспокоиться об этом.

Напротив, вот график для 1^st и 3^rd.

Оба компилятора производят код, который по существу работает одинаково. Для GCC это мало что говорит, но что касается Clang, похоже, что __builtin_expect не принимается во внимание при включении в функцию, что делает его слабым по сравнению с GCC для всех коэффициентов попаданий.

Итак, в заключение, не используйте функции в качестве оберток. Если макрос написан правильно, он не опасен. (Помимо загрязнения пространства имен.) __builtin_expect уже ведет себя (по крайней мере, в том, что касается оценки ее аргументов) как функция. Обёртка вызова функции в макрос не оказывает неожиданного влияния на оценку её аргумента.

Я понимаю, что это был не ваш вопрос, поэтому я буду краток, но в целом предпочтительнее собирать фактические данные профилирования, чем угадывать вероятные ветки вручную. Данные будут более точными, и GCC будет уделять им больше внимания.

Не гарантируется, что компилятор встраивает встроенную функцию. Большинство современных компиляторов рассматривают ключевое слово inline только как подсказку. Если вы форсируете встраивание, используя __attribute__((always_inline)) с GCC (или __forceinline с MSVC), не имеет значения, используете ли вы встроенную функцию или макрос (но даже __forceinline может не работать). В противном случае возможно, что функция не будет встроена. Например, GCC не встраивает функции с отключенной оптимизацией. В этом случае результирующий код будет значительно медленнее. Я бы придерживался макроса, чтобы быть в безопасности.