В статье приводится описание техники программирования без использования условных операторов. Такая техника позволяет минимизировать эффект ошибочного предсказания ветви процессора. Приводится сравнение скорости работы функций с условными операторами и без них.
Ключевые слова: условный оператор, предсказатель переходов, branch misprediction, бенчмарк, Си, ассемблер.
Введение
Внимательно посмотрев на таблицу 1 «задержек, которые должен знать каждый программист» [1] можно заметить строчку «Branch mispredict». Ошибочное предсказание ветви (branch mispredict) — это ситуация, когда процессор не смог угадать ветвь, по которой пойдет программа в условном переходе [2]. Если процессор не смог угадать ветвь, то ему требуется дополнительное время на удаление и загрузку инструкций (команд) для другой ветви. На это тратится какое-то время, в 5–10 раз большее, чем обращение к кешу L1 процессора.
Таблица 1
Задержки, которые должен знать каждый программист (часть)
|
L1 cache reference |
0.5 ns |
|
Branch mispredict |
5 ns |
|
L2 cache reference |
7 ns |
|
Mutex lock/unlock |
25 ns |
|
Main memory reference |
100 ns |
|
... |
... |
Если понимать, как работает ошибочное предсказание, то можно уменьшить количество условных переходов в программе и сильно оптимизировать ее работу по времени. Такой подход называется безусловным программированием (branchless programming). Подробнее о предсказателе переходов процессора можно прочитать в соответствующих источниках [3].
В этой статье будет продемонстрированы временные затраты программы на разрешение ошибочного предсказания, а также способы написания условий без условных переходов.
Простейший пример
Рассмотрим простейший пример, функция min():
Это обычный способ написания функции нахождения минимума на языке Си. Он понятен всем разработчикам. Но в нем существует условный оператор if, который, если верить таблице выше, может замедлить выполнение нашей программы. Напишем функцию min_branchless():
В данном случае мы используем особенность языка Си, которая позволяет преобразовать значение false в 0, а значение true в 1. Мы используем сумму произведений с взаимно-исключающими условиями, чтобы получить необходимый нам результат. Например a = 5 и b = 7, тогда выражение (a < b) будет равно 1, а выражение (b <= a) будет равно 0. Тогда итоговое выражение будет 1 * 5 + 0 * 7. Таким образом мы составили функцию нахождения минимума без операций условного перехода .
Проверим, какая из этих функций будет работать быстрее дизассемблировав их:
Важное замечание. Во время компиляции здесь и далее используются флаги оптимизации (для gcc -O2 например). Также сокращены адреса для повышения читаемости.
Видно, что операций в min_branchless() несколько больше, чем в min(). А в min() вообще нет операций условных переходов (таких как jg, je, jle и т. д.). Это связано с тем, что современные компиляторы достаточно умные, и могут понять, что в этой функции мы хотим найти минимум из двух чисел и используют соответствующую ассемблерную команду cmovg (выделено жирным).
В простейшем случае применение branchless программирования не позволит ускорить работу программы.
Пример с ускорением работы
Рассмотрим функцию, которая заменяет все строчные буквы на прописные — toUpper(). Обычная реализация этой функции выглядит следующим образом:
Поясним, что мы пишем программы на языке Си в котором строка представляется в виде участка памяти, разбитого на байты — отдельные ASCII символы, оканчивающиеся символом ‘\0’. Поэтому мы используем цикл по этому участку памяти for (; *str; ++str).
Поскольку символы имеют представление ASCII, то чтобы изменить регистр символа нужно добавить или вычесть к нему 32. Латинские буквы в ASCII таблице идут подряд и ‘A’ отличается от ‘a’ на 32 единицы.
Дизассемблировав эту функцию мы обнаружим условный переход переходов ja.
Время выполнения этой функции для строки размером 1024 случайных символа (небольшой размер, чтобы минимизировать влияние промахов кэша) четыре миллиона раз составляет примерно 21,9 секунд.
Изменим функцию to_upper() с применением принципов безусловного программирования:
В этой функции отказываемся от условного оператора if, но оставляем взаимоисключающие условия. Результат вычисления условий умножается на необходимый нам результат: на (*str — 32) если буква была строчной (т. е. делаем букву заглавной), или на (*str) т. е. на сам символ (т. е. символ не меняется).
Время выполнения этой функции условиях идентичных условиям из to_upper() составило 11,2 секунды, что в 2 раза быстрее первого варианта.
Функцию to_upper() можно ускорить еще больше:
Время выполнение этой версии функции составило 7,0 секунд, что примерно в 3 раза быстрее первого варианта.
Взглянув на дизассемблерный код to_upper_branchless2() можно увидеть, что там отсутствуют команды условных переходов:
Именно поэтому скорость выполнения этой функции выше, чем у той, где есть условные переходы.
Выводы
Очевидно, техника программирования без условных операторов позволяет значительно (в несколько раз) оптимизировать программу по скорости выполнения. Однако, этот способ программирования значительно усложняет восприятие программного кода, и не каждый программист поймет, что происходит в такой оптимизированной функции. Этот способ можно применять в программах критичных к времени выполнения, например высоконагруженных сервисах, или огромных научных вычислениях.
Литература:
- Jonas Bonér Latency Numbers Every Programmer Should Know — Текст: электронный // Текстовый документ на гит репозитории — URL: https://gist.github.com/jboner/2841832 (дата обращения 28.04.2021)
- Иерархия памяти. — Текст: электронный // Википедия свободная энциклопедия. — URL: https://computer_en_ru.academic.ru/4251/branch_misprediction (дата обращения 30.04.2021)
- Предсказатель переходов. — Текст: электронный // Википедия свободная энциклопедия. — URL: https://ru.wikipedia.org/wiki/Предсказатель_переходов (дата обращения 30.04.2021)
