Безветвевой код, который отображает ноль, отрицательный и положительный значения в 0, 1, 2.
https://stackoverflow.com/questions/1610836
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Напишите функцию без ветвей, которая возвращает 0, 1 или 2, если разница между двумя целыми числами со знаком равна нулю, отрицательному или положительному значению.
Вот версия с ветвлением:
int Compare(int x, int y)
{
int diff = x - y;
if (diff == 0)
return 0;
else if (diff < 0)
return 1;
else
return 2;
}
Вот версия, которая может быть быстрее в зависимости от компилятора и процессора:
int Compare(int x, int y)
{
int diff = x - y;
return diff == 0 ? 0 : (diff < 0 ? 1 : 2);
}
Можете ли вы придумать более быстрый вариант без ветвей?
КРАТКОЕ СОДЕРЖАНИЕ
10 протестированных мной решений имели одинаковую производительность.Фактические числа и победитель варьировались в зависимости от компилятора (icc/gcc), параметров компилятора (например, -O3, -march=nocona, -fast, -xHost) и компьютера. Решение Canon показало хорошие результаты во многих тестах., но опять же преимущество в производительности было небольшим.Меня удивило, что в некоторых случаях некоторые решения работали медленнее, чем наивное решение с ветвями.
Решение
int Compare(int x, int y) {
return (x < y) + (y < x) << 1;
}
Редактировать:Только побитовое?Значит, <и> не в счет?
int Compare(int x, int y) {
int diff = x - y;
return (!!diff) | (!!(diff & 0x80000000) << 1);
}
Но вот это противно -.
Редактировать:Переключитесь в другую сторону.
Ммм, просто чтобы попробовать еще раз:
int Compare(int x, int y) {
int diff = y - x;
return (!!diff) << ((diff >> 31) & 1);
}
Но я предполагаю, что не существует стандартной инструкции ASM для !!.Так же << можно заменить на +, смотря что быстрее...
Повозиться с битами — это весело!
Хм, я только что узнал о setnz.
Я не проверял вывод ассемблера (но на этот раз я его немного протестировал), и, если повезет, это может спасти целая инструкция!:
В ТЕОРИИ.МОЙ СБОРЧИК РЖАВЫЙ
subl %edi, %esi
setnz %eax
sarl $31, %esi
andl $1, %esi
sarl %eax, %esi
mov %esi, %eax
ret
Бродяга - это весело.
Мне нужно поспать.
Другие советы
Безветвевой (на уровне языка) код, который отображает отрицательное значение в -1, ноль в 0 и положительное значение в +1, выглядит следующим образом.
int c = (n > 0) - (n < 0);
если вам нужно другое сопоставление, вы можете просто использовать явную карту, чтобы переназначить его
const int MAP[] = { 1, 0, 2 };
int c = MAP[(n > 0) - (n < 0) + 1];
или, для запрошенного сопоставления, используйте какой-нибудь числовой трюк, например
int c = 2 * (n > 0) + (n < 0);
(Очевидно, что из этого очень легко создать любое отображение, если 0 отображается в 0.И код вполне читаемый.Если 0 сопоставляется с чем-то другим, это становится сложнее и менее читабельным.)
В качестве дополнительного примечания:сравнение двух целых чисел путем вычитания одного из другого на уровне языка C является ошибочным методом, поскольку обычно оно склонно к переполнению.Прелесть вышеупомянутых методов в том, что их можно сразу использовать для сравнений без вычитания, например
int c = 2 * (x > y) + (x < y);
Предполагая дополнение до 2, арифметический сдвиг вправо и отсутствие переполнения при вычитании:
#define SHIFT (CHARBIT*sizeof(int) - 1)
int Compare(int x, int y)
{
int diff = x - y;
return -(diff >> SHIFT) - (((-diff) >> SHIFT) << 1);
}
Двойное дополнение:
#include <limits.h>
#define INT_BITS (CHAR_BITS * sizeof (int))
int Compare(int x, int y) {
int d = y - x;
int p = (d + INT_MAX) >> (INT_BITS - 1);
d = d >> (INT_BITS - 2);
return (d & 2) + (p & 1);
}
Предполагая, что компилятор работает нормально, он не будет вызывать аппаратное обеспечение сравнения вашей системы и не будет использовать сравнение в языке.Проверять:если x == y, то d и p явно будут равны 0, поэтому окончательный результат будет равен нулю.Если (x - y) > 0, то ((x - y) + INT_MAX) установит старший бит целого числа, в противном случае он будет отключен.Таким образом, у p будет установлен младший бит тогда и только тогда, когда (x - y) > 0.Если (x - y) < 0, то будет установлен его старший бит, а d установит второй по младшему бит.
Сравнение без знака, возвращающее -1,0,1 (cmpu), является одним из случаев, который проверяется ГНУ СуперОптимизатор.
cmpu: compare (unsigned)
int cmpu(unsigned_word v0, unsigned_word v1)
{
return ( (v0 > v1) ? 1 : ( (v0 < v1) ? -1 : 0) );
}
Супероптимизатор тщательно ищет в пространстве инструкций наилучшую возможную комбинацию инструкций, реализующую заданную функцию. Предполагается, что компиляторы автоматически заменяют приведенные выше функции их супероптимизированными версиями (хотя не все компиляторы это делают).Например, в Руководстве по написанию компилятора PowerPC (powerpc-cwg.pdf), функция cmpu показана в Приложении D на стр. 204:
cmpu: compare (unsigned)
PowerPC SuperOptimized Version
subf R5,R4,R3
subfc R6,R3,R4
subfe R7,R4,R3
subfe R8,R7,R5
Это очень хорошо, не так ли...всего четыре вычитания (и с переносной, и/или расширенной версиями).Не говоря уже о том, что это действительно без ветвей на уровне машинного кода операции.Вероятно, существует эквивалентная последовательность ПК/Intel X86, которая так же коротка, поскольку GNU Superoptimizer работает как для X86, так и для PowerPC.
Обратите внимание, что сравнение без знака (cmpu) можно превратить в сравнение со знаком (cmps) при 32-битном сравнении, добавив 0x80000000 к обоим входам со знаком перед передачей его в cmpu.
cmps: compare (signed)
int cmps(signed_word v0, signed_word v1)
{
signed_word offset=0x80000000;
return ( (unsigned_word) (v0 + signed_word),
(unsigned_word) (v1 + signed_word) );
}
Хотя это только один из вариантов...SuperOptimizer может найти cmps, который короче и не требует добавления смещений и вызова cmpu.
Чтобы получить запрошенную вами версию, которая возвращает значения {1,0,2}, а не {-1,0,1}, используйте следующий код, который использует преимущества функции SuperOptimized cmps.
int Compare(int x, int y)
{
static const int retvals[]={1,0,2};
return (retvals[cmps(x,y)+1]);
}
Я поддерживаю оригинальный ответ Тордека:
int compare(int x, int y) {
return (x < y) + 2*(y < x);
}
Компиляция с gcc -O3 -march=pentium4 приводит к получению кода без ветвей, использующего условные инструкции setg и setl (видеть это объяснение инструкций x86).
push %ebp
mov %esp,%ebp
mov %eax,%ecx
xor %eax,%eax
cmp %edx,%ecx
setg %al
add %eax,%eax
cmp %edx,%ecx
setl %dl
movzbl %dl,%edx
add %edx,%eax
pop %ebp
ret
Боже мой, это преследовало меня.
Как бы то ни было, думаю, я выжал последнюю каплю производительности:
int compare(int a, int b) {
return (a != b) << (a > b);
}
Хотя компиляция с -O3 в GCC даст (потерпите, я делаю это по памяти)
xorl %eax, %eax
cmpl %esi, %edi
setne %al
cmpl %esi, %edi
setgt %dl
sall %dl, %eax
ret
Но второе сравнение кажется (согласно небольшому тестированию;Я хреново разбираюсь в ASM), чтобы быть излишним, оставив маленькое и красивое
xorl %eax, %eax
cmpl %esi, %edi
setne %al
setgt %dl
sall %dl, %eax
ret
(Sall может быть совсем не ASM-инструкцией, но я точно не помню)
Так...если вы не против еще раз запустить тест, мне бы хотелось услышать результаты (мой дал улучшение на 3%, но это может быть неправильно).
Объединение ответов Стивена Кэнона и Тордека:
int Compare(int x, int y)
{
int diff = x - y;
return -(diff >> 31) + (2 & (-diff >> 30));
}
Выход:(г++ -О3)
subl %esi,%edi
movl %edi,%eax
sarl $31,%edi
negl %eax
sarl $30,%eax
andl $2,%eax
subl %edi,%eax
ret
Тугой!Однако версия Пола Се содержит еще меньше инструкций:
subl %esi,%edi
leal 0x7fffffff(%rdi),%eax
sarl $30,%edi
andl $2,%edi
shrl $31,%eax
leal (%rdi,%rax,1),%eax
ret
int Compare(int x, int y)
{
int diff = x - y;
int absdiff = 0x7fffffff & diff; // diff with sign bit 0
int absdiff_not_zero = (int) (0 != udiff);
return
(absdiff_not_zero << 1) // 2 iff abs(diff) > 0
-
((0x80000000 & diff) >> 31); // 1 iff diff < 0
}
Для 32 целых чисел со знаком (как в Java) попробуйте:
return 2 - ((((x >> 30) & 2) + (((x-1) >> 30) & 2))) >> 1;
где (x >> 30) & 2 возвращает 2 для отрицательных чисел и 0 в противном случае.
x будет разницей двух входных целых чисел
