Я экспериментировал со следующим и заметил, что определенное здесь «if» без ветвления (теперь с &-!!
заменой *!!
) может ускорить код определенного узкого места почти в 2 раза на 64-битных целевых устройствах Intel с clang:
// Produces x if f is true, else 0 if f is false.
#define BRANCHLESS_IF(f,x) ((x) & -((typeof(x))!!(f)))
// Produces x if f is true, else y if f is false.
#define BRANCHLESS_IF_ELSE(f,x,y) (((x) & -((typeof(x))!!(f))) | \
((y) & -((typeof(y)) !(f))))
Обратите внимание, что f
должно быть достаточно простым выражением без побочных эффектов, чтобы компилятор мог выполнить оптимальную оптимизацию.
Производительность сильно зависит от процессора и компилятора. Производительность if без ответвлений превосходна с clang; Однако я еще не нашел случаев, когда безветвистый if/else работает быстрее.
Мой вопрос: являются ли они безопасными и портативными, как написано (имеется в виду, что они гарантированно дают правильные результаты для всех целей), и можно ли их сделать быстрее?
Пример использования ветвления if/else
Они вычисляют 64-битный минимум и максимум.
inline uint64_t uint64_min(uint64_t a, uint64_t b)
{
return BRANCHLESS_IF_ELSE((a <= b), a, b);
}
inline uint64_t uint64_max(uint64_t a, uint64_t b)
{
return BRANCHLESS_IF_ELSE((a >= b), a, b);
}
Пример использования ветвления if
Это 64-битное модульное сложение — оно вычисляет (a + b) % n
. Версия с ветвлением (не показана) ужасно страдает от сбоев предсказания ветвлений, но версия без ветвлений работает очень быстро (по крайней мере, с clang).
inline uint64_t uint64_add_mod(uint64_t a, uint64_t b, uint64_t n)
{
assert(n > 1); assert(a < n); assert(b < n);
uint64_t c = a + b - BRANCHLESS_IF((a >= n - b), n);
assert(c < n);
return c;
}
Обновление: полный конкретный рабочий пример без ветки, если
Ниже приведена полностью работающая программа C11, которая демонстрирует разницу в скорости между версиями с ветвлением и без веток простого условного оператора if
, если вы хотите попробовать его в своей системе. Программа вычисляет модульное возведение в степень, то есть (a ** b) % n
, для очень больших значений.
Для компиляции используйте в командной строке следующее:
-O3
(или любой другой высокий уровень оптимизации, который вы предпочитаете)-DNDEBUG
(чтобы отключить утверждения, для скорости)- Либо
-DBRANCHLESS=0
, либо-DBRANCHLESS=1
для указания поведения ветвления или безветвления соответственно.
В моей системе происходит следующее:
$ cc -DBRANCHLESS=0 -DNDEBUG -O3 -o powmod powmod.c && ./powmod
BRANCHLESS = 0
CPU time: 21.83 seconds
foo = 10585369126512366091
$ cc -DBRANCHLESS=1 -DNDEBUG -O3 -o powmod powmod.c && ./powmod
BRANCHLESS = 1
CPU time: 11.76 seconds
foo = 10585369126512366091
$ cc --version
Apple LLVM version 6.0 (clang-600.0.57) (based on LLVM 3.5svn)
Target: x86_64-apple-darwin14.1.0
Thread model: posix
Итак, версия без ответвлений почти в два раза быстрее версии с ответвлениями на моей системе (3,4 ГГц, Intel Core i7).
// SPEED TEST OF MODULAR MULTIPLICATION WITH BRANCHLESS CONDITIONALS
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <time.h>
#include <assert.h>
typedef uint64_t uint64;
//------------------------------------------------------------------------------
#if BRANCHLESS
// Actually branchless.
#define BRANCHLESS_IF(f,x) ((x) & -((typeof(x))!!(f)))
#define BRANCHLESS_IF_ELSE(f,x,y) (((x) & -((typeof(x))!!(f))) | \
((y) & -((typeof(y)) !(f))))
#else
// Not actually branchless, but used for comparison.
#define BRANCHLESS_IF(f,x) ((f)? (x) : 0)
#define BRANCHLESS_IF_ELSE(f,x,y) ((f)? (x) : (y))
#endif
//------------------------------------------------------------------------------
// 64-bit modular multiplication. Computes (a * b) % n without division.
static uint64 uint64_mul_mod(uint64 a, uint64 b, const uint64 n)
{
assert(n > 1); assert(a < n); assert(b < n);
if (a < b) { uint64 t = a; a = b; b = t; } // Ensure that b <= a.
uint64 c = 0;
for (; b != 0; b /= 2)
{
// This computes c = (c + a) % n if (b & 1).
c += BRANCHLESS_IF((b & 1), a - BRANCHLESS_IF((c >= n - a), n));
assert(c < n);
// This computes a = (a + a) % n.
a += a - BRANCHLESS_IF((a >= n - a), n);
assert(a < n);
}
assert(c < n);
return c;
}
//------------------------------------------------------------------------------
// 64-bit modular exponentiation. Computes (a ** b) % n using modular
// multiplication.
static
uint64 uint64_pow_mod(uint64 a, uint64 b, const uint64 n)
{
assert(n > 1); assert(a < n);
uint64 c = 1;
for (; b > 0; b /= 2)
{
if (b & 1)
c = uint64_mul_mod(c, a, n);
a = uint64_mul_mod(a, a, n);
}
assert(c < n);
return c;
}
//------------------------------------------------------------------------------
int main(const int argc, const char *const argv[const])
{
printf("BRANCHLESS = %d\n", BRANCHLESS);
clock_t clock_start = clock();
#define SHOW_RESULTS 0
uint64 foo = 0; // Used in forcing compiler not to throw away results.
uint64 n = 3, a = 1, b = 1;
const uint64 iterations = 1000000;
for (uint64 iteration = 0; iteration < iterations; iteration++)
{
uint64 c = uint64_pow_mod(a%n, b, n);
if (SHOW_RESULTS)
{
printf("(%"PRIu64" ** %"PRIu64") %% %"PRIu64" = %"PRIu64"\n",
a%n, b, n, c);
}
else
{
foo ^= c;
}
n = n * 3 + 1;
a = a * 5 + 3;
b = b * 7 + 5;
}
clock_t clock_end = clock();
double elapsed = (double)(clock_end - clock_start) / CLOCKS_PER_SEC;
printf("CPU time: %.2f seconds\n", elapsed);
printf("foo = %"PRIu64"\n", foo);
return 0;
}
Второе обновление: производительность Intel и ARM
- Тестирование на 32-разрядных целевых устройствах ARM (iPhone 3GS/4S, iPad 1/2/3/4, скомпилированное с помощью Xcode 6.1 с clang) показывает, что безответственное «если» здесь на самом деле примерно в 2–3 раза медленнее< /em>, чем троичный
?:
для модульного кода возведения в степень в этих случаях. Таким образом, кажется, что эти макросы без ветвления не являются хорошей идеей, если требуется максимальная скорость, хотя они могут быть полезны в редких случаях, когда требуется постоянная скорость. - На 64-битных ARM-целях (iPhone 6+, iPad 5) безответвительное «if» работает с той же скоростью, что и троичное
?:
— опять же, как скомпилировано Xcode 6.1 с clang. - Как для Intel, так и для ARM (составлено с помощью clang) неветвящийся if/else был примерно в два раза медленнее, чем троичный
?:
для вычисления min/max.
f ? a: b
? - person Oliver Charlesworth   schedule 08.08.2015f
оценивается дважды во второй версии, что может иметь нежелательные побочные эффекты. - person Oliver Charlesworth   schedule 08.08.2015a
илиb
равны NAN или бесконечности, могут происходить странные вещи. - person Oliver Charlesworth   schedule 08.08.2015f ? a : b
. Я видел ускорение в 2 раза. (2) Да, вы должны быть осторожны, чтобы не сделать ничего с побочными эффектами при прохожденииf
.f
должно быть простым выражением, и в этом случае оно фактически не вычисляется дважды, потому что современные компиляторы отлично справляются с устранением избыточных подвыражений. (3)a
иb
не могут бытьNaN
, потому что они предназначены только для целых чисел. - person Todd Lehman   schedule 08.08.2015(uint32_t)(x|(-x))>>31
эквивалентноx==0? 0:1
. Подробнее см. здесь. - person barak manos   schedule 08.08.2015#define MIN(a,b) (a & (signed)((a-b)>>63)) | (b & ~(signed)((a-b)>>63))
. - person barak manos   schedule 08.08.2015*!!
) на побитовое логическое и (&-!!
), и теперь он работает с одинаковой скоростью для меня с gcc, независимо от того, является ли он ветвящимся или безветвящимся. - person Todd Lehman   schedule 09.08.2015-1
, преобразованный в беззнаковый тип, всегда равен единицам. - person Jens Gustedt   schedule 10.08.2015-1
в дополнении до двух равно0xFFFFFFFFFFFFFFFF
, но в дополнении до единицы это0xFFFFFFFFFFFFFFFE
, не так ли? Мне кажется, Джин прав, и в этом случае использование&
против-1
было бы нехорошо, если бы целевая система использовала его дополнение. - person Todd Lehman   schedule 10.08.2015-1
, преобразованное в любой беззнаковый тип, всегда является максимальным значением этого беззнакового типа, а это, в свою очередь, значение со всеми-1. Это не вопрос платформы и тем более представления подписанных типов. - person Jens Gustedt   schedule 11.08.2015MIN
может переполниться, например. сMIN(INT_MAX, -1)
. Существуют неветвящиеся определения минимума, которые избегают этого вычитания (например, с использованием выраженияa < b
в качестве целочисленного значения). - person Maëlan   schedule 03.10.2019