i = (i + 1) & 3 быстрее, чем i = (i + 1)% 4

Question

Я оптимизирую код на C ++.на одном критическом этапе я хочу реализовать следующую функцию y=f(x):

f(0)=1

f(1)=2

f(2)=3

f(3)=0

какая из них быстрее?используя таблицу поиска или i=(i+1)&3 или i=(i+1)%4?или лучше предложение?

Answer 1

Почти наверняка таблица поиска будет медленной.Во многих случаях компилятор генерирует одну и ту же сборку для (i+1)&3 и (i+1)%4;однако, в зависимости от типа / подписи i, они могут быть не совсем эквивалентными, и компилятор не сможет выполнить эту оптимизацию.Например, для кода

int foo(int i)
{
    return (i+1)%4;
}

unsigned bar(unsigned i)
{
    return (i+1)%4;
}

в моей системе, gcc -O2 генерирует:

0000000000000000 <foo>:
   0:   8d 47 01                lea    0x1(%rdi),%eax
   3:   89 c2                   mov    %eax,%edx
   5:   c1 fa 1f                sar    $0x1f,%edx
   8:   c1 ea 1e                shr    $0x1e,%edx
   b:   01 d0                   add    %edx,%eax
   d:   83 e0 03                and    $0x3,%eax
  10:   29 d0                   sub    %edx,%eax
  12:   c3                      retq   

0000000000000020 <bar>:
  20:   8d 47 01                lea    0x1(%rdi),%eax
  23:   83 e0 03                and    $0x3,%eax
  26:   c3                      retq

, так что, как вы можете видеть из правил о результатах модуля со знаком, (i+1)%4 создаетВо-первых, гораздо больше кода.

В итоге, вам, вероятно, лучше использовать версию (i+1)&3, если она выражает то, что вы хотите, потому что у компилятора меньше шансов сделать то, что вы не делаете.не ожидаю.

Answer 2

Я не буду вдаваться в обсуждение преждевременной оптимизации.Но ответ в том, что они будут одинаковой скорости.

Любой здравомыслящий компилятор скомпилирует их в одно и то же.Деление / модуль на степень два будет в любом случае оптимизировано для побитовых операций.

Поэтому используйте то, что вы найдете (или другие найдут), чтобы быть более читабельным.

РЕДАКТИРОВАТЬ: Как отметил Роланд, он иногда ведет себя по-разному в зависимости от подписи:

Без знака &:

int main(void)
{
    unsigned x;
    cin >> x;
    x = (x + 1) & 3;
    cout << x;

    return 0;
}

mov eax, DWORD PTR _x$[ebp]
inc eax
and eax, 3
push    eax

Модуль без знака:

int main(void)
{
    unsigned x;
    cin >> x;
    x = (x + 1) % 4;
    cout << x;

    return 0;
}

mov eax, DWORD PTR _x$[ebp]
inc eax
and eax, 3
push    eax

Подпись &:

int main(void)
{
    int x;
    cin >> x;
    x = (x + 1) & 3;
    cout << x;

    return 0;
}

mov eax, DWORD PTR _x$[ebp]
inc eax
and eax, 3
push    eax

Подписанный модуль:

int main(void)
{
    int x;
    cin >> x;
    x = (x + 1) % 4;
    cout << x;

    return 0;
}

mov eax, DWORD PTR _x$[ebp]
inc eax
and eax, -2147483645            ; 80000003H
jns SHORT $LN3@main
dec eax
or  eax, -4                 ; fffffffcH

Answer 3

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

Answer 4

Вы пробовали сравнить его? В качестве необоснованного предположения, я предполагаю, что версия &3 будет быстрее, поскольку это простое добавление и побитовая операция И, обе из которых должны быть одноцикловыми операциями на любом современном ЦПУ.

%4 может пойти несколькими путями, в зависимости от того, насколько умным является компилятор. это можно сделать с помощью деления, которое намного медленнее, чем сложение, или же оно может быть переведено в побитовую and операцию и в итоге будет таким же быстрым, как и &3 версия.

Answer 5

то же, что и Mystical, но C и ARM

int fun1 ( int i )
{
    return( (i+1)&3 );
}

int fun2 ( int i )
{
    return( (i+1)%4 );
}

unsigned int fun3 ( unsigned int i )
{
    return( (i+1)&3 );
}

unsigned int fun4 ( unsigned int i )
{
    return( (i+1)%4 );
}

создает:

00000000 <fun1>:
   0:   e2800001    add r0, r0, #1
   4:   e2000003    and r0, r0, #3
   8:   e12fff1e    bx  lr

0000000c <fun2>:
   c:   e2802001    add r2, r0, #1
  10:   e1a0cfc2    asr ip, r2, #31
  14:   e1a03f2c    lsr r3, ip, #30
  18:   e0821003    add r1, r2, r3
  1c:   e2010003    and r0, r1, #3
  20:   e0630000    rsb r0, r3, r0
  24:   e12fff1e    bx  lr

00000028 <fun3>:
  28:   e2800001    add r0, r0, #1
  2c:   e2000003    and r0, r0, #3
  30:   e12fff1e    bx  lr

00000034 <fun4>:
  34:   e2800001    add r0, r0, #1
  38:   e2000003    and r0, r0, #3
      3c:   e12fff1e    bx  lr

Для отрицательных чисел маска и модуль не эквивалентны, только для положительных / беззнаковых чисел.В этих случаях ваш компилятор должен знать, что% 4 - это то же самое, что и & 3, и использовать менее дорогой для (& 3), как gcc выше.лязг / ооо ниже

fun3:                             
    add r0, r0, #1
    and r0, r0, #3
    mov pc, lr

fun4:
    add r0, r0, #1
    and r0, r0, #3
    mov pc, lr

Answer 6

Конечно и быстрее, чем%. Что доказано многими предыдущими постами. Также, поскольку i является локальной переменной, вы можете использовать ++ i вместо i + 1, так как это лучше реализуется большинством компиляторов. i + 1 может (не) быть оптимизирован как ++ i.

ОБНОВЛЕНИЕ: Возможно, я не совсем понял, я имел в виду, что функция должна просто "вернуть ((++ i) & 3);"