Является ли if( a < 901 )быстрееif( a <= 900 ) .

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

Нет, это не будет быстрее на большинстве архитектур. Вы не указали, но на 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. Задержка и пропускная способность.

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

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

Значения для Jcc:

      Latency   Throughput
Jcc     N/A        0.5

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

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

Таким образом, ничто в документах Intel никогда не рассматривает одну Jccинструкцию в отличие от других.

Если задуматься о фактической схеме, используемой для реализации инструкций, можно предположить, что в разных битах будут простые вентили И / ИЛИ 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

Исторически (мы говорим о 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, но сегодня это практически не имеет значения.

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

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

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

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

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

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нужно оба оценить как ложное.

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

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

По крайней мере, если бы это было так, компилятор мог бы тривиально оптимизировать a <= b к! (A> b), и поэтому даже если бы само сравнение было на самом деле медленнее со всеми, кроме самого наивного компилятора, вы бы не заметили разницу ,

У них одинаковая скорость. Возможно, в какой-то особой архитектуре то, что он / она сказал, правильно, но, по крайней мере, в семействе x86 я знаю, что они одинаковы. Потому что для этого ЦП выполнит вычитание (a - b), а затем проверит флаги регистра флага. Два бита этого регистра называются ZF (нулевой флаг) и SF (знаковый флаг), и это делается за один цикл, потому что он будет делать это с одной операцией маски.

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

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

TL; DR ответ

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

Полный ответ

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

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

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

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

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

Вы не должны быть в состоянии заметить разницу, даже если она есть. Кроме того, на практике вам придется выполнить дополнительное условие a + 1или a - 1выполнить условие, если вы не собираетесь использовать магические константы, что во всех отношениях является очень плохой практикой.

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

Когда я писал этот ответ, я смотрел только на титульный вопрос о <против <= в целом, а не конкретный пример постоянного a < 901VS. a <= 900. Многие компиляторы всегда уменьшают величину констант путем преобразования между <и <=, например, потому что непосредственный операнд x86 имеет более короткую 1-байтовую кодировку для -128..127.

Для ARM и особенно для AArch64 возможность кодирования как непосредственного зависит от возможности поворота узкого поля в любую позицию в слове. Так cmp w0, #0x00f000что будет закодировано, а cmp w0, #0x00effffможет и не быть. Таким образом, правило «сделай это меньше» для сравнения с константой времени компиляции не всегда применимо к AArch64.

<vs. <= в целом, в том числе для переменных во время выполнения

На языке ассемблера на большинстве машин сравнение для <=имеет такую ​​же стоимость, что и сравнение <. Это применимо, независимо от того, ветвитесь ли вы на нем, логизируете его для создания целого числа 0/1 или используете его в качестве предиката для операции выбора без ответвлений (например, CMOV x86). Другие ответы касались только этой части вопроса.

Но этот вопрос касается операторов C ++, входных данных для оптимизатора. Обычно они оба одинаково эффективны; совет из книги звучит совершенно фиктивно, потому что компиляторы всегда могут преобразовать сравнение, которое они реализуют в asm. Но есть по крайней мере одно исключение, когда использование <=может случайно создать что-то, что компилятор не может оптимизировать.

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

Неподписанное переполнение четко определено как перестановка по основанию 2, в отличие от подписанного переполнения (UB). Счетчики циклов со знаком, как правило, защищены от этого, поскольку компиляторы, которые оптимизируют на основе UB со знаком переполнения, не происходят: ++i <= sizeвсегда в конечном итоге становятся ложными. ( Что должен знать каждый программист на C о неопределенном поведении )

void foo(unsigned size) {
    unsigned upper_bound = size - 1;  // or any calculation that could produce UINT_MAX
    for(unsigned i=0 ; i <= upper_bound ; i++)
        ...

Компиляторы могут оптимизировать только таким образом, чтобы сохранить (определенное и юридически наблюдаемое) поведение источника C ++ для всех возможных входных значений , кроме тех, которые приводят к неопределенному поведению.

(Простое i <= sizeтоже создало бы проблему, но я подумал, что вычисление верхней границы было более реалистичным примером случайного введения возможности бесконечного цикла для ввода, который вас не волнует, но который должен учитывать компилятор.)

В этом случае size=0приводит к upper_bound=UINT_MAXи i <= UINT_MAXвсегда верно. Так что этот цикл бесконечен size=0, и компилятор должен учитывать это, даже если вы, как программист, вероятно, никогда не намереваетесь передать size = 0. Если компилятор может встроить эту функцию в вызывающую функцию, где он может доказать, что size = 0 невозможен, то это здорово, он может оптимизировать так, как мог бы i < size.

Asm like if(!size) skip the loop; do{...}while(--size);- это один обычно эффективный способ оптимизировать for( i<size )цикл, если фактическое значение iвнутри цикла не требуется ( почему циклы всегда компилируются в стиле "do ... while" (прыжок в хвост)? ).

Но это делает {}, хотя не может быть бесконечным: если введено с size==0, мы получаем 2 ^ n итераций. ( Итерация по всем целым числам без знака в цикле for C позволяет выразить цикл по всем целым числам без знака, включая ноль, но без флага переноса это непросто, как в asm.)

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

Пример: сумма целых чисел от 1 до n

Использование неподписанных i <= nпоражений распознавания идиома clang, которая оптимизирует sum(1 .. n)петли с замкнутой формой на основе n * (n+1) / 2формулы Гаусса .

unsigned sum_1_to_n_finite(unsigned n) {
    unsigned total = 0;
    for (unsigned i = 0 ; i < n+1 ; ++i)
        total += i;
    return total;
}

x86-64 asm из clang7.0 и gcc8.2 в проводнике компилятора Godbolt

 # clang7.0 -O3 closed-form
    cmp     edi, -1       # n passed in EDI: x86-64 System V calling convention
    je      .LBB1_1       # if (n == UINT_MAX) return 0;  // C++ loop runs 0 times
          # else fall through into the closed-form calc
    mov     ecx, edi         # zero-extend n into RCX
    lea     eax, [rdi - 1]   # n-1
    imul    rax, rcx         # n * (n-1)             # 64-bit
    shr     rax              # n * (n-1) / 2
    add     eax, edi         # n + (stuff / 2) = n * (n+1) / 2   # truncated to 32-bit
    ret          # computed without possible overflow of the product before right shifting
.LBB1_1:
    xor     eax, eax
    ret

Но для наивной версии мы просто получаем тупую петлю от лязга.

unsigned sum_1_to_n_naive(unsigned n) {
    unsigned total = 0;
    for (unsigned i = 0 ; i<=n ; ++i)
        total += i;
    return total;
}

# clang7.0 -O3
sum_1_to_n(unsigned int):
    xor     ecx, ecx           # i = 0
    xor     eax, eax           # retval = 0
.LBB0_1:                       # do {
    add     eax, ecx             # retval += i
    add     ecx, 1               # ++1
    cmp     ecx, edi
    jbe     .LBB0_1            # } while( i<n );
    ret

GCC в любом случае не использует замкнутую форму, поэтому выбор условия цикла на самом деле не повредит ; он автоматически векторизуется с добавлением целых чисел SIMD, выполняя 4 iзначения параллельно в элементах регистра XMM.

# "naive" inner loop
.L3:
    add     eax, 1       # do {
    paddd   xmm0, xmm1    # vect_total_4.6, vect_vec_iv_.5
    paddd   xmm1, xmm2    # vect_vec_iv_.5, tmp114
    cmp     edx, eax      # bnd.1, ivtmp.14     # bound and induction-variable tmp, I think.
    ja      .L3 #,       # }while( n > i )

 "finite" inner loop
  # before the loop:
  # xmm0 = 0 = totals
  # xmm1 = {0,1,2,3} = i
  # xmm2 = set1_epi32(4)
 .L13:                # do {
    add     eax, 1       # i++
    paddd   xmm0, xmm1    # total[0..3] += i[0..3]
    paddd   xmm1, xmm2    # i[0..3] += 4
    cmp     eax, edx
    jne     .L13      # }while( i != upper_limit );

     then horizontal sum xmm0
     and peeled cleanup for the last n%3 iterations, or something.

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

Кстати, оба этих цикла тратят впустую инструкцию (и моп на процессорах семейства Sandybridge) на издержки цикла. sub eax,1/ jnzвместо add eax,1/ cmp / jcc будет более эффективным. 1 моп вместо 2 (после макро-слияния sub / jcc или cmp / jcc). Код после обоих циклов безоговорочно записывает EAX, поэтому он не использует окончательное значение счетчика цикла.

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

Каждое сравнение ( >= <= > <) может быть сделано с той же скоростью.

То, что каждое сравнение, это просто вычитание (разница) и проверка, является ли оно положительным / отрицательным.
(Если msbустановлено, число является отрицательным)

Как проверить a >= b? Sub a-b >= 0Проверьте, если a-bположительный.
Как проверить a <= b? Sub 0 <= b-aПроверьте, если b-aположительный.
Как проверить a < b? Sub a-b < 0Check, если a-bотрицательный.
Как проверить a > b? Sub 0 > b-aCheck, если b-aотрицательный.

Проще говоря, компьютер может просто сделать это под капотом для данной операции:

a >= b== msb(a-b)==0
a <= b== msb(b-a)==0
a > b== msb(b-a)==1
a < b==msb(a-b)==1

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

Во всяком случае, они наверняка не были a >= bбы рассчитаны как a>b || a==bLOL