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

109

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.

philipp
źródło
22
W jaki sposób ustaliłeś, że oddział if jest zbyt drogi?
djechlin
7
Jak pan ustalił, że tam jest oddział?
leemes
13
+1 do profilowania, przy współczesnych prognozach branżowych możesz tego nie potrzebować. Poza tym, dlaczego kodujesz własne algorytmy przetwarzania obrazu?
TC1
8
„Jaki jest najszybszy sposób na kręcenie hacków…” Może y += !y? Żadna gałąź nie była potrzebna do obliczenia tego. Możesz porównać x / (y + !y)z, x / max(y, 1)a może także y ? (x/y) : 0. Myślę, że w żadnym z nich nie będzie odgałęzienia, przynajmniej przy włączonych optymalizacjach.
leemes
6
Każdy, kto uważa, że ​​współczesne przewidywanie rozgałęzień oznacza, że ​​nie musisz tego robić, nie sprofilował wystarczająco dużo kodu eliminującego gałęzie, który działa na poziomie na piksel. Współczesne prognozy dotyczące gałęzi są dopuszczalne, jeśli 0sekcje alfa są duże i ciągłe. Jest miejsce na majstrowanie przy mikrooptymalizacjach, a operacje na piksel są właśnie tym miejscem.
Yakk - Adam Nevraumont

Odpowiedzi:

107

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.

Bryan Olivier
źródło
Czy możesz nam pokazać wynikowy kod asemblera? Albo jak ustaliliście, że nie ma oddziału?
Haatschii
1
Niesamowite. Można go wykonać constexpri uniknąć niepotrzebnych rzutów typu: template<typename T, typename U> constexpr auto fdiv( T t, U u ) -> decltype(t/(u+!u)) { return t/(u+!u); } A jeśli chcesz 255,(lhs)/(rhs+!rhs) & -!rhs
Yakk - Adam Nevraumont
1
@leemes ale ja miałem na myśli |nie &. Ups - ( (lhs)/(rhs+!rhs) ) | -!rhsnależy ustawić wartość na 0xFFFFFFFjeśli rhsjest 0i lhs/rhsjeśli rhs!=0.
Yakk - Adam Nevraumont
1
To było bardzo sprytne.
Theodoros Chatzigiannakis
1
Świetna odpowiedź! Zwykle uciekam się do montażu do tego typu rzeczy, ale zawsze jest to okropne w utrzymaniu (nie wspominając o mniej przenośnym;)).
Leo
20

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.


źródło
4
Spraw, aby 50% wpisów było d=0losowych, zamiast prawie zawsze d!=0, a zobaczysz więcej błędów przewidywania gałęzi. Przewidywanie gałęzi jest świetne, jeśli prawie zawsze przestrzega się jednej gałęzi lub jeśli śledzenie jednej lub drugiej gałęzi jest naprawdę
zlepione
@Yakk dIteracja to pętla wewnętrzna, więc obserwacje d == 0są rozmieszczone równomiernie. I czy 50% przypadków jest d == 0realistyczne?
2
czy prowadzenie 0.002%spraw jest d==0realistyczne? Są rozprowadzane po każdym 65000 iteracji, które trafią w Twoją d==0sprawę. Chociaż 50%może nie zdarzać się często 10%lub 1%może się zdarzyć łatwo, a nawet 90%lub 99%. Test, tak jak jest wyświetlany, tak naprawdę sprawdza tylko „jeśli w zasadzie nigdy, przenigdy nie zejdziesz w dół gałęzi, czy przewidywanie gałęzi sprawia, że ​​usuwanie gałęzi jest bezcelowe?”, Na co odpowiedź brzmi „tak, ale to nie jest interesujące”.
Yakk - Adam Nevraumont
1
Nie, ponieważ różnice będą praktycznie niewidoczne z powodu hałasu.
Joe
3
Rozkład zer nie odnosi się do rozkładu znalezionego w sytuacji osoby zadającej pytanie. Obrazy zawierające połączenie alfa 0 i innych mają dziury lub nieregularny kształt, ale (zwykle) nie jest to szum. Zakładanie, że nic nie wiesz o danych (i uważanie ich za szum) jest błędem. To jest aplikacja z prawdziwego świata, z rzeczywistymi obrazami, które mogą mieć 0 alfa. A ponieważ wiersz pikseli prawdopodobnie będzie zawierał wszystkie a = 0 lub wszystkie a> 0, wykorzystanie predykcji rozgałęzień może być najszybsze, zwłaszcza gdy a = 0 występuje dużo i (wolne) dzielenie (ponad 15 cykli !) są unikane.
DDS
13

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

Tyler Durden
źródło
gdzie jest podział?
Yakk - Adam Nevraumont
1
to nie robi podziału, po prostu zanieczyszcza dzielnik, więc dzielenie przez zero jest niemożliwe
Tyler Durden
@Jens Timmerman Przepraszamy, napisałem to przed dodaniem instrukcji div. Zaktualizowałem tekst.
Tyler Durden
1

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.

cmaster - przywróć monikę
źródło