В C ++, что быстрее?(2 * i + 1) или (i << 1 | 1)?

Question

Я понимаю, что ответ, вероятно, зависит от аппаратного обеспечения, но мне любопытно, была ли более общая интуиция, по которой я скучаю?

Я задал этот вопрос и далответ, теперь я задаюсь вопросом, должен ли я вообще изменить свой подход, чтобы использовать "(i << 1 | 1)" вместо "(2 * i + 1)" ?? </p>

Answer 1

Поскольку стандарт ISO на самом деле не требует требований к производительности, это будет зависеть от реализации, выбранных флагов компилятора, целевого процессора и, возможно, фазы луны.

Такого рода оптимизация (сохранение нескольких циклов) почти всегда становится незначительным с точки зрения окупаемости инвестиций на фоне оптимизаций на макроуровне, таких как выбор алгоритма.

В первую очередь, стремимся к удобочитаемости кода.Если вы хотите сдвинуть биты и OR, используйте версию с битовой сменой.Если ваше намерение заключается в умножении, используйте версию *.Заботьтесь о производительности только после того, как вы установили, что есть проблема.

Любой приличный компилятор оптимизирует ее гораздо лучше, чем вы в любом случае: -)

Answer 2

Просто эксперимент, касающийся ответов, данных о "... он будет использовать LEA":
Следующий код:

int main(int argc, char **argv)
{
#ifdef USE_SHIFTOR
return (argc << 1 | 1);
#else
return (2 * argc + 1);
#endif
}

, с gcc -fomit-frame-pointer -O8 -m{32|64} (для 32 или 64 бит)) скомпилировать в следующий код сборки:

1. x86, 32 бита:

   080483a0 <main>:
   80483a0:    8b 44 24 04             mov    0x4(%esp),%eax
   80483a4:    8d 44 00 01             lea    0x1(%eax,%eax,1),%eax
   80483a8:    c3                      ret

2. x86, 64 бита:

   00000000004004c0 <main>:
   4004c0: 8d 44 3f 01             lea    0x1(%rdi,%rdi,1),%eax
   4004c4: c3                      retq

3. x86, 64 бита, -DUSE_SHIFTOR:

   080483a0 <main>:
   80483a0:    8b 44 24 04             mov    0x4(%esp),%eax
   80483a4:    01 c0                   add    %eax,%eax
   80483a6:    83 c8 01                or     $0x1,%eax
   80483a9:    c3                      ret

4. x86, 32 бита, -DUSE_SHIFTOR:

   00000000004004c0 <main>:
   4004c0: 8d 04 3f                lea    (%rdi,%rdi,1),%eax
   4004c3: 83 c8 01                or     $0x1,%eax
   4004c6: c3                      retq

Фактически, в большинстве случаев будет использоваться LEA.Тем не менее, код не одинаков для двух случаев.Для этого есть две причины:

1. сложение может переполниться и обернуться, в то время как битовые операции, такие как << или |, не могут
2. (x + 1) == (x | 1), только если true !(x & 1) иначе добавление переносится на следующий бит.Как правило, добавление единицы приводит к тому, что младший бит устанавливается в половине случаев.

Хотя мы (и, возможно, компилятор) знаем, что второе обязательно применимо, первое по-прежнемувозможность.Таким образом, компилятор создает другой код, поскольку для «or-version» необходимо установить нулевой бит в 1.

Answer 3

Любой, кроме самого мертвого компилятора, увидит эти выражения как эквивалентные и скомпилирует их в один и тот же исполняемый код.

Как правило, не стоит особо беспокоиться об оптимизации простых арифметических выражений, подобных этим, поскольку компиляторы лучше всего подходят для оптимизации.(В отличие от многих других случаев, когда «умный компилятор» может делать правильные вещи, но фактический компилятор не работает.)

Это сработает в той же паре инструкций для PPC, Sparc и MIPSМежду прочим: сдвиг, сопровождаемый добавлением.На ARM это будет сводиться к одной объединенной инструкции shift-add, а на x86 это, вероятно, будет одна LEA op.

Answer 4

Вывод gcc с опцией -S (флаги компилятора не заданы):

.LCFI3:
        movl    8(%ebp), %eax
        addl    %eax, %eax
        orl     $1, %eax
        popl    %ebp
        ret

.LCFI1:
        movl    8(%ebp), %eax
        addl    %eax, %eax
        addl    $1, %eax
        popl    %ebp
        ret

Я не уверен, какой из них какой, но я не верю, что это важно.

Если компилятор не выполняет никаких оптимизаций, то второй, вероятно, будет переводиться в более быстрые инструкции по сборке.Сколько времени занимает каждая инструкция, полностью зависит от архитектуры.Большинство компиляторов оптимизируют их так, чтобы они соответствовали инструкциям уровня сборки.

Answer 5

Я только что проверил это с gcc-4.7.1, используя источник FrankH, сгенерированный код:

lea    0x1(%rdi,%rdi,1),%eax
retq

независимо от того, используется версия смещения или умножения.

Answer 6

Чем быстрее первая форма (та, у которой сдвиг вправо), на самом деле инструкция shr выполняет 4 такта в худшем случае, а mul 10 - в лучшемОднако, лучшая форма должна быть определена компилятором, потому что он имеет полное представление о других (сборочных) инструкциях.

Answer 7

i + i + 1 может быть быстрее, чем другие два, потому что сложение быстрее, чем умножение и может быть быстрее, чем сдвиг.

Answer 8

Никому нет дела. И они не должны.
Перестаньте беспокоиться об этом и получите правильный, простой и готовый код.