Беседы о программировании 016 :: Функция sign(x) — определение знака переменной

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

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

Для начала определимся с понятиями, чтобы мы с Вами говорили об одном и том же.

Знак числа x определяется следующим образом:

sign

Конечно, существуют варианты задач, в которых нам нужно другое определение знака, скажем, из двух значений: 0 (если значение x неотрицательное) и 1 (если отрицательное). Подобное определение знака используется, например, в формате IEEE-754. Но мы будем рассматривать именно такой знак, как мы определили выше, то есть из трёх значений.

Прежде чем я покажу реализации всех известных мне функций, определимся с некоторыми типами и константой SHIFT:

Во многих функциях будет использоваться сдвиг на 31 бит, поэтому я и завёл константу SHIFT, как того требуют правила хорошего тона. Я опишу функции только применительно к типу данных размером 32 бита со знаком (i32).

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

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

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

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

Несомненным преимуществом такой функции будет её переносимость и простота — здесь очень трудно ошибиться.

Метод 1

Можно использовать трюк, который позволителен в языке Си, когда результат вычисления логического выражение может быть приравнен к числу 0 или 1. Это позволит получить красивый код:

Комментарии здесь излишни, просто проверьте вручную, что будет, если поставить вместо a какое-либо число.

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

Метод 2

Я решил выделить этот метод отдельно, потому что он хоть и похож на предыдущий, но всё равно отличается, а поэтому требует отдельного тестирования, которое будет выполнено ниже в сводной таблице. Суть та же, но вдруг разница в скорости будет? Мы же не знаем наверняка. Помня о невероятной кривизне процессора Intel, в котором операции типа inc ecx могут работать заметно дольше чем lea ecx, [ecx+1] (см. Беседу 008 про сложение векторов), у меня нет уверенности, что условные переходы работают одинаково быстро. Вдруг получится, что одно сравнение заметно дольше другого?

Метод 3

Принцип работы этого метода следующий. Если a=0, то слева и справа от побитового «или» будет 0, в итоге ответ будет 0, что и требуется. Если же а не равно нулю, то слева будет 1, а справа всё зависит от знака a. Если a>0, то сдвиг на 31 бит даст 0, поэтому итог всего выражения будет равен 1. Если а<0, то беззнаковый сдвиг даст 1, а последующее отрицание даст -1 = 0xFFFFFFFF. В итоге ответ будет -1.

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

Опытный программист заметит, что нет смысла в этом нагромождении преобразований к беззнаковому типу и обратно с отрицанием — и он будет отчасти прав.

Метод 4

Здесь всё точно так же, но сдвиг справа является знаковым. Опасность такого подхода в том, что он является машинно-зависимым. Дело в том, что в архитектуре x86 знаковый сдвиг вправо выполняется с копированием старшего сдвигаемого бита на старшую позицию, именно поэтому сдвиг на 31 любого отрицательного числа даст -1, а любого положительного — 0. Однако в некоторых других архитектурах подобная операция может работать иначе, или её вообще может не существовать. Используйте данный трюк осторожно.

Метод 5

Наконец-то вариант без ветвлений!

Принцип работы следующий. Слева от побитового «или» тот же знаковый сдвиг, что в предыдущем трюке, он даст либо 0, либо -1 в зависимости от того, неотрицательное число или отрицательное. Справа выполняется беззнаковый сдвиг отрицания a. Если a>0, то слева и справа получим единицу (общий ответ 1), если a<0, то слева -1, а справа 0 (общий ответ -1). В случае a=0, очевидно, всё тоже работает.

Данный метод также является машинно-зависимым.

Метод 6

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

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

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

sign_time

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

Я разбил функции на блоки. Первая — это наша эталонная функция с двумя сравнениями. Далее идут две «красивые» функции с двумя сравнениями и вычитанием, затем две функции с одним сравнением, а затем две без ветвлений. Итак, вывод нас удивляет, на моём процессоре самая тривиальная реализация «в лоб» оказалась заметно быстрее остальных. Остальные же отличаются друг от друга потому, что знаковый и беззнаковый сдвиг имеют разную эффективность (на моём процессоре).

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

Вот последняя, функция, которая без ветвлений. Привожу её код ещё раз, а затем листинг на ассемблере с моими пояснениями.

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

Теперь посмотрим на код функции sign0.

Мы видим либо 4, либо 5 команд в зависимости от ветки, по которой пойдёт исполнение. Заметьте, что прыжок будет только один, а второе ветвление хитро заменено командой setg, которая установит 1 в том случае, когда команда test показала положительное значение в ecx. Данная команда даёт 1, когда флаг нуля равен 0 и флаг знака равен флагу переполнения. Это не совсем прямое использование команды setg, но согласитесь, красиво!

Видимо, более короткая программа исполняется быстрее потому, что обе в общем-то имеют зависимости соседних команд, значит где команд меньше, там и скорость больше. Это ИМХО, потому что я плохо понимаю микроархитектуру процессоров Intel (скажу правду, вообще не понимаю) и не могу определить, откуда такие тормоза.

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

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

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

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

abs_time_imp

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

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

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