Код без ответвлений, который отображает ноль, минус и позитив на 0, 1, 2

Question

Напишите функцию без ответвлений, которая возвращает 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 показало хорошие результаты во многих тестах , но опять же преимущество в производительности было небольшим. Я был удивлен, что в некоторых случаях некоторые решения были медленнее, чем простое решение с ответвлениями.

Answer 1

Код без ответвлений (на уровне языка), который отображает отрицательное значение -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);

Answer 2

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.

Я не проверял вывод ассемблера (но на этот раз я немного его протестировал), и, если повезет, он может сэкономить всю инструкцию !:

В ТЕОРИИ. МОЙ МОНТАЖНИК RUSTY

subl  %edi, %esi
setnz %eax
sarl  $31, %esi
andl  $1, %esi
sarl  %eax, %esi
mov   %esi, %eax
ret

Бродить весело.

Мне нужен сон.

Answer 3

При условии дополнения 2 с, арифметического сдвига вправо и без переполнения в вычитании:

#define SHIFT (CHARBIT*sizeof(int) - 1)

int Compare(int x, int y)
{
    int diff = x - y;
    return -(diff >> SHIFT) - (((-diff) >> SHIFT) << 1);
}

Answer 4

Два дополнения:

#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 установит его второй младший бит. </p>

Answer 5

Сравнение без знака, которое возвращает -1,0,1 (cmpu), - это один из случаев, который проверяется GNU SuperOptimizer .

cmpu: compare (unsigned)
int cmpu(unsigned_word v0, unsigned_word v1)
{
    return ( (v0 > v1) ? 1 : ( (v0 < v1) ? -1 : 0) );
}

SuperOptimizer исчерпывающе ищет в пространстве команд наилучшую возможную комбинацию команд, которая будет реализовывать данную функцию. Предполагается, что компиляторы автоматически заменяют функции, указанные выше, их супероптимизированными версиями (хотя не все компиляторы делают этот). Например, в Руководстве по написанию компилятора 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]);
}

Answer 6

Я перехожу к первоначальному ответу Тордека:

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 

Answer 7

Боже мой, это преследовало меня.

Как бы то ни было, я думаю, что выжал последнюю каплю производительности:

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

(Сал может быть совсем не инструкцией ASM, но я точно не помню)

Так что ... если вы не возражаете еще раз провести тест, я хотел бы услышать результаты (у меня улучшение составило 3%, но это может быть неправильно).

Answer 8

Для 32 целых чисел со знаком (как в Java) попробуйте:

return 2 - ((((x >> 30) & 2) + (((x-1) >> 30) & 2))) >> 1;

, где (x >> 30) & 2 возвращает 2 для отрицательных чисел и 0 в противном случае.

x будет разностью двух входных целых чисел

Answer 9

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
}

Answer 10

Сочетание ответов Стивена Канона и Тордека:

int Compare(int x, int y)
{
    int diff = x - y; 
    return -(diff >> 31) + (2 & (-diff >> 30));
} 

Выход: (g ++ -O3)

subl     %esi,%edi 
movl     %edi,%eax
sarl     $31,%edi
negl     %eax
sarl     $30,%eax
andl     $2,%eax
subl     %edi,%eax 
ret 

Tight! Тем не менее, версия Пола Се содержит еще меньше инструкций:

subl     %esi,%edi
leal     0x7fffffff(%rdi),%eax
sarl     $30,%edi
andl     $2,%edi
shrl     $31,%eax
leal     (%rdi,%rax,1),%eax
ret