Почему GCC не оптимизирует этот набор ветвлений и условных выражений так сильно, как мог бы?

Question

Следующие три фрагмента кода достигают абсолютно одинакового эффекта. Тем не менее, при компиляции с -O3 в GCC 4.5.2 время для многих итераций меняется весьма заметно.

1 - нормальное ветвление с использованием нескольких условий, лучшее время 1,0:

// a, b, c, d are set to random values 0-255 before each iteration.
if (a < 16 or b < 32 or c < 64 or d < 128) result += a+b+c+d;

2 - Ветвление, вручную с использованием побитового или для проверки условий, наилучшее время 0,92:

if (a < 16 | b < 32 | c < 64 | d < 128) result += a+b+c+d;

3 - наконец, получить тот же результат без ветки, лучшее время 0,85:

result += (a+b+c+d) * (a < 16 | b < 32 | c < 64 | d < 128);

Указанные выше значения времени являются лучшими для каждого метода, когда он выполняется как внутренний цикл созданной мной программы тестирования производительности. random() высевается одинаково перед каждым прогоном.

До того, как я сделал этот тест, я предполагал, что GCC оптимизирует различия. Особенно второй пример заставляет меня почесать голову. Кто-нибудь может объяснить, почему GCC не превращает подобный код в эквивалентный более быстрый код?

РЕДАКТИРОВАТЬ: Исправлены некоторые ошибки, а также прояснилось, что случайные числа создаются независимо и используются, чтобы не быть оптимизированы. Они всегда были в исходном бенчмарке, я просто испортил код, который надел здесь.

Вот пример действительной тестовой функции:

boost::random::mt19937 rng;
boost::random::uniform_int_distribution<> ranchar(0, 255);

double quadruple_or(uint64_t runs) {
  uint64_t result = 0;
  rng.seed(0);

  boost::chrono::high_resolution_clock::time_point start = 
    boost::chrono::high_resolution_clock::now();
  for (; runs; runs--) {
    int a = ranchar(rng);
    int b = ranchar(rng);
    int c = ranchar(rng);
    int d = ranchar(rng);
    if (a < 16 or b < 32 or c < 64 or d < 128) result += a;
    if (d > 16 or c > 32 or b > 64 or a > 128) result += b;
    if (a < 96 or b < 53 or c < 199 or d < 177) result += c;
    if (d > 66 or c > 35 or b > 99 or a > 77) result += d;
  }

  // Force gcc to not optimize away result.
  std::cout << "Result check " << result << std::endl;
  boost::chrono::duration<double> sec = 
    boost::chrono::high_resolution_clock::now() - start;
  return sec.count();
}

Полный тест можно найти здесь .

Answer 1

ОП несколько изменился со времени моего первоначального ответа.Позвольте мне попытаться вернуться здесь.

В случае 1, из-за короткого замыкания or, я ожидаю, что компилятор сгенерирует четыре секции кода сравнения-затем-ветви.Очевидно, что ответвления могут быть довольно дорогими, особенно если они не идут по предсказанному пути.

В случае 2 компилятор может решить выполнить все четыре сравнения, преобразовать их в результаты bool 0/1 и затем побитировать or все четыре штуки вместе, затем делаем одну (дополнительную) ветку.Это торгует, возможно, большим количеством сравнений для, возможно, меньшего количества ветвей.Похоже, что уменьшение числа ветвей действительно улучшает производительность.

В случае 3 все работает почти так же, как 2, за исключением того, что в самом конце еще одна ветвь может быть устранена путем явного указания компилятору: «Я знаюрезультат будет равен нулю или единице, поэтому просто умножьте значение слева на это значение ».Умножение очевидно происходит быстрее, чем соответствующая ветка на вашем оборудовании.Это отличается от второго примера, где компилятор не знает диапазон возможных выходных данных от побитового or, поэтому он должен предположить, что это может быть любое целое число, и вместо этого должен выполнить сравнение и переход.

Оригинальный ответ для истории: Первый случай функционально отличается от второго и третьего, если random имеет побочные эффекты (что было бы у обычного PRNG), поэтому вполне понятно, что компилятор может оптимизироватьих по-разному.В частности, первый случай будет вызывать random столько раз, сколько необходимо для прохождения проверки, в то время как в двух других случаях random всегда будет вызываться четыре раза.Это (при условии, что random действительно является состоянием) приведет к тому, что будущие случайные числа будут другими.

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

Answer 2

Вы всегда можете попробовать оптимизировать ветку и умножить. Вместо:

if (test) result+= blah;

или

result+= blah*(test);

Вы можете сделать:

result+= blah&(-(test));

Если test ложно, -false==0 и (blah&0)==0. Если test истинно, -true==~0 и (blah&~0)==blah. Возможно, вам придется поиграть с test как !!test, чтобы обеспечить true==1.

Answer 3

С помощью логических операторов код будет разветвляться и ранний выход. Битовые операторы всегда выполняют всю работу.

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

Невозможно оптимизировать random(), потому что эта функция не чистая (идемпотентная).

Answer 4

На моей машине (Intel E5503) с gcc 4.5.3 я нахожу, что версия 1, как правило, самая быстрая, хотя разница находится в пределах шума измерения (f3 самый медленный, хотя всего на 2% медленнее, чем f1) .

Как вы измеряете время? Возможно, вы обнаружите, что различия, которые вы видите, связаны скорее с фактической разницей в создаваемом коде.