Является ли < быстрее, чем <=?

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

Сравнение     Вычитание
----------     -----------
A < B      --> A - B < 0
A = B      --> A - B = 0
A > B      --> A - B > 0

Когда A < B, вычитание требует заимствования старшего бита для корректности результата, так же как мы переносим и занимаем при ручном сложении и вычитании. Этот "заимствованный" бит обычно называли битом переноса и его можно было проверять с помощью условной команды перехода. Второй бит, называемый нулевым битом, устанавливался в 1, если вычитание давало ноль, что указывало на равенство.

Обычно существовало как минимум две команды условного перехода: одна для перехода по биту переноса и одна по нулевому биту.

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

Сравнение     Вычитание  Бит переноса  Нулевой бит
----------     -----------  -----------  ---------
A < B      --> A - B < 0    0             0
A = B      --> A - B = 0    1             1
A > B      --> A - B > 0    1             0

Таким образом, реализация перехода для A < B может быть выполнена за одну команду, потому что бит переноса очищен только в этом случае, то есть,

;; Реализация "if (A < B) goto address;"
cmp  A, B          ;; сравниваем A с B
bcz  address       ;; Переход, если бит переноса равен нулю

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

;; Реализация "if (A <= B) goto address;"
cmp A, B           ;; сравниваем A с B
bcz address        ;; переход, если A < B
bzs address        ;; также, переход, если установлен нулевой бит

Таким образом, на некоторых машинах использование сравнения "меньше" может сэкономить одну машинную инструкцию. Это имело значение в эпоху процессоров с частотой ниже мегагерца и 1:1 соотношением скорость ЦПУ к памяти, но сегодня это почти полностью неактуально.

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

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

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

Для случая с константами, когда вы используете if (a < 901) или if (a <= 901), компилятор генерирует следующие инструкции:

cmpl  $900, -4(%rbp)
jg .L2

и

cmpl  $901, -4(%rbp)
jg .L3

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

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

cmpl  -4(%rbp), %eax
jge   .L2

и

cmpl  -4(%rbp), %eax
jg .L3

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

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

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

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 - побитовая операция OR для регистра условий), чтобы объединить эти два бита в один. Таким образом, compare_loose требует уже пять инструкций, в то время как compare_strict — четыре.

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

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

Однако это неверно обрабатывает NaN. Сравнения NaN1 <= NaN2 и NaN1 > NaN2 должны оба возвращать false.

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

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