Резюме:
Я ищу самый быстрый способ расчета
(int) x / (int) y
без исключения y==0
. Вместо этого я просто хочу произвольный результат.
Задний план:
При кодировании алгоритмов обработки изображений мне часто приходится делить на (накопленное) альфа-значение. Самый простой вариант - это простой код на C с целочисленной арифметикой. Моя проблема в том, что я обычно получаю ошибку деления на ноль для пикселей результата с alpha==0
. Однако это именно те пиксели, где результат вообще не имеет значения: меня не волнуют значения цвета пикселей с alpha==0
.
Подробности:
Я ищу что-то вроде:
result = (y==0)? 0 : x/y;
или
result = x / MAX( y, 1 );
x и y - положительные целые числа. Код выполняется огромное количество раз во вложенном цикле, поэтому я ищу способ избавиться от условного ветвления.
Когда y не превышает диапазон байтов, я доволен решением
unsigned char kill_zero_table[256] = { 1, 1, 2, 3, 4, 5, 6, 7, [...] 255 };
[...]
result = x / kill_zero_table[y];
Но это явно не работает для больших диапазонов.
Я предполагаю, что последний вопрос: какой самый быстрый способ взлома битов меняет 0 на любое другое целочисленное значение, оставляя все остальные значения без изменений?
Разъяснения
Я не уверен на 100%, что разветвление обходится слишком дорого. Однако используются разные компиляторы, поэтому я предпочитаю тестирование с небольшими оптимизациями (что действительно сомнительно).
Конечно, компиляторы хороши, когда дело касается битового тидлинга, но я не могу выразить результат «безразлично» на C, поэтому компилятор никогда не сможет использовать весь спектр оптимизаций.
Код должен быть полностью совместим с C, основными платформами являются Linux 64 Bit с gcc & clang и MacOS.
источник
y += !y
? Для этого не нужна ветвь. Вы могли бы сравнитьx / (y + !y)
противx / max(y, 1)
и , возможно , такжеy ? (x/y) : 0
. Думаю, ни в одном из них не будет ветки, по крайней мере, с включенной оптимизацией.0
секции огромны и непрерывны. Есть место повозиться с микрооптимизациями, и попиксельные операции - это именно то место.Ответы:
Вдохновленный некоторыми комментариями, я избавился от ветки на моем Pentium и
gcc
компиляторе, используяКомпилятор в основном распознает, что он может использовать флаг условия теста в дополнение.
По запросу сборка:
Поскольку это оказался очень популярный вопрос и ответ, я расскажу немного подробнее. Приведенный выше пример основан на идиоме программирования, которую распознает компилятор. В приведенном выше случае в интегральной арифметике используется логическое выражение, и для этой цели в аппаратном обеспечении изобретены флаги условий. В общем случае флаги условий доступны только в C с использованием идиомы. Вот почему так сложно создать переносимую целочисленную библиотеку с множественной точностью на C, не прибегая к (встроенной) сборке. Я предполагаю, что большинство достойных компиляторов поймут эту идиому.
Другой способ избежать ветвлений, как также отмечалось в некоторых из приведенных выше комментариев, - это выполнение с условием. Поэтому я взял первый код Филиппа и свой код и пропустил его через компилятор ARM и компилятор GCC для архитектуры ARM, в которой реализовано предсказуемое выполнение. Оба компилятора избегают ветвления в обоих примерах кода:
Версия Филиппа с компилятором ARM:
Версия Филиппа с GCC:
Мой код с компилятором ARM:
Мой код с GCC:
Все версии по-прежнему нуждаются в ветвлении к подпрограмме деления, потому что в этой версии ARM нет оборудования для разделения, но проверка
y == 0
полностью реализована посредством предиктивного выполнения.источник
constexpr
и избежать ненужных приведений типа вот так:template<typename T, typename U> constexpr auto fdiv( T t, U u ) -> decltype(t/(u+!u)) { return t/(u+!u); }
И если хотите255
,(lhs)/(rhs+!rhs) & -!rhs
|
не&
. Ooops -( (lhs)/(rhs+!rhs) ) | -!rhs
должно установить ваше значение,0xFFFFFFF
еслиrhs
есть0
, иlhs/rhs
еслиrhs!=0
.Вот некоторые конкретные числа в Windows с использованием GCC 4.7.2:
Обратите внимание, что я намеренно не звоню
srand()
, чтобыrand()
всегда возвращать одни и те же результаты. Также обратите внимание, что-DCHECK=0
просто подсчитываются нули, поэтому очевидно, как часто они появляются.Теперь компилируем и синхронизируем его разными способами:
показывает результат, который можно свести в таблицу:
Если нули встречаются редко,
-DCHECK=2
версия работает плохо. По мере того, как нулей становится больше,-DCHECK=2
кейс начинает работать значительно лучше. Из других вариантов особой разницы нет.Для
-O3
, хотя, это другая история:Здесь проверка 2 не имеет недостатков по сравнению с другими проверками и сохраняет преимущества, поскольку нули становятся все более распространенными.
Однако вы должны действительно измерить, чтобы увидеть, что происходит с вашим компилятором и вашими репрезентативными выборочными данными.
источник
d=0
случайными, вместо того чтобы делать это почти всегдаd!=0
, и вы увидите больше ошибок предсказания ветвления. Предсказание ветвления великолепно, если за одной веткой следуют почти всегда, или если следование той или другой действительно неуклюже ...d
- это внутренний цикл, поэтомуd == 0
случаи распределяются равномерно. Иd == 0
реально ли сделать 50% случаев ?0.002%
корпусовd==0
? Они распространяются повсюду, каждые 65000 итераций вы попадаете в своеd==0
дело. Хотя50%
может случиться не часто10%
или1%
легко, или даже90%
или99%
. Отображаемый тест на самом деле проверяет только «если вы в принципе никогда не спускаетесь по ветке, делает ли предсказание ветвления бессмысленным удаление ветки?», На который ответ будет «да, но это не интересно».Не зная платформу, невозможно узнать точный наиболее эффективный метод, однако в общей системе он может быть близок к оптимальному (с использованием синтаксиса ассемблера Intel):
(предположим, что делитель
ecx
и дивиденд находятся вeax
)Четыре неразветвленных одноцикловых инструкции плюс разделитель. В конце будет частное,
eax
а остаток - вedx
конце. (Этот вид показывает, почему вы не хотите отправлять компилятор для выполнения мужской работы).источник
По этой ссылке вы можете просто заблокировать сигнал SIGFPE
sigaction()
(я сам не пробовал, но считаю, что он должен работать).Это самый быстрый из возможных подходов, если ошибки деления на ноль встречаются крайне редко: вы платите только за деления на ноль, а не за действительные деления, нормальный путь выполнения не изменяется вообще.
Однако ОС будет участвовать в каждом игнорируемом исключении, что дорого. Я думаю, у вас должно быть как минимум тысяча хороших делений на деление на ноль, которые вы игнорируете. Если исключения встречаются чаще, вы, вероятно, заплатите больше, игнорируя исключения, чем проверяя каждое значение перед делением.
источник