Беседы о программировании 017 :: Функция abs(x) — абсолютное значение числа

Не менее важной чем sign(x) для целых чисел является функция взятия абсолютного значения abs(x). Существуют разные варианты реализации этой функции (как с ветвлениями, так и без них) и мы, как обычно, изучим их реальную стоимость. Ниже в статье излагается то же, что на видео.

Определение

На всякий случай введём определение функции абсолютного значения:

abs

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

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

Описание методов

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

Пусть T=u32. Пусть на вход подаётся значение a=-231=0x80000000. Тогда функция вернёт ему на выходе -a=231=0x80000000=-231. Возможно, что это не имеет смысла в большинстве программ, но ошибка возникнет, например, когда пользователь захочет сравнить два числа по абсолютному значению

В случае переполнения код будет работать неправильно, и далеко не каждый сходу заметит этот подвох. Именно поэтому я считаю, что на языке C++ НЕЛЬЗЯ делать такую функцию шаблоном с одним параметром. А делать нужно так, чтобы она получала на вход знаковое число, а выдавала ответ без знака. Согласен, что неудобно, но зато более безопасно. Именно так сделано в этой статье ниже для пары i32/u32.

Метод 0. Эталонный

Действуя по определению, можно состряпать простейшую функцию, не требующую специального комментария:

Традиционный недостаток функции: наличие ветвления.

Метод 1

Математик в первую очередь вспомнит, что модуль числа — это произведение числа на его знак. Знак мы вычислять уже научились в беседе 016, давайте воспользуемся этим знанием:

В качестве функции sign мы взяли самую быструю из предыдущей беседы.

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

Метод 2

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

neg_minus

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

В первой строке функции выполняется знаковый сдвиг. Как Вы знаете, знаковый сдвиг на архитектуре x86 дает 0, если число неотрицательное и -1, если отрицательное. Таким образом, если a неотрицательное, то b=0, а значит функция вернёт a.

Если же a отрицательное, то b=-1, значит функция вернёт (a-1)^(-1), а операция побитового исключающего или с числом -1=0xFFFFFFFF есть ни что иное как инвертирование битов. Согласитесь, красиво!

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

Метод 3

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

Очевидный недостаток — дополнительная операция отрицания числа, но ничего не поделаешь.

Метод 4

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

neg_plus

По аналогии с методом 2, получаем следующий код:

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

Метод 5

Переходя в предыдущем методе к беззнаковому сдвигу, имеем:

Сравнение

Самое интересное в подобных исследованиях — это разоблачение 🙂

Протестируем скорость работы этих функций. На вход подаются все числа из диапазона [-231, 231-1] и засекается время работы функций, а после вычитается время работы пустого цикла. Процессор Core 2 Duo E8400 @ 3ГГц. Компилятор VС++ 2015. Время указано в секундах. Смотрим таблицу (можно кликнуть на картинку для просмотра полного размера).

abs_time

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

Первые две функции — эталонные, одна из STL, вторая наша, написанная по определению (с ветвлением). Прошу сразу обратить внимание на то, что наша функция быстрее!

Далее идёт вариант с умножением, самый медленный из всех (ну что ж, он хотя бы попытался).

Дальше два варианта (методы 2 и 3), основанные на битовом трюке с «исключающим или» (символ  — это на самом деле ^). Первый со знаковым сдвигом, а второй с его беззнаковым аналогом. Последние две строки, соответственно, — это методы 4 и 5. Мы видим, что беззнаковый аналог хуже в обоих случаях. Также мы видим, что оба, казалось бы, одинаковых трюка работают с разной скоростью.

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

Давайте разбираться, в чём же дело. Изучим ассемблерные листинги. Сначала метод std::abs.

Операция cdq делает следующее. Берёт знак eax и копирует его во все биты регистра edx. То есть если eax отрицательный, то edx=-1, иначе edx=0. Дальше используется метод 4: то есть инвертирование и прибавление 1. Это красивое решение: вместо знакового сдвига мы можем получить -1 в регистре edx командой cdq, правда для этого нужно сначала поместить наше исходное число в регистр eax, но это мелочь, от которой в ряде случаев можно избавиться заблаговременно. Недостаток здесь в том, что все 4 команды опираются на eax, а значит тормозят, ожидая друг друга.

Смотрим на наш метод с ветвлениями:

Как видим, ветвление остаётся при компиляции и процессор выполняет либо  3, либо 4 команды. И странным образом такой код работает быстрее красивого трюка выше.

Смотрим на код метода 2.

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

Почему же метод 4, который основан на той же идее, что метод 2, работает так заметно медленнее? Давайте посмотрим:

А здесь 5 команд! Компилятор не сообразил, как сделать это в 4 строки, отсюда и замедление скорости.

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

Если вы учились программировать в конце 90-х или даже раньше, то у Вас, как и у меня, может быть некий «врожденный» страх перед ветвлениями и чрезвычайное недоверие к способностям компилятора. Так вот, спустя 20 лет многое изменилось и пора понять две простые вещи: (1) ветвление — это не всегда медленнее на настольной машине и (2) компилятор обычно умнее Вас в простых бытовых условиях (разумеется, «обычно» — это НЕ значит «всегда»). Пора менять стереотипы.

Работа над ошибками

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

abs_time_imp2

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

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

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

Источники

При подготовке статьи помимо собственного опыта я опирался на следующие два источника:

Compute the integer absolute value (abs) without branching

Optimized abs function

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

До новых встреч!