Какое самое быстрое целочисленное деление поддерживает деление на ноль, независимо от результата?
Резюме:
Я ищу самый быстрый способ расчета
(int) x / (int) y
без получения исключения для y==0, Вместо этого я просто хочу произвольный результат.
Фон:
При кодировании алгоритмов обработки изображений мне часто нужно делить на (накопленное) альфа-значение. Самый простой вариант — это простой C-код с целочисленной арифметикой. Моя проблема в том, что я обычно получаю ошибку деления на ноль для пикселей результата с alpha==0, Однако это именно те пиксели, где результат не имеет никакого значения: мне не нужны значения цвета для пикселей с alpha==0,
Подробности:
Я ищу что-то вроде:
result = (y==0)? 0 : x/y;
или же
result = x / MAX( y, 1 );
х и у натуральные числа. Код выполняется огромное количество раз во вложенном цикле, поэтому я ищу способ избавиться от условного ветвления.
Когда у не превышает диапазон байтов, я доволен решением
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 & лязг и MacOS.
Решение
Вдохновленный некоторыми комментариями, я избавился от ветки на моем Pentium и gcc использование компилятора
int f (int x, int y)
{
y += y == 0;
return x/y;
}
Компилятор в основном признает, что он может использовать флаг условия теста в дополнении.
Согласно запросу сборка:
.globl f
.type f, @function
f:
pushl %ebp
xorl %eax, %eax
movl %esp, %ebp
movl 12(%ebp), %edx
testl %edx, %edx
sete %al
addl %edx, %eax
movl 8(%ebp), %edx
movl %eax, %ecx
popl %ebp
movl %edx, %eax
sarl $31, %edx
idivl %ecx
ret
Поскольку это оказалось таким популярным вопросом и ответом, я уточню немного подробнее. Приведенный выше пример основан на идиоме программирования, которую распознает компилятор. В приведенном выше случае логическое выражение используется в интегральной арифметике, и для этого в аппаратных средствах изобретены флаги условий. В общем случае флаги условий доступны только в Си через идиому. Вот почему так сложно создать переносимую целочисленную библиотеку с множественной точностью в C, не прибегая к (встроенной) сборке. Я предполагаю, что большинство приличных компиляторов поймут вышеупомянутую идиому.
Другой способ избежать ветвлений, как также отмечается в некоторых из приведенных выше комментариев, — это предикатное выполнение. Поэтому я взял первый код Филиппа и мой код и пропустил его через компилятор из ARM и компилятор GCC для архитектуры ARM, которая поддерживает предикатное выполнение. Оба компилятора избегают перехода в обоих примерах кода:
Версия Филиппа с компилятором ARM:
f PROC
CMP r1,#0
BNE __aeabi_idivmod
MOVEQ r0,#0
BX lr
Версия Филиппа с GCC:
f:
subs r3, r1, #0
str lr, [sp, #-4]!
moveq r0, r3
ldreq pc, [sp], #4
bl __divsi3
ldr pc, [sp], #4
Мой код с компилятором ARM:
f PROC
RSBS r2,r1,#1
MOVCC r2,#0
ADD r1,r1,r2
B __aeabi_idivmod
Мой код с GCC:
f:
str lr, [sp, #-4]!
cmp r1, #0
addeq r1, r1, #1
bl __divsi3
ldr pc, [sp], #4
Все версии по-прежнему нуждаются в переходе к процедуре деления, потому что в этой версии ARM нет аппаратного обеспечения для деления, но есть тест для y == 0 полностью реализовано через предикатное выполнение.
Другие решения
Вот некоторые конкретные цифры для Windows, использующей GCC 4.7.2:
#include <stdio.h>
#include <stdlib.h>
int main()
{
unsigned int result = 0;
for (int n = -500000000; n != 500000000; n++)
{
int d = -1;
for (int i = 0; i != ITERATIONS; i++)
d &= rand();
#if CHECK == 0
if (d == 0) result++;
#elif CHECK == 1
result += n / d;
#elif CHECK == 2
result += n / (d + !d);
#elif CHECK == 3
result += d == 0 ? 0 : n / d;
#elif CHECK == 4
result += d == 0 ? 1 : n / d;
#elif CHECK == 5
if (d != 0) result += n / d;
#endif
}
printf("%u\n", result);
}
Обратите внимание, что я намеренно не звоню srand(), чтобы rand() всегда возвращает одинаковые результаты. Обратите внимание, что -DCHECK=0 просто считает нули, так что очевидно, как часто они появляются.
Теперь компилируем и рассчитываем его различными способами:
$ for it in 0 1 2 3 4 5; do for ch in 0 1 2 3 4 5; do gcc test.cc -o test -O -DITERATIONS=$it -DCHECK=$ch && { time=`time ./test`; echo "Iterations $it, check $ch: exit status $?, output $time"; }; done; done
показывает вывод, который может быть сведен в таблицу:
Iterations → | 0 | 1 | 2 | 3 | 4 | 5
-------------+-------------------------------------------------------------------
Zeroes | 0 | 1 | 133173 | 1593376 | 135245875 | 373728555
Check 1 | 0m0.612s | - | - | - | - | -
Check 2 | 0m0.612s | 0m6.527s | 0m9.718s | 0m13.464s | 0m18.422s | 0m22.871s
Check 3 | 0m0.616s | 0m5.601s | 0m8.954s | 0m13.211s | 0m19.579s | 0m25.389s
Check 4 | 0m0.611s | 0m5.570s | 0m9.030s | 0m13.544s | 0m19.393s | 0m25.081s
Check 5 | 0m0.612s | 0m5.627s | 0m9.322s | 0m14.218s | 0m19.576s | 0m25.443s
Если нули редки, то -DCHECK=2 версия работает плохо. Поскольку нули начинают появляться больше, -DCHECK=2 дело начинает работать значительно лучше. Из других вариантов нет особой разницы.
За -O3Впрочем, это другая история:
Iterations → | 0 | 1 | 2 | 3 | 4 | 5
-------------+-------------------------------------------------------------------
Zeroes | 0 | 1 | 133173 | 1593376 | 135245875 | 373728555
Check 1 | 0m0.646s | - | - | - | - | -
Check 2 | 0m0.654s | 0m5.670s | 0m9.905s | 0m14.238s | 0m17.520s | 0m22.101s
Check 3 | 0m0.647s | 0m5.611s | 0m9.085s | 0m13.626s | 0m18.679s | 0m25.513s
Check 4 | 0m0.649s | 0m5.381s | 0m9.117s | 0m13.692s | 0m18.878s | 0m25.354s
Check 5 | 0m0.649s | 0m6.178s | 0m9.032s | 0m13.783s | 0m18.593s | 0m25.377s
Там проверка 2 не имеет недостатка по сравнению с другими проверками, и она сохраняет преимущества, так как нули становятся более распространенными.
Вы должны действительно измерить, чтобы увидеть, что происходит с вашим компилятором и вашими репрезентативными образцами данных.
Без знания платформы невозможно найти точный наиболее эффективный метод, однако в общей системе это может быть близко к оптимальному (с использованием синтаксиса Intel на ассемблере):
(предположим, что делитель находится в ecx и дивиденд в eax)
mov ebx, ecx
neg ebx
sbb ebx, ebx
add ecx, ebx
div eax, ecx
Четыре неразветвленные инструкции с одним циклом плюс разделение. Коэффициент будет в eax и остаток будет в edx в конце. (Этот вид показывает, почему вы не хотите отправлять компилятор для выполнения мужской работы).
Согласно этому ссылка на сайт, Вы можете просто заблокировать сигнал SIGFPE с sigaction() (Я не пробовал сам, но я считаю, что это должно работать).
Это самый быстрый из возможных подходов, если ошибки деления на ноль крайне редки: вы платите только за деления на ноль, а не за действительные деления, нормальный путь выполнения вообще не изменяется.
Тем не менее, ОС будет участвовать в каждом исключении, которое игнорируется, что дорого. Я думаю, у вас должно быть не менее тысячи хороших делений на деление на ноль, которые вы игнорируете. Если исключения встречаются чаще, вы, вероятно, заплатите больше, игнорируя исключения, чем проверяя каждое значение перед делением.