Блог

Следующие три фрагмента кода достигают точно такого же эффекта. Тем не менее, при компиляции с -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 оптимизирует различия. Особенно 2-й пример заставляет меня почесать голову. Кто-нибудь может объяснить, почему 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();
}
  

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

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

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

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

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

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

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

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

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

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

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

 if (test) result = blah;
  

или

 result = blah*(test);
  

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

 result = blahamp;(-(test));
  

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