Модуль, минимум и выбор без if: маска из знакового бита

Если ты получишь маску из знака числа, запишешь через неё модуль и минимум, объяснишь, почему отсортированный массив иногда обрабатывается быстрее того же несортированного, - листай до «Теперь сам».

Как думаешь, зависит ли скорость суммы от порядка чисел

В массиве две тысячи чисел от 0 до 255. Программа складывает те из них, которые не меньше 128: цикл, внутри if. Один и тот же массив обрабатывают дважды: в случайном порядке и отсортированным.

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

На что это похоже

Стрелочник на железнодорожной развилке. Поезд не останавливается перед стрелкой: стрелочник заранее ставит её так, как, по его опыту, поедет следующий поезд. Угадал - поезд проходит на полной скорости. Не угадал - поезд тормозит, сдаёт назад и идёт по другому пути.

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

Механизм: предсказатель, маска и три формулы

Процессор начинает выполнять следующие команды раньше, чем закончил текущую. Условный переход - так на уровне процессора выглядит if или проверка цикла. Перед ним процессор не знает, куда пойдёт программа, и угадывает - этим занят предсказатель переходов. Ошибка стоит дорого: начатые команды выбрасываются, это 15-20 тактов, а такт - время одного сложения.

Способ не угадывать - не ветвиться. Для этого условие превращают в число.

x >= 0:   x >> 31  =  0000 … 0000  =  0
x <  0:   x >> 31  =  1111 … 1111  = −1        арифметический сдвиг копирует знаковый бит во все разряды

Маска m - либо все нули, либо все единицы, и дальше она работает как выключатель: y & m - это либо ноль, либо y.

Модуль. Для отрицательного x нужно -x = ~x + 1. x ^ m при m = −1 переворачивает все биты, при m = 0 ничего не делает. Вычитание m при m = −1 прибавляет единицу, при m = 0 - ничего. Получается (x ^ m) - m: одна формула на оба случая.

Минимум. Маска делается из знака разности: m = (a - b) >> 31. Если a < b, маска включена и b + (a - b) даёт a; иначе выключена и остаётся b.

Выбор. b ^ ((a ^ b) & m): при выключенной маске это b, при включённой - b ^ a ^ b, то есть a. Маску из условия, которое равно 0 или 1, получают минусом: -0 = 0, -1 - все единицы.

Правило

Для 32-битного x со знаком маска m = x >> 31 равна 0 при x ≥ 0 и −1 при x < 0. Модуль: (x ^ m) - m при x ≠ −2³¹: модуль −2³¹ не помещается в тот же знаковый тип. Минимум: b + ((a - b) & m), где m = (a - b) >> 31. Выбор: b ^ ((a ^ b) & m) даёт a при m = −1 и b при m = 0. Формулы с разностью верны, пока a − b не переполняется.

Разбор: четыре функции без единого if

def modul(x):
    m = x >> 31
    return (x ^ m) - m

def minimum(a, b):
    m = a - b >> 31
    return b + (a - b & m)

def znak(x):
    return x >> 31 | -x >> 31 & 1

def vybor(usl, a, b):
    m = -usl
    return b ^ (a ^ b) & m

print(modul(-17), modul(17), minimum(3, 8), minimum(8, 3), minimum(-5, 2))
print(znak(-9), znak(0), znak(9), vybor(1, 10, 20), vybor(0, 10, 20))

17 17 3 3 -5
-1 0 1 10 20

Проследи modul(-17). Маска −1. -17 ^ -1 - переворот всех битов, это ~(-17) = 16. Минус маска: 16 − (−1) = 17. Для положительного 17 маска ноль, и обе операции ничего не меняют.

znak собран из двух масок. x >> 31 даёт −1 для отрицательных. -x >> 31 & 1 даёт единицу для положительных: у них отрицательно -x. Для нуля обе части нулевые. Порядок действий: & сильнее |, а сдвиг сильнее обоих.

Разбор: сколько раз ошибается предсказатель, и где приём не нужен

Простейший предсказатель - счётчик из двух битов на каждый переход: значения 0 и 1 означают «думаю, не выполнится», 2 и 3 - «думаю, выполнится»; после каждого перехода счётчик меняется на единицу в сторону того, что произошло. Смоделируем его на сумме из начала урока; dannye - две тысячи чисел от 0 до 255 из генератора случайных чисел.

sostoyanie = 2
oshibok = 0
summa = 0
for x in dannye:
    budet = x >= 128
    if (sostoyanie >= 2) != budet:
        oshibok = oshibok + 1
    if budet:
        summa = summa + x
        if sostoyanie < 3:
            sostoyanie = sostoyanie + 1
    else:
        if sostoyanie > 0:
            sostoyanie = sostoyanie - 1
print(summa, oshibok)

Два запуска - на случайных данных и на них же после сортировки:

данные                         сумма      ошибок предсказателя
2000 чисел, случайный порядок  192 825        1017
те же числа, отсортированы     192 825           3

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

Версия без ветвления:

summa = 0
for x in dannye:
    m = 127 - x >> 31
    summa = summa + (x & m)
print(summa)

127 − x отрицательно ровно при x ≥ 128; маска включает слагаемое или обнуляет его. Сумма та же, 192 825, при любом порядке данных, и угадывать нечего.

Теперь границы. Первая: в тренажёре версия без ветвления дороже - 6002 шага против 5008 у обычного цикла с if x >= 128: summa = summa + x. Тренажёр считает строки программы и про предсказатель не знает; выигрыш существует только на настоящем процессоре и только на непредсказуемых данных. Если условие почти всегда одно и то же, ветвление дешевле: предсказатель угадывает, а ветка, которая не понадобилась, не выполняется вовсе. Формула без ветвления считает обе ветки всегда.

Вторая: для простых случаев вроде минимума компилятор сам ставит команду условной пересылки - «скопируй, если условие выполнено», без перехода, - и руками писать маски незачем. Знать приём нужно, чтобы читать такой код, чтобы применять его к целым массивам - там масками работают векторные команды, - и для случая из следующего блока, когда время работы не должно выдавать данные.

Что ломается без этого

Первое: время выдаёт данные. Сравнение двух строк, которое выходит на первом несовпавшем байте, работает тем дольше, чем длиннее совпавшее начало. Если одна из строк - секретный код, его подбирают по байту, измеряя время ответа. Защита - сравнение без ветвления по данным: накопить raznica = raznica | (a[i] ^ b[i]) по всем байтам и проверить ноль один раз в конце. В разделе про числа та же беда была у степени по модулю.

Второе: переполнение разности. В 32-битном слове минимум на маске из a − b неверен, когда разность не помещается: для a = 2 000 000 000 и b = −2 000 000 000 она переполняется, знак переворачивается и возвращается большее число. Показанная функция на Python этого не воспроизводит - у его целых нет ширины, - зато и маска у неё получается, только пока разность по модулю меньше 2³¹.

Третье: сдвиг не той ширины. x >> 31 - маска только для 32-битного числа. Для 64-битного нужен сдвиг на 63, а сдвиг беззнакового числа даёт 0 или 1, а не 0 или −1.

Четвёртое: обмен через ^ с самим собой. Три действия a ^= b, b ^= a, a ^= b - короткая запись a = a ^ b и так далее - меняют значения местами без третьей переменной. Если a и b - одна и та же ячейка массива, первая же строка обнуляет её. Обычный обмен через временную переменную быстрее и не ломается.

Зачем это в работе

Криптографические библиотеки пишут без ветвлений и без обращений к памяти по секретным данным - это требование, а не оптимизация. Функция сравнения с постоянным временем есть в стандартной библиотеке Python: hmac.compare_digest.

Обработка изображений и звука: «ограничить значение диапазоном 0-255» для миллиона точек - это минимум и максимум без ветвлений, выполняемые векторными командами над шестнадцатью или шестьюдесятью четырьмя точками сразу.

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

Теперь сам

1. Чему равна маска x >> 31 для x = −1, x = 0 и x = 2 000 000 000?
2. Проследи modul(-1) по шагам.
3. Запиши максимум двух чисел через маску по образцу минимума.
4. usl равно 0 или 1. Что вернёт vybor(usl, 7, 7) и почему ответ не зависит от usl?
5. В массиве 1000 чисел, условие истинно для 990 из них, и они идут вперемешку. Что выгоднее - ветвление или маска?