n отрицательный, положительный или ноль? вернуть 1, 2 или 4

Question

Я создаю интерпретатор PowerPC, и он работает довольно хорошо.В архитектуре Power регистр условий CR0 (EFLAGS на x86) обновляется практически для любой инструкции.Это установлено так.Значение CR0 равно 1, если последний результат был отрицательным, 2, если последний результат был положительным, иначе 4. 4.

Мой первый наивный метод для интерпретации этого:

if (n < 0)
    cr0 = 1
else if (n > 0)
    cr0 = 2;
else
    cr0 = 4;

ОднакоЯ понимаю, что все эти ветви не будут оптимальными, будучи запущенными миллионы раз в секунду.Я видел немного взлома на SO, но ни один из них не казался мне идеальным.Например, я нашел много примеров для преобразования числа в -1, 0 или 1 соответственно в знак или 0. Но как сделать -1 = 1, 1 = 2, 0 = 4?Я прошу помощи Bit Hackers ...

Заранее спасибо

Обновление: Прежде всего: спасибо, ребята, вы были великолепны.Я тщательно проверю все ваши коды на скорость, и вы будете первыми, кто узнает, кто победил.

@ jalf: Что касается вашего первого совета, я фактически не рассчитывал CR0 для каждой инструкции.Я скорее держал переменную lastResult, и когда (и если) следующая инструкция запрашивала флаг, сделайте сравнение.Три основных мотивации вернули меня к обновлению «каждый раз»:

1. На PPC вы не обязаны обновлять CR0, как на x86 (где ADD всегда меняет EFLAGS, даже если не требуется), у вас есть дваароматы ADD, одно обновление.Если компилятор решит использовать обновляющий, это означает, что он будет использовать CR0 в какой-то момент, поэтому нет смысла откладывать ...
2. Существует особенно болезненная инструкция под названием mtcrf, которая позволяет вамизмените CR0 произвольно.Вы даже можете установить его равным 7, без арифметического значения ... Это просто уничтожает возможность сохранения переменной lastResult.

Answer 1

Во-первых, если эта переменная должна обновляться после (почти) каждой инструкции, очевидный совет:

не

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

Но в любом случае, когда мы обновляем его, нам нужно следующее поведение:

R < 0  => CR0 == 0b001 
R > 0  => CR0 == 0b010
R == 0 => CR0 == 0b100

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

1. Установите CR0 на значение 1. (если вам действительно нужна скорость, выясните, можно ли это сделать, не извлекая константу из памяти. Даже если вам придется потратить на это пару инструкций, это может стоить того)
2. Если R> = 0, сдвиг влево на один бит.
3. Если R == 0, сдвиг влево на один бит

Где шаги 2 и 3 могут быть преобразованы для исключения части "если"

CR0 <<= (R >= 0);
CR0 <<= (R == 0);

Это быстрее? Я не знаю. Как всегда, когда вы беспокоитесь о производительности, вам нужно измерить, измерить, измерить.

Однако я вижу несколько преимуществ этого подхода:

1. избегаем веток полностью
2. мы избегаем загрузки / хранения памяти.
3. инструкции, на которые мы опираемся (сдвиг битов и сравнение), должны иметь низкую задержку, что, например, не всегда имеет место для умножения.

Недостатком является то, что у нас есть цепочка зависимостей между всеми тремя строками: каждая изменяет CR0, который затем используется в следующей строке. Это несколько ограничивает параллелизм на уровне команд.

Чтобы минимизировать эту цепочку зависимостей, мы могли бы сделать что-то вроде этого:

CR0 <<= ((R >= 0) + (R == 0));

поэтому нам нужно изменить CR0 только один раз, после его инициализации.

Или, делая все в одной строке:

CR0 = 1 << ((R >= 0) + (R == 0));

Конечно, существует множество возможных вариаций этой темы, поэтому продолжайте и экспериментируйте.

Answer 2

Множество ответов, которые, как обычно, уже "не", как обычно :) Вы хотите немного взломать? Ты получишь это. Тогда не стесняйтесь использовать его или нет как вы посчитаете нужным.

Вы можете использовать это отображение на -1, 0 и 1 (sign), а затем сделать это:

return 7 & (0x241 >> ((sign(x) + 1) * 4));

Который по существу использует крошечную таблицу поиска.

Или "наивный битхак":

int y = ((x >> 31) & 1) | ((-x >> 31) & 2)
return (~(-y >> 31) & 4) | y;

Первая строка отображает x < 0 в 1, x > 0 в 2 и x == 0 в 0. Вторая строка затем отображает y == 0 в 4 и y != 0 в y.

---

И, конечно, он имеет случай скрытого края для x = 0x80000000, который сопоставлен с 3. Упс. Что ж, давайте исправим это:

int y = ((x >> 31) & 1) | ((-x >> 31) & 2)
y &= 1 | ~(y << 1);  // remove the 2 if odd
return (~(-y >> 31) & 4) | y;

Answer 3

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

cr0 = 4 >> ((2 * (n < 0)) + (n > 0));

Вот что GCC 4.6.1 для цели x86 компилирует егос -O2:

xor ecx, ecx
mov eax, edx
sar eax, 31
and eax, 2
test    edx, edx
setg    cl
add ecx, eax
mov eax, 4
sar eax, cl

И VC 2010 с /Ox выглядит очень похоже:

xor ecx, ecx
test eax, eax
sets cl
xor edx, edx
test eax, eax
setg dl
mov eax, 4
lea ecx, DWORD PTR [edx+ecx*2]
sar eax, cl

Версия, использующая if тесты, компилируется в сборку, в которой используются переходы либо сиз этих компиляторов.Конечно, вы никогда не будете уверены, что какой-то конкретный компилятор будет делать с каким-то конкретным фрагментом кода, который вы выберете, если вы на самом деле не изучите вывод.Мое выражение настолько загадочно, что, если бы это не был действительно критичный к производительности фрагмент кода, я все равно мог бы пойти с if версией оператора.Поскольку вам нужно часто устанавливать регистр CR0, я думаю, возможно, стоит измерить, поможет ли это выражение вообще.

Answer 4

Я работал над этим при сбое моего компьютера.

int cr0 = (-(n | n-1) >> 31) & 6;
cr0 |= (n >> 31) & 5;
cr0 ^= 4;

Вот итоговая сборка (для Intel x86):

PUBLIC  ?tricky@@YAHH@Z                                 ; tricky
; Function compile flags: /Ogtpy
_TEXT   SEGMENT
_n$ = 8                                                 ; size = 4
?tricky@@YAHH@Z PROC                                    ; tricky
; Line 18
        mov     ecx, DWORD PTR _n$[esp-4]
        lea     eax, DWORD PTR [ecx-1]
        or      eax, ecx
        neg     eax
        sar     eax, 31                                 ; 0000001fH
; Line 19
        sar     ecx, 31                                 ; 0000001fH
        and     eax, 6
        and     ecx, 5
        or      eax, ecx
; Line 20
        xor     eax, 4
; Line 22
        ret     0
?tricky@@YAHH@Z ENDP                                    ; tricky

И полный исчерпывающий тест, который такжеразумно подходит для бенчмаркинга:

#include <limits.h>

int direct(int n)
{
    int cr0;
    if (n < 0)
        cr0 = 1;
    else if (n > 0)
        cr0 = 2;
    else
        cr0 = 4;
    return cr0;
}

const int shift_count = sizeof(int) * CHAR_BIT - 1;
int tricky(int n)
{
    int cr0 = (-(n | n-1) >> shift_count) & 6;
    cr0 |= (n >> shift_count) & 5;
    cr0 ^= 4;
    return cr0;
}

#include <iostream>
#include <iomanip>
int main(void)
{
    int i = 0;
    do {
        if (direct(i) != tricky(i)) {
            std::cerr << std::hex << i << std::endl;
            return i;
        }
    } while (++i);
    return 0;
}

Answer 5

gcc без оптимизации

        movl    %eax, 24(%esp)  ; eax has result of reading n
        cmpl    $0, 24(%esp)
        jns     .L2
        movl    $1, 28(%esp)
        jmp     .L3
.L2:
        cmpl    $0, 24(%esp)
        jle     .L4
        movl    $2, 28(%esp)
        jmp     .L3
.L4:
        movl    $4, 28(%esp)
.L3:

С -O2:

        movl    $1, %edx       ; edx = 1
        cmpl    $0, %eax
        jl      .L2            ; n < 0
        cmpl    $1, %eax       ; n < 1
        sbbl    %edx, %edx     ; edx = 0 or -1
        andl    $2, %edx       ; now 0 or 2
        addl    $2, %edx       ; now 2 or 4
.L2:
        movl    %edx, 4(%esp)

Я не думаю, что вы, вероятно, будете намного лучше

Answer 6

Для совершенно непереносимого подхода, мне интересно, может ли это иметь какое-то преимущество в скорости:

void func(signed n, signed& cr0) {
    cr0 = 1 << (!(unsigned(n)>>31)+(n==0));
}

mov         ecx,eax  ;with MSVC10, all optimizations except inlining on.
shr         ecx,1Fh  
not         ecx  
and         ecx,1  
xor         edx,edx  
test        eax,eax  
sete        dl  
mov         eax,1  
add         ecx,edx  
shl         eax,cl  
mov         ecx,dword ptr [cr0]  
mov         dword ptr [ecx],eax  

по сравнению с вашим кодом на моей машине:

test        eax,eax            ; if (n < 0)
jns         func+0Bh (401B1Bh)  
mov         dword ptr [ecx],1  ; cr0 = 1;
ret                            ; cr0 = 2; else cr0 = 4; }
xor         edx,edx            ; else if (n > 0)
test        eax,eax  
setle       dl  
lea         edx,[edx+edx+2]  
mov         dword ptr [ecx],edx ; cr0 = 2; else cr0 = 4; }
ret  

Я не знаюМногое о сборке, так что я не могу точно сказать, принесет ли это какую-либо пользу (или даже если у меня есть какие-то прыжки. В любом случае я не вижу инструкций, начинающихся с j).Как всегда (и как все говорили миллион раз) ПРОФИЛЬ.

Я сомневаюсь, что это быстрее, чем, скажем, у Джальфа или Бена, но я не видел ни одного, который бы использовал тот факт, что на x86 все отрицательноу чисел есть определенный бит, и я решил выбросить его.

[EDIT] БенВойгт предлагает cr0 = 4 >> ((n != 0) + (unsigned(n) >> 31)); убрать логическое отрицание, и мои тесты показывают, что это обширный улучшение.

Answer 7

Если есть более быстрый метод, компилятор, вероятно, уже использует его.

Сохраните ваш код коротким и простым;это делает оптимизатор наиболее эффективным.

Простое простое решение удивительно хорошо справляется со скоростью:

cr0 = n? (n < 0)? 1: 2: 4;

x86 Assembly (производится VC ++ 2010, flags /Ox):

PUBLIC  ?tricky@@YAHH@Z                                 ; tricky
; Function compile flags: /Ogtpy
_TEXT   SEGMENT
_n$ = 8                                                 ; size = 4
?tricky@@YAHH@Z PROC                                    ; tricky
; Line 26
        mov     eax, DWORD PTR _n$[esp-4]
        test    eax, eax
        je      SHORT $LN3@tricky
        xor     ecx, ecx
        test    eax, eax
        setns   cl
        lea     eax, DWORD PTR [ecx+1]
; Line 31
        ret     0
$LN3@tricky:
; Line 26
        mov     eax, 4
; Line 31
        ret     0
?tricky@@YAHH@Z ENDP                                    ; tricky

Answer 8

Следующая моя попытка.

int cro = 4 >> (((n > 0) - (n < 0)) % 3 + (n < 0)*3);