Техника оптимизации под линуха

Избавление от ветвлений


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

Рассмотрим функцию поиска максимума среди двух целых чисел: "((a>b)?a:b)", для наглядности записанную так: "if(a<b) a=b;". Как избавиться от ветвления? В этом нам поможет машинная команда SBB, реализующая вычитание с заемом. На языке ассемблера это могло бы выглядеть, например, так:

SUB b, a

; отнять от содержимого 'b' значение 'a', записав результат в 'b'

; если a > b, то процессор установит флаг заема в единицу

SBB c, c

; отнять от содержимого 'c' значение 'c' с учетом флага заема,

; записав результат обратно в 'c' ('c' - временная переменная)

; Если a <= b, то флаг заема сброшен, и 'c' будет равно 0,

; Если a > b, то флаг заема установлен и 'c' будет равно -1.

AND c, b

; выполнить битовую операцию (c & b), записав результат в 'c'

; Если a <= b, то флаг заема равен нулю, 'c' равно 0,

; значит, с =(c & b) == 0, в противном случае: c == b - a

;

ADD a, c

; выполнить сложение содержимого 'a' со значением 'c', записав

; результат в 'a'.

; если a <= b, то c = 0 и a = a

; если a > b, то c = b - a, и a = a + (b-a) == b



Содержание раздела