Какое самое быстрое целочисленное деление поддерживает деление на ноль независимо от результата?

109

Резюме:

Я ищу самый быстрый способ расчета

(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.

Philipp
источник
22
Как вы определили, что if-ветка слишком дорога?
djechlin
7
Как вы определили , что там есть филиал?
leemes
13
+1 для профилирования, с современным прогнозированием ветвлений вам это может не понадобиться. Кроме того, почему вы кодируете собственные алгоритмы обработки изображений?
TC1
8
«Какой самый быстрый способ взлома ...» Может быть y += !y? Для этого не нужна ветвь. Вы могли бы сравнить x / (y + !y)против x / max(y, 1)и , возможно , также y ? (x/y) : 0. Думаю, ни в одном из них не будет ветки, по крайней мере, с включенной оптимизацией.
leemes
6
Любой, кто думает, что современное предсказание ветвлений означает, что вам не нужно этого делать, не профилировал достаточно кода исключения ветвлений, который выполняется на уровне пикселей. Современное предсказание ветвлений приемлемо, если альфа- 0секции огромны и непрерывны. Есть место повозиться с микрооптимизациями, и попиксельные операции - это именно то место.
Якк - Адам Неврамонт

Ответы:

107

Вдохновленный некоторыми комментариями, я избавился от ветки на моем 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 с использованием идиомы. Вот почему так сложно создать переносимую целочисленную библиотеку с множественной точностью на 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полностью реализована посредством предиктивного выполнения.

Брайан Оливье
источник
Не могли бы вы показать нам получившийся код ассемблера? Или как вы определили, что ветки нет?
Haatschii
1
Потрясающие. Можно сделать 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
Якк - Адам Неврамонт
1
@leemes , но я имел в виду , |не &. Ooops - ( (lhs)/(rhs+!rhs) ) | -!rhsдолжно установить ваше значение, 0xFFFFFFFесли rhsесть 0, и lhs/rhsесли rhs!=0.
Якк - Адам Неврамонт
1
Это было очень умно.
Теодорос Хатцигианнакис
1
Отличный ответ! Я обычно прибегаю к сборке для таких вещей, но ее всегда ужасно поддерживать (не говоря уже о меньшей переносимости;)).
Лео
20

Вот некоторые конкретные числа в 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 не имеет недостатков по сравнению с другими проверками и сохраняет преимущества, поскольку нули становятся все более распространенными.

Однако вы должны действительно измерить, чтобы увидеть, что происходит с вашим компилятором и вашими репрезентативными выборочными данными.


источник
4
Сделайте 50% записей d=0случайными, вместо того чтобы делать это почти всегда d!=0, и вы увидите больше ошибок предсказания ветвления. Предсказание ветвления великолепно, если за одной веткой следуют почти всегда, или если следование той или другой действительно неуклюже ...
Якк - Адам Неврамонт
@Yakk Итерация d- это внутренний цикл, поэтому d == 0случаи распределяются равномерно. И d == 0реально ли сделать 50% случаев ?
2
реалистично ли изготовление 0.002%корпусов d==0? Они распространяются повсюду, каждые 65000 итераций вы попадаете в свое d==0дело. Хотя 50%может случиться не часто 10%или 1%легко, или даже 90%или 99%. Отображаемый тест на самом деле проверяет только «если вы в принципе никогда не спускаетесь по ветке, делает ли предсказание ветвления бессмысленным удаление ветки?», На который ответ будет «да, но это не интересно».
Якк - Адам Неврамонт
1
Нет, потому что из-за шума различия будут практически незаметны.
Джо
3
Распределение нулей не связано с распределением, найденным в ситуации задающего вопрос. Изображения, содержащие смесь 0 альфа и других, имеют дыры или неправильную форму, но (обычно) это не шум. Было бы ошибкой предполагать, что вы ничего не знаете о данных (и считаете это шумом). Это реальное приложение с реальными изображениями, которые могут иметь значение 0 альфа. И поскольку строка пикселей, вероятно, будет иметь либо все a = 0, либо все a> 0, использование предсказания ветвления вполне может быть самым быстрым, особенно когда a = 0 встречается часто и (медленные) деления (15+ циклов !) избегаются.
DDS
13

Не зная платформу, невозможно узнать точный наиболее эффективный метод, однако в общей системе он может быть близок к оптимальному (с использованием синтаксиса ассемблера Intel):

(предположим, что делитель ecxи дивиденд находятся в eax)

mov ebx, ecx
neg ebx
sbb ebx, ebx
add ecx, ebx
div eax, ecx

Четыре неразветвленных одноцикловых инструкции плюс разделитель. В конце будет частное, eaxа остаток - в edxконце. (Этот вид показывает, почему вы не хотите отправлять компилятор для выполнения мужской работы).

Тайлер Дерден
источник
где разделение?
Якк - Адам Неврамонт
1
это не делает деление, оно просто загрязняет делитель, так что деление на ноль невозможно,
Тайлер Дерден,
@Jens Timmerman Извините, я написал это до того, как добавил оператор div. Я обновил текст.
Тайлер Дерден,
1

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

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

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

cmaster - восстановить монику
источник