Jakie jest najszybsze dzielenie liczb całkowitych obsługujące dzielenie przez zero, niezależnie od wyniku?

Podsumowanie:

Szukam najszybszego sposobu obliczenia

(int) x / (int) y

bez wyjątku dla y==0. Zamiast tego chcę po prostu arbitralnego wyniku.

Tło:

Podczas kodowania algorytmów przetwarzania obrazu często muszę podzielić przez (skumulowaną) wartość alfa. Najprostszym wariantem jest zwykły kod C z arytmetyką liczb całkowitych. Mój problem polega na tym, że zwykle otrzymuję błąd dzielenia przez zero dla pikseli wynikowych z alpha==0. Jednak są to dokładnie piksele, w których wynik nie ma żadnego znaczenia: nie obchodzą mnie wartości kolorów pikseli z alpha==0.

Detale:

Szukam czegoś takiego:

result = (y==0)? 0 : x/y;

lub

result = x / MAX( y, 1 );

x i y są dodatnimi liczbami całkowitymi. Kod jest wykonywany ogromną liczbę razy w zagnieżdżonej pętli, więc szukam sposobu na pozbycie się rozgałęzień warunkowych.

Kiedy y nie przekracza zakresu bajtów, jestem zadowolony z rozwiązania

unsigned char kill_zero_table[256] = { 1, 1, 2, 3, 4, 5, 6, 7, [...] 255 };
[...]
result = x / kill_zero_table[y];

Ale to oczywiście nie działa dobrze dla większych zakresów.

Wydaje mi się, że ostatnie pytanie brzmi: jaki jest najszybszy sposób na zmianę wartości 0 na dowolną inną liczbę całkowitą, pozostawiając wszystkie inne wartości bez zmian?

Wyjaśnienia

Nie jestem w 100% pewien, czy rozgałęzianie jest zbyt drogie. Jednak używane są różne kompilatory, więc wolę testy porównawcze z niewielkimi optymalizacjami (co jest rzeczywiście wątpliwe).

Z pewnością kompilatory są świetne, jeśli chodzi o manipulowanie bitami, ale nie mogę wyrazić wyniku "nie przejmuję się" w C, więc kompilator nigdy nie będzie w stanie wykorzystać pełnego zakresu optymalizacji.

Kod powinien być w pełni kompatybilny z C, główne platformy to Linux 64-bitowy z gcc i clang oraz MacOS.

Zainspirowany niektórymi komentarzami pozbyłem się gałęzi na moim Pentium i gcckompilatorze za pomocą

int f (int x, int y)
{
        y += y == 0;
        return x/y;
}

Kompilator zasadniczo rozpoznaje, że może użyć flagi warunku testu w dodatku.

Na życzenie montaż:

.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

Ponieważ okazało się, że jest to popularne pytanie i odpowiedź, opowiem o tym nieco więcej. Powyższy przykład jest oparty na idiomie programowania, który rozpoznaje kompilator. W powyższym przypadku w arytmetyce całkowej używane jest wyrażenie boolowskie, a do tego celu w sprzęcie wymyślono użycie flag warunków. Ogólnie flagi warunków są dostępne tylko w C za pomocą idiomu. Dlatego tak trudno jest stworzyć przenośną bibliotekę liczb całkowitych o wielokrotnej precyzji w C bez uciekania się do asemblacji (inline). Domyślam się, że większość przyzwoitych kompilatorów zrozumie powyższy idiom.

Innym sposobem na unikanie rozgałęzień, jak również zauważono w niektórych z powyższych komentarzy, jest wykonanie predykatu. Dlatego wziąłem pierwszy kod Philippa i mój kod i przepuściłem go przez kompilator z ARM i kompilator GCC dla architektury ARM, która zawiera predykowane wykonanie. Oba kompilatory unikają gałęzi w obu przykładach kodu:

Wersja Filipa z kompilatorem ARM:

f PROC
        CMP      r1,#0
        BNE      __aeabi_idivmod
        MOVEQ    r0,#0
        BX       lr

Wersja Filipa z GCC:

f:
        subs    r3, r1, #0
        str     lr, [sp, #-4]!
        moveq   r0, r3
        ldreq   pc, [sp], #4
        bl      __divsi3
        ldr     pc, [sp], #4

Mój kod z kompilatorem ARM:

f PROC
        RSBS     r2,r1,#1
        MOVCC    r2,#0
        ADD      r1,r1,r2
        B        __aeabi_idivmod

Mój kod z GCC:

f:
        str     lr, [sp, #-4]!
        cmp     r1, #0
        addeq   r1, r1, #1
        bl      __divsi3
        ldr     pc, [sp], #4

Wszystkie wersje nadal wymagają rozgałęzienia do procedury dywizji, ponieważ ta wersja ARM nie ma sprzętu do podziału, ale test y == 0jest w pełni zaimplementowany poprzez wykonanie predykatu.

Oto kilka konkretnych liczb w systemie Windows używającym 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);
}

Zauważ, że celowo nie dzwonię srand(), więc rand()zawsze zwraca dokładnie te same wyniki. Zauważ również, że -DCHECK=0liczy tylko zera, więc jest oczywiste, jak często się pojawiał.

Teraz kompilujemy i mierzymy czas na różne sposoby:

$ 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

pokazuje dane wyjściowe, które można podsumować w tabeli:

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

Jeśli zera są rzadkie, -DCHECK=2wersja działa źle. Gdy zera zaczną pojawiać się więcej,-DCHECK=2 sprawa zaczyna działać znacznie lepiej. Wśród innych opcji naprawdę nie ma dużej różnicy.

Bo -O3to jednak inna historia:

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

W tym przypadku sprawdzenie 2 nie ma wady w porównaniu z innymi kontrolami i zachowuje korzyści, ponieważ zera stają się bardziej powszechne.

Jednak naprawdę powinieneś dokonać pomiaru, aby zobaczyć, co dzieje się z twoim kompilatorem i reprezentatywnymi przykładowymi danymi.

Bez znajomości platformy nie ma sposobu, aby poznać dokładną najbardziej wydajną metodę, jednak w systemie ogólnym może to być zbliżone do optymalnego (przy użyciu składni Intel assembler):

(załóżmy, że jest dzielnik, ecxa dywidenda jest eax)

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

Cztery nierozgałęzione instrukcje z jednym cyklem plus dzielenie. Iloraz będzie w, eaxa reszta będzie edxna końcu. (Ten rodzaj pokazuje, dlaczego nie chcesz wysyłać kompilatora do pracy mężczyzny).

Zgodnie z tym linkiem możesz po prostu zablokować sygnał SIGFPE za pomocąsigaction() (sam tego nie próbowałem, ale uważam, że powinno działać).

Jest to najszybsze możliwe podejście, jeśli błędy dzielenia przez zero są niezwykle rzadkie: płacisz tylko za podziały przez zero, a nie za prawidłowe podziały, normalna ścieżka wykonania w ogóle się nie zmienia.

Jednak system operacyjny będzie zaangażowany w każdy ignorowany wyjątek, co jest kosztowne. Myślę, że powinieneś mieć co najmniej tysiąc dobrych podziałów na dział przez zero, które ignorujesz. Jeśli wyjątki są częstsze, prawdopodobnie zapłacisz więcej, ignorując wyjątki niż sprawdzając każdą wartość przed dzieleniem.