Оператор if vs оператор if-else, что быстрее? [закрыто]

84

На днях я спорил с другом по поводу этих двух отрывков. Что быстрее и почему?

value = 5;
if (condition) {
    value = 6;
}

и:

if (condition) {
    value = 6;
} else {
    value = 5;
}

Что, если valueэто матрица?

Примечание: я знаю, что он value = condition ? 6 : 5;существует, и ожидаю, что он будет быстрее, но это был не вариант.

Изменить (запрошено персоналом, поскольку вопрос в настоящий момент отложен):

  • ответьте, пожалуйста, на сборку x86, сгенерированную основными компиляторами ( например, g ++, clang ++, vc, mingw ) как в оптимизированной, так и в неоптимизированной версиях, или сборку MIPS .
  • если сборки различаются, объясните, почему версия работает быстрее и когда ( например, «лучше, потому что нет ветвления и ветвления не имеют следующей проблемы, бла-бла» )
Жюльен__
источник
173
Оптимизация убьет все это ... это не имеет значения ...
The Quantum Physicist
21
Вы можете профилировать его, лично я сомневаюсь, что вы заметите какую-либо разницу, используя современный компилятор.
Джордж
25
Использование value = condition ? 6 : 5;вместо if/else, скорее всего, приведет к созданию того же кода. Посмотрите на вывод сборки, если хотите узнать больше.
Jabberwocky
8
в этом случае самое главное - избегать ветки, которая здесь самая дорогая. (перезагрузка канала, удаление предварительно
загруженных
11
Единственный раз, когда имеет смысл микро-оптимизировать скорость, как это, - это внутри цикла, который будет выполняться много-много раз, и либо оптимизатор может оптимизировать все инструкции ветвления, как gcc для этого тривиального примера, либо в реальном мире производительность будет сильно зависеть от правильного предсказания ветвления (обязательная ссылка на stackoverflow.com/questions/11227809/… ). Если вы неизбежно разветвляетесь внутри цикла, вы можете помочь предсказателю ветвления, сгенерировав профиль и перекомпилировав его.
Дэвислор

Ответы:

282

TL; DR: В неоптимизированном коде ifбез elseкажется несущественно более эффективным, но даже при включении самого базового уровня оптимизации код в основном переписывается value = condition + 5.


Я попробовал и сгенерировал сборку для следующего кода:

int ifonly(bool condition, int value)
{
    value = 5;
    if (condition) {
        value = 6;
    }
    return value;
}

int ifelse(bool condition, int value)
{
    if (condition) {
        value = 6;
    } else {
        value = 5;
    }
    return value;
}

В gcc 6.3 с отключенной оптимизацией ( -O0) соответствующая разница:

 mov     DWORD PTR [rbp-8], 5
 cmp     BYTE PTR [rbp-4], 0
 je      .L2
 mov     DWORD PTR [rbp-8], 6
.L2:
 mov     eax, DWORD PTR [rbp-8]

в ifonlyто время ifelseкак

 cmp     BYTE PTR [rbp-4], 0
 je      .L5
 mov     DWORD PTR [rbp-8], 6
 jmp     .L6
.L5:
 mov     DWORD PTR [rbp-8], 5
.L6:
 mov     eax, DWORD PTR [rbp-8]

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

Однако даже при самом низком уровне оптимизации ( -O1) обе функции сводятся к одному и тому же:

test    dil, dil
setne   al
movzx   eax, al
add     eax, 5

что в основном эквивалентно

return 5 + condition;

предполагая, что conditionэто ноль или один. Более высокие уровни оптимизации на самом деле не меняют результат, за исключением того, что им удается избежать movzx, эффективно обнуляя EAXрегистр в начале.


Отказ от ответственности: вам, вероятно, не следует писать 5 + conditionсамостоятельно (хотя стандартные гарантии, что преобразование trueв целочисленный тип дает 1), потому что ваше намерение может не сразу быть очевидным для людей, читающих ваш код (которые могут включать ваше будущее). Цель этого кода - показать, что то, что компилятор производит в обоих случаях (практически) идентично. Сиприан Томояга хорошо об этом говорит в комментариях:

Человек Иов, чтобы написать код для людей , и пусть компилятор кода для записи машины .

CompuChip
источник
50
Это отличный ответ, и его следует принять.
dtell
10
Я бы никогда не подумал использовать дополнение (<- что питон делает с вами.)
Ciprian Tomoiagă
26
@CiprianTomoiaga, и если вы не пишете оптимизатор, вам не нужно! Практически во всех случаях вы должны позволить компилятору выполнять подобные оптимизации, особенно когда они сильно ухудшают читаемость кода. Только если тестирование производительности выявляет проблемы с определенным фрагментом кода, вам следует даже начать попытки его оптимизировать, и даже тогда держать его в чистоте и хорошо комментировать, и выполнять только оптимизацию, которая дает измеримые различия.
Muzer
22
Я хотел ответить Музеру, но это не добавило бы ничего к теме. Однако я просто хочу повторить, что человеческая работа - писать код для людей, а компилятор - писать код для машины . Я сказал это от разработчика компилятора PoV (что я не знаю, но я немного узнал о них)
Ciprian Tomoiagă
10
Значение, trueпреобразованное в intвсегда, дает 1, период. Конечно, если ваше состояние просто «правдиво», а не boolценность true, то это совсем другое дело.
TC
44

Ответ CompuChip показывает, что intони оба оптимизированы для одной и той же сборки, поэтому это не имеет значения.

Что, если значение - это матрица?

Я буду интерпретировать это в более общем смысле, т.е. что, если valueотносится к типу, конструкции и назначения которого дороги (а ходы дешевы).

тогда

T value = init1;
if (condition)
   value = init2;

является неоптимальным, потому что в случае conditionистины вы выполняете ненужную инициализацию, init1а затем выполняете копирование.

T value;
if (condition)
   value = init2;
else
   value = init3;

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

У вас есть хорошее решение с условным оператором:

T value = condition ? init1 : init2;

Или, если вам не нравится условный оператор, вы можете создать вспомогательную функцию, подобную этой:

T create(bool condition)
{
  if (condition)
     return {init1};
  else
     return {init2};
}

T value = create(condition);

В зависимости от того, что init1и init2как вы также можете рассмотреть это:

auto final_init = condition ? init1 : init2;
T value = final_init;

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

болов
источник
3
Дорогое и не оптимизированное. Например, если конструктор по умолчанию обнуляет матрицу, компилятор может понять, что присваивание просто перезаписывает эти 0, поэтому не обнуляет его вообще, а записывает непосредственно в эту память. Конечно, оптимизаторы привередливы, поэтому трудно предсказать, когда они
Матье М.
@MatthieuM. конечно. Под словом «дорого» я ​​имел в виду «дорогое выполнение (по метрике, будь то
частота
Мне кажется маловероятным, что строительство по умолчанию будет дорогим, а перемещение будет дешевым.
plugwash
6
@plugwash Рассмотрим класс с очень большим распределенным массивом. Конструктор по умолчанию выделяет и инициализирует массив, что требует больших затрат. Конструктор перемещения (не копирования!) Может просто поменять местами указатели с исходным объектом, и ему не нужно выделять или инициализировать большой массив.
TrentP
1
Поскольку части простые, я определенно предпочитаю использовать ?:оператор, а не вводить новую функцию. В конце концов, вы, скорее всего, передадите в функцию не только условие, но и некоторые аргументы конструктора. Некоторые из них могут даже не использоваться в create()зависимости от состояния.
cmaster - восстановить
12

На псевдо-ассемблере

    li    #0, r0
    test  r1
    beq   L1
    li    #1, r0
L1:

может или не может быть быстрее, чем

    test  r1
    beq   L1
    li    #1, r0
    bra   L2
L1:
    li    #0, r0
L2:

в зависимости от того, насколько сложен фактический процессор. От самого простого к самому красивому:

  • Для любого ЦП, произведенного примерно после 1990 года, хорошая производительность зависит от соответствия кода кэшу инструкций . Поэтому в случае сомнений минимизируйте размер кода. Это говорит в пользу первого примера.

  • С базовым процессором « упорядоченного пятиступенчатого конвейера », который по-прежнему является примерно тем, что вы получаете во многих микроконтроллерах, возникает пузырек конвейера каждый раз, когда выполняется переход - условный или безусловный - поэтому также важно минимизировать количество инструкций ветвления. Это тоже говорит в пользу первого примера.

  • Несколько более сложные процессоры - достаточно причудливые, чтобы выполнять « неупорядоченное выполнение », но недостаточно сложные , чтобы использовать наиболее известные реализации этой концепции, - могут вызывать пузыри конвейера всякий раз, когда они сталкиваются с опасностями записи после записи . Это говорит в пользу второго примера, где r0написано только один раз, несмотря ни на что. Эти процессоры обычно достаточно наворочены, чтобы обрабатывать безусловные переходы в сборщике инструкций, поэтому вы не просто обмениваете штраф за запись после записи на штраф за переход .

    Я не знаю, делает ли кто-нибудь еще такие процессоры. Однако процессоры, которые действительно используют «самые известные реализации» внепланового выполнения, вероятно, срежут углы на менее часто используемых инструкциях, поэтому вы должны знать, что такого рода вещи могут случиться. Реальный пример - ложные зависимости данных от регистров назначения в процессорах Sandy Bridge popcntи lzcntна них .

  • На самом высоком конце OOO-движок завершит выполнение одной и той же последовательности внутренних операций для обоих фрагментов кода - это аппаратная версия «не беспокойтесь об этом, компилятор в любом случае сгенерирует один и тот же машинный код». Однако размер кода по-прежнему имеет значение, и теперь вы также должны беспокоиться о предсказуемости условного перехода. Сбои в прогнозировании ветвления потенциально могут вызвать полную очистку конвейера , что является катастрофическим для производительности; см. Почему обрабатывать отсортированный массив быстрее, чем несортированный? чтобы понять, насколько это может иметь значение.

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

        li    #0, r0
        test  r1
        setne r0
    

    или же

        li    #0, r0
        li    #1, r2
        test  r1
        movne r2, r0
    

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

Zwol
источник
Я бы перефразировал ваше второе замечание относительно того, есть ли у ЦП механизм неисправности, который задерживается из-за опасностей записи после записи. Если процессор имеет испорченный двигатель , который может работать с такими опасностями без задержки, нет никаких проблем, но нет также никаких проблем , если процессор не имеет двигателя испорченные вообще .
supercat
@supercat В конце абзаца рассматривается этот случай, но я подумаю, как сделать его более понятным.
zwol
Я не знаю, какие текущие процессоры имеют кеш, который заставил бы последовательно выполняемый код работать быстрее во второй раз, чем в первый раз (некоторые части ARM на основе флэш-памяти имеют интерфейс, который может буферизовать несколько строк флэш-данных, но могут извлекать код последовательно так же быстро, как они его выполняют, но ключ к быстрому выполнению кода с тяжелыми ветвями - это копирование его в ОЗУ). ЦП без какого-либо нарушения порядка выполнения встречаются гораздо чаще, чем те, которые могут задерживаться из-за опасностей записи после записи.
supercat
Это очень проницательно
Жюльен__
9

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

Как всегда, если вас это беспокоит, сгенерируйте сборку и посмотрите, что на самом деле делает компилятор.

Нил
источник
1
Если беспокоиться о производительности, они не будут компилировать неоптимизированные. Но, конечно, насколько "хорош" оптимизатор, зависит от компилятора / версии.
old_timer
AFAIK нет комментариев о том, какая архитектура компилятора / процессора и т.д., поэтому потенциально их компилятор не выполняет оптимизацию. Они могут компилироваться на чем угодно, от 8-битного PIC до 64-битного Xeon.
Нил
8

Что заставит вас подумать, что любой из них, даже один лайнер, быстрее или медленнее?

unsigned int fun0 ( unsigned int condition, unsigned int value )
{
    value = 5;
    if (condition) {
        value = 6;
    }
    return(value);
}
unsigned int fun1 ( unsigned int condition, unsigned int value )
{

    if (condition) {
        value = 6;
    } else {
        value = 5;
    }
    return(value);
}
unsigned int fun2 ( unsigned int condition, unsigned int value )
{
    value = condition ? 6 : 5;
    return(value);
}

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

00000000 <fun0>:
   0:   e3500000    cmp r0, #0
   4:   03a00005    moveq   r0, #5
   8:   13a00006    movne   r0, #6
   c:   e12fff1e    bx  lr

00000010 <fun1>:
  10:   e3500000    cmp r0, #0
  14:   13a00006    movne   r0, #6
  18:   03a00005    moveq   r0, #5
  1c:   e12fff1e    bx  lr

00000020 <fun2>:
  20:   e3500000    cmp r0, #0
  24:   13a00006    movne   r0, #6
  28:   03a00005    moveq   r0, #5
  2c:   e12fff1e    bx  lr

неудивительно, что первая функция выполнилась в другом порядке, хотя и с тем же временем выполнения.

0000000000000000 <fun0>:
   0:   7100001f    cmp w0, #0x0
   4:   1a9f07e0    cset    w0, ne
   8:   11001400    add w0, w0, #0x5
   c:   d65f03c0    ret

0000000000000010 <fun1>:
  10:   7100001f    cmp w0, #0x0
  14:   1a9f07e0    cset    w0, ne
  18:   11001400    add w0, w0, #0x5
  1c:   d65f03c0    ret

0000000000000020 <fun2>:
  20:   7100001f    cmp w0, #0x0
  24:   1a9f07e0    cset    w0, ne
  28:   11001400    add w0, w0, #0x5
  2c:   d65f03c0    ret

Надеюсь, вы поняли, что могли бы просто попробовать это, если бы не было очевидно, что разные реализации на самом деле не отличаются.

Что касается матрицы, не знаю, какое это имеет значение,

if(condition)
{
 big blob of code a
}
else
{
 big blob of code b
}

просто собираюсь поместить ту же оболочку if-then-else вокруг больших кляксов кода, будь то значение = 5 или что-то более сложное. Точно так же сравнение, даже если это большой кусок кода, его все равно нужно вычислить, и он равен или не равен чему-то, часто компилируется с отрицательным значением, if (condition) do something часто компилируется, как если бы не условие goto.

00000000 <fun0>:
   0:   0f 93           tst r15     
   2:   03 24           jz  $+8         ;abs 0xa
   4:   3f 40 06 00     mov #6, r15 ;#0x0006
   8:   30 41           ret         
   a:   3f 40 05 00     mov #5, r15 ;#0x0005
   e:   30 41           ret         

00000010 <fun1>:
  10:   0f 93           tst r15     
  12:   03 20           jnz $+8         ;abs 0x1a
  14:   3f 40 05 00     mov #5, r15 ;#0x0005
  18:   30 41           ret         
  1a:   3f 40 06 00     mov #6, r15 ;#0x0006
  1e:   30 41           ret         

00000020 <fun2>:
  20:   0f 93           tst r15     
  22:   03 20           jnz $+8         ;abs 0x2a
  24:   3f 40 05 00     mov #5, r15 ;#0x0005
  28:   30 41           ret         
  2a:   3f 40 06 00     mov #6, r15 ;#0x0006
  2e:   30 41

мы только что проделали это упражнение с кем-то недавно на stackoverflow. Интересно, что этот компилятор mips не только понял, что функции были одинаковыми, но и заставил одну функцию просто переходить к другой, чтобы сэкономить место для кода. Но я этого не делал

00000000 <fun0>:
   0:   0004102b    sltu    $2,$0,$4
   4:   03e00008    jr  $31
   8:   24420005    addiu   $2,$2,5

0000000c <fun1>:
   c:   0004102b    sltu    $2,$0,$4
  10:   03e00008    jr  $31
  14:   24420005    addiu   $2,$2,5

00000018 <fun2>:
  18:   0004102b    sltu    $2,$0,$4
  1c:   03e00008    jr  $31
  20:   24420005    addiu   $2,$2,5

еще несколько целей.

00000000 <_fun0>:
   0:   1166            mov r5, -(sp)
   2:   1185            mov sp, r5
   4:   0bf5 0004       tst 4(r5)
   8:   0304            beq 12 <_fun0+0x12>
   a:   15c0 0006       mov $6, r0
   e:   1585            mov (sp)+, r5
  10:   0087            rts pc
  12:   15c0 0005       mov $5, r0
  16:   1585            mov (sp)+, r5
  18:   0087            rts pc

0000001a <_fun1>:
  1a:   1166            mov r5, -(sp)
  1c:   1185            mov sp, r5
  1e:   0bf5 0004       tst 4(r5)
  22:   0204            bne 2c <_fun1+0x12>
  24:   15c0 0005       mov $5, r0
  28:   1585            mov (sp)+, r5
  2a:   0087            rts pc
  2c:   15c0 0006       mov $6, r0
  30:   1585            mov (sp)+, r5
  32:   0087            rts pc

00000034 <_fun2>:
  34:   1166            mov r5, -(sp)
  36:   1185            mov sp, r5
  38:   0bf5 0004       tst 4(r5)
  3c:   0204            bne 46 <_fun2+0x12>
  3e:   15c0 0005       mov $5, r0
  42:   1585            mov (sp)+, r5
  44:   0087            rts pc
  46:   15c0 0006       mov $6, r0
  4a:   1585            mov (sp)+, r5
  4c:   0087            rts pc

00000000 <fun0>:
   0:   00a03533            snez    x10,x10
   4:   0515                    addi    x10,x10,5
   6:   8082                    ret

00000008 <fun1>:
   8:   00a03533            snez    x10,x10
   c:   0515                    addi    x10,x10,5
   e:   8082                    ret

00000010 <fun2>:
  10:   00a03533            snez    x10,x10
  14:   0515                    addi    x10,x10,5
  16:   8082                    ret

и компиляторы

с этим кодом i можно было бы ожидать, что разные цели также будут совпадать

define i32 @fun0(i32 %condition, i32 %value) #0 {
  %1 = icmp ne i32 %condition, 0
  %. = select i1 %1, i32 6, i32 5
  ret i32 %.
}

; Function Attrs: norecurse nounwind readnone
define i32 @fun1(i32 %condition, i32 %value) #0 {
  %1 = icmp eq i32 %condition, 0
  %. = select i1 %1, i32 5, i32 6
  ret i32 %.
}

; Function Attrs: norecurse nounwind readnone
define i32 @fun2(i32 %condition, i32 %value) #0 {
  %1 = icmp ne i32 %condition, 0
  %2 = select i1 %1, i32 6, i32 5
  ret i32 %2
}


00000000 <fun0>:
   0:   e3a01005    mov r1, #5
   4:   e3500000    cmp r0, #0
   8:   13a01006    movne   r1, #6
   c:   e1a00001    mov r0, r1
  10:   e12fff1e    bx  lr

00000014 <fun1>:
  14:   e3a01006    mov r1, #6
  18:   e3500000    cmp r0, #0
  1c:   03a01005    moveq   r1, #5
  20:   e1a00001    mov r0, r1
  24:   e12fff1e    bx  lr

00000028 <fun2>:
  28:   e3a01005    mov r1, #5
  2c:   e3500000    cmp r0, #0
  30:   13a01006    movne   r1, #6
  34:   e1a00001    mov r0, r1
  38:   e12fff1e    bx  lr


fun0:
    push.w  r4
    mov.w   r1, r4
    mov.w   r15, r12
    mov.w   #6, r15
    cmp.w   #0, r12
    jne .LBB0_2
    mov.w   #5, r15
.LBB0_2:
    pop.w   r4
    ret

fun1:
    push.w  r4
    mov.w   r1, r4
    mov.w   r15, r12
    mov.w   #5, r15
    cmp.w   #0, r12
    jeq .LBB1_2
    mov.w   #6, r15
.LBB1_2:
    pop.w   r4
    ret


fun2:
    push.w  r4
    mov.w   r1, r4
    mov.w   r15, r12
    mov.w   #6, r15
    cmp.w   #0, r12
    jne .LBB2_2
    mov.w   #5, r15
.LBB2_2:
    pop.w   r4
    ret

Теперь технически существует разница в производительности в некоторых из этих решений, иногда результат 5, если перепрыгивают, результат равен 6 коду, и наоборот, ветвление быстрее, чем выполнение? можно спорить, но исполнение должно быть разным. Но это больше похоже на условие if против if not в коде, в результате чего компилятор выполняет if, этот переход через else выполняется. но это не обязательно из-за стиля кодирования, а из-за сравнения и случаев if и the else в любом синтаксисе.

Старожил
источник
0

Хорошо, поскольку сборка является одним из тегов, я просто предположу, что ваш код является псевдокодом (и не обязательно c), и переведу его человеком в сборку 6502.

1-й вариант (без остального)

        ldy #$00
        lda #$05
        dey
        bmi false
        lda #$06
false   brk

2-й вариант (с остальным)

        ldy #$00
        dey
        bmi else
        lda #$06
        sec
        bcs end
else    lda #$05
end     brk

Предположения: Условие находится в регистре Y, установите значение 0 или 1 в первой строке любого варианта, результат будет в аккумуляторе.

Итак, подсчитав циклы для обеих возможностей каждого случая, мы видим, что первая конструкция обычно быстрее; 9 циклов, если условие равно 0, и 10 циклов, если условие равно 1, тогда как второй вариант также составляет 9 циклов, когда условие равно 0, но 13 циклов, когда условие равно 1. (количество циклов не включает в себя BRKв конце ).

Вывод: If onlyбыстрее If-Elseпостроить.

И для полноты картины вот оптимизированное value = condition + 5решение:

ldy #$00
lda #$00
tya
adc #$05
brk

Это сокращает время до 8 циклов ( опять же, не считая BRKв конце ).

Глен Йейтс
источник
6
К сожалению для этого ответа, загрузка одного и того же исходного кода в компилятор C (или в компилятор C ++) дает совершенно другой результат, чем загрузка его в мозг Глена. Нет никакой разницы, никакого «оптимизационного» потенциала между любыми альтернативами на уровне исходного кода. Просто используйте наиболее читаемый (предположительно, if / else).
Quuxplusone
1
@Ага. Компилятор может либо оптимизировать оба варианта до самой быстрой версии, либо добавить дополнительные накладные расходы, которые намного перевешивают разницу между ними. Или оба.
jpaugh
1
Предположение, что это « не обязательно C », кажется разумным выбором, учитывая, что вопрос помечен как C ++ (к сожалению, не удается объявить типы задействованных переменных).
Тоби Спейт