Вопрос: Является <быстрее, чем <=?


Я читаю книгу, в которой автор говорит, что if( a < 901 )быстрее, чем if( a <= 900 ),

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


1362


источник


Ответы:


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

  • testили cmpинструкция, которая устанавливает EFLAGS
  • И Jcc(прыжок) , в зависимости от типа сравнения (и макета кода):
    • jne- Перейти, если не равна -> ZF = 0
    • jz- Перейти, если ноль (равный) -> ZF = 1
    • jg- Перейти, если больше -> ZF = 0 and SF = OF
    • (и т.д...)

пример (Отредактировано для краткости) Составлено с $ gcc -m32 -S -masm=intel test.c

    if (a < b) {
        // Do something 1
    }

Скомпилирует:

    mov     eax, DWORD PTR [esp+24]      ; a
    cmp     eax, DWORD PTR [esp+28]      ; b
    jge     .L2                          ; jump if a is >= b
    ; Do something 1
.L2:

А также

    if (a <= b) {
        // Do something 2
    }

Скомпилирует:

    mov     eax, DWORD PTR [esp+24]      ; a
    cmp     eax, DWORD PTR [esp+28]      ; b
    jg      .L5                          ; jump if a is > b
    ; Do something 2
.L5:

Таким образом, единственное различие между этими двумя jgпротив jgeинструкция. Эти два будут занимать одинаковое количество времени.


Я хотел бы обратиться к комментарию, что ничто не указывает на то, что разные инструкции перехода требуют одинакового количества времени. Это немного сложно ответить, но вот что я могу дать: в Справочник по набору инструкций Intel , все они сгруппированы по одной общей инструкции, Jcc(Перейти, если условие выполнено). Та же группировка составлена ​​под Справочное руководство по оптимизации , в Приложении C. Задержка и пропускная способность.

Задержка - Количество тактовых циклов, которые необходимы для   ядро выполнения для завершения выполнения всех μops, которые формируют   инструкции.

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

Значения для Jccнаходятся:

      Latency   Throughput
Jcc     N/A        0.5

со следующей сноской Jcc:

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

Итак, ничто в документах Intel никогда не рассматривает один Jccинструкции иначе, чем другие.

Если кто-то думает о фактической схеме, используемой для реализации инструкций, можно предположить, что на разных битах были бы простые логические элементы AND / OR EFLAGS, чтобы определить, выполнены ли условия. Тогда нет причин, по которым команда, тестирующая два бита, должна занимать больше или меньше времени, чем одно тестирование только одного (Игнорирование задержки распространения затвора, которое намного меньше, чем период синхронизации).


Изменить: плавающая точка

Это справедливо и для x87 с плавающей запятой: (Почти такой же код, как и выше, но с doubleвместо int.)

        fld     QWORD PTR [esp+32]
        fld     QWORD PTR [esp+40]
        fucomip st, st(1)              ; Compare ST(0) and ST(1), and set CF, PF, ZF in EFLAGS
        fstp    st(0)
        seta    al                     ; Set al if above (CF=0 and ZF=0).
        test    al, al
        je      .L2
        ; Do something 1
.L2:

        fld     QWORD PTR [esp+32]
        fld     QWORD PTR [esp+40]
        fucomip st, st(1)              ; (same thing as above)
        fstp    st(0)
        setae   al                     ; Set al if above or equal (CF=0).
        test    al, al
        je      .L5
        ; Do something 2
.L5:
        leave
        ret

1559



Исторически (мы говорим о 1980-х и начале 1990-х годов), некоторые архитектуры, в которых это было правдой. Корневая проблема заключается в том, что целочисленное сравнение реализуется посредством целочисленных вычитаний. Это приводит к следующим случаям.

Comparison     Subtraction
----------     -----------
A < B      --> A - B < 0
A = B      --> A - B = 0
A > B      --> A - B > 0

Теперь, когда A < Bвычитание должно занять высокий бит для правильного вычитания, так же, как вы переносите и занимаете при добавлении и вычитании вручную. Этот «заимствованный» бит обычно назывался бит переноса и будет проверяться инструкцией о ветвлении. Второй бит называется нулевой бит если бы вычитание было тождественно равным нулю, что подразумевало равенство.

Как правило, по меньшей мере две условные инструкции ветвления, одна для ветвления на переносном бите и одна на нулевом бите.

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

Comparison     Subtraction  Carry Bit  Zero Bit
----------     -----------  ---------  --------
A < B      --> A - B < 0    0          0
A = B      --> A - B = 0    1          1
A > B      --> A - B > 0    1          0

Итак, внедрение ветви для A < Bможет выполняться в одной инструкции, поскольку бит переноса является понятным только в этом случае, т. е.

;; Implementation of "if (A < B) goto address;"
cmp  A, B          ;; compare A to B
bcz  address       ;; Branch if Carry is Zero to the new address

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

;; Implementation of "if (A <= B) goto address;"
cmp A, B           ;; compare A to B
bcz address        ;; branch if A < B
bzs address        ;; also, Branch if the Zero bit is Set

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


551



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

Если бы была какая-то платформа, где <был быстрее, чем <=для простых целых типов компилятор должен всегда конвертировать <=в <для констант. Любой компилятор, который не просто был бы плохим компилятором (для этой платформы).


83



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

if(a < 901)
cmpl  $900, -4(%rbp)
jg .L2

if(a <=901)
cmpl  $901, -4(%rbp)
jg .L3

Мой пример ifот GCC на платформе x86_64 в Linux.

Авторы-компиляторы - довольно умные люди, и они думают об этих вещах, и многие другие большинство из нас воспринимают как должное.

Я заметил, что если он не является константой, то тот же машинный код генерируется в любом случае.

int b;
if(a < b)
cmpl  -4(%rbp), %eax
jge   .L2

if(a <=b)
cmpl  -4(%rbp), %eax
jg .L3

66



Для кода с плавающей запятой <= сравнение действительно может быть медленнее (по одной инструкции) даже на современных архитектурах. Вот первая функция:

int compare_strict(double a, double b) { return a < b; }

В PowerPC сначала выполняется сравнение с плавающей запятой (какие обновления cr, регистр условий), затем переводит регистр условий в GPR, сдвигает бит «сравнивается меньше», а затем возвращается. Требуется четыре инструкции.

Теперь рассмотрим эту функцию:

int compare_loose(double a, double b) { return a <= b; }

Это требует той же работы, что и compare_strictвыше, но теперь есть две части интереса: «было меньше» и «было равно». Для этого требуется дополнительная инструкция ( cror- регистр условия побитовое ИЛИ), чтобы объединить эти два бита в один. Так compare_looseтребуется пять инструкций, тогда как compare_strictтребуется четыре.

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

int compare_loose(double a, double b) { return ! (a > b); }

Однако это неправильно обрабатывает NaN. NaN1 <= NaN2а также NaN1 > NaN2необходимо, чтобы оба оценивали значение false.


48



Возможно, автор этой неназванной книги прочитал, что a > 0работает быстрее, чем a >= 1и думает, что это верно повсеместно.

Но это связано с тем, что 0(потому что CMPможет, в зависимости от архитектуры, заменить, например. с OR), а не из-за <,


34



At the very least, if this were true a compiler could trivially optimise a <= b to !(a > b), and so even if the comparison itself were actually slower, with all but the most naive compiler you would not notice a difference.


29



They have the same speed. Maybe in some special architecture what he/she said is right, but in the x86 family at least I know they are the same. Because for doing this the CPU will do a substraction (a - b) and then check the flags of the flag register. Two bits of that register are called ZF (zero Flag) and SF (sign flag), and it is done in one cycle, because it will do it with one mask operation.


15