Беседы о программировании 019 :: Функции min(a,b) и max(a,b) для чисел со знаком

Здесь рассматриваются функции определения минимума и максимума из двух чисел со знаком. Приводится 7 реализаций как с ветвлениями, так и без них, как для общего случая, так и для некоторых частных случаев. Код программ приведён для случая 32-битовых чисел. В конце выполнено сравнение всех функций между собой и обнаружено забавное свойство операции сравнения. Текст статьи полностью повторяет содержание видеозаписи.

Определение

Функции минимума и максимума двух чисел едва ли нуждаются в определении, но для полноты картины я всё-таки их приведу. С них начинается обзор алгоритмов вычисления данных функций.

min

max

В приводимых ниже фрагментах кода используются следующие псевдонимы и константа SHIFT:

Помимо описанных ниже алгоритмов, будем также тестировать std::min и std::max из STL.

Алгоритмы

Метод 0. Классический

Данный метод работает по математическому определению функций и едва ли требует каких-то пояснений.

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

Метод 1

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

Этот код основан на свойстве операции xor, если a<b, то -(a<b) даст число -1=0xFFFFFFFF, таким образом, (a^b)&(-1) = a^b. Поэтому в случае минимума функция вернёт b^a^b=a. Если же a>=b, то -(a<b)=0. Поэтому (a^b)&0 = 0 и функция вернёт b^0=b. В случае максимума всё аналогично.

Недостаток функции по сравнению с предыдущим методом очевиден: кроме ветвления здесь ещё 4 операции. Даже с точки зрения эстетики всё плохо — функция более длинная и запутанная.

Функция doz(a,b) — difference or zero

Следующая серия методов основана на функции doz(a,b), которая определяется следующим образом:

doz

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

Вычислив doz(a,b), можно теперь определить минимум и максимум:

min_max_doz

Теперь всё зависит от того, как мы реализуем функцию doz(a,b). Следующие 4 метода покажут 4 варианта её реализации.

Метод 2

Функцию doz(a,b) можно вычислить по её определению.

Обратите внимание, возвращается число без знака. Функция названа doz2, потому что она будет относится ко второму методу вычисления минимума и максимума (в нашей сплошной нумерации методов).

Метод 3

Аналогично методу 1 для min и max, можно смешать логические и арифметические операции.

Очевидно, что когда a>=b, справа от побитового И будет (-1), поэтому в результате функция вернёт a-b. В случае нарушения условия, справа будет 0 и функция вернёт 0.

Метод 4

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

Жуткого вида формула становится менее страшной, если её записать в более привычном виде:

doz_bf

К сожалению, даже в таком виде принцип её работы не очевиден. Поэтому сейчас будет краткое объяснение, которое вы сами сможете довести до математической строгости, если это будет необходимо.

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

В больших круглых скобках у нас побитовое И,  слева от которого a^b, справа d^a. Отсюда сразу получаем первый случай.

Первый случай. Числа a и b имеют одинаковый знак. При вычислении d=a-b переполнение невозможно (поэтому знак d соответствует знаку a-b). В этом случае a^b даёт ноль в старшем бите и вся наша операция И в скобках будет давать 0 (в старшем бите). В итоге вся формула выродится в такую: d&[~d>>SHIFT]. Здесь всё очевидно: если d>=0, то оно и вернётся в качестве ответа, если d<0, то будет возвращён 0.

Все остальные элементы формулы нужны для того, чтобы учесть переполнение знаковой переменной при  вычислении d=a-b. Может оказаться, что знак d будет не совпадать со знаком реальной разности a-b из-за переполнения.

Второй случай. Переменные a и b имеют разные знаки. Слева от внутреннего побитового И у нас всегда 1 в старшем бите. Справа может быть 4 случая, которые нужно аккуратно рассмотреть отдельно.

  1. a-b>=0 И a>=0 И b<0. Выражение в квадратных скобках даст (-1), поэтому функция вернёт d. И действительно, при этих условиях a>=b.
  2. a-b<0 И a>=0 И b<0. Выражение в квадратных скобках даст (-1), поэтому функция вернёт d. И действительно, при этих условиях a>=b, но при вычитании имело место переполнение.
  3. a-b>=0 И a<0 И b>=0. Выражение в квадратных скобках даст 0, поэтому функция вернёт 0. И действительно, при этих условиях a<b, но при вычитании имело место переполнение.
  4. a-b<0 И a<0 И b>=0. Выражение в квадратных скобках даст 0, поэтому функция вернёт 0. И действительно, при этих условиях a<b.

Таким образом, рассмотрев все случаи, мы приходим к выводу, что функция возвращает d, когда a>=b (не зависимо от того, было ли переполнение, ведь возвращаем-то мы число без знака) и возвращает 0, когда a<b.

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

Метод 5

Данный метод будет работать только в том случае, когда при вычислении d=a-b переполнение знакового типа не возникает. Это частный случай предыдущего метода (см. первый случай в его описании).

Недостаток метода (помимо машинной зависимости от знакового сдвига) очевиден: он работает не всегда.

Метод 6

Данный метод основан на ещё одном математическом определении максимального и минимального значения:

min_max_abs

Для взятия модуля можно воспользоваться одной из функций из этой статьи.

Для правильной работы функций, написанных по такому определению, необходимо, чтобы a-b и a+b не покидали пределы знакового диапазона целых чисел, в рамках которых выполняются расчёты.

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

Сравнение скорости

Процессор Core 2 Duo E8400 @ 3ГГц. Компилятор VС++ 2015. Время указано в секундах. Для измерения времени через наши функции прогонялось 232 пар чисел.

Compare_min_max

В первой строке функции std::min и std::max из STL. Четвёртый метод я специально выделил особо — это функция без операций сравнения (помните ту страшную формулу?).

Во-первых, бросается в глаза очевидный недостаток метода 6. Во-вторых, очевидным недостатком обладают и все остальные методы — они «сливают» по полной программе самому простому методу с явным сравнением.

В-третьих, почему-то наш метод «ноль», написанный по определению, проигрывает функции из стандартной библиотеки, написанной почти один-в-один. И вот это «почти»… Давайте смотреть ассемблерный код?

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

Здесь не случайно выполняется сложение (чтобы компилятор не удалил цикл, переменная s затем выводится на экран). Откомментировав то одну, то другую строку, я замеряю время работы цикла, затем вычитаю из него время работы пустого цикла.

Итак, вот листинг, в котором включена только min0:

Обратите внимание, как я и обещал, нет здесь никакого ветвления. Инструкция cmovl выполняет условное перемещение в зависимости от состояния регистра флагов, а он зависит от команды cmp выше по коду.

Вот листинг, в котором включена только std::min:

Вы видите разницу? Основная разница в том, что в первом случае сравнивается a и b, а во втором наоборот, b и а. Вот и всё. Перестановка инструкций на таком коротком промежутке роли играть не должна, процессор переставляет их «на лету» сам в пределах конвейера. Самое время задать вопрос: WTF???

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

Что ж, давайте поможем компилятору и чуть подправим нашу функцию сравнения. Было:

Стало:

Мы поменяли знаки «>» на «<» в min и наоборот в max. Теперь таблица сравнения стала такой, какой она и должна быть:

Compare_min_max_imp

Вот такая забавная ситуация, меняя знаки «больше» на «меньше» и наоборот, мы получаем разницу в скорости в полтора раза. Кто бы мог подумать…

Вывод

На самом деле вывод к этому эксперименту уже сформулировал в XI веке персидский поэт, философ и математик Омар Хайям:

Все, что видим мы, видимость только одна.
Далеко от поверхности моря до дна.
Полагай несущественным явное в мире,
Ибо тайная сущность вещей не видна.

Как в воду глядел…