Najszybszy sposób ustalenia, czy liczba całkowita znajduje się między dwiema liczbami całkowitymi (włącznie) ze znanymi zestawami wartości

389

Czy istnieje szybszy sposób niż x >= start && x <= endw C lub C ++ sprawdzenie, czy liczba całkowita znajduje się między dwiema liczbami całkowitymi?

AKTUALIZACJA : Moja konkretna platforma to iOS. Jest to część funkcji rozmycia ramki, która ogranicza piksele do okręgu w danym kwadracie.

AKTUALIZACJA : Po wypróbowaniu zaakceptowanej odpowiedzi otrzymałem przyspieszenie o rząd wielkości w jednym wierszu kodu, zamiast robić to normalnie x >= start && x <= end.

AKTUALIZACJA : Oto kod po i przed asemblerem z XCode:

NOWY SPOSÓB

// diff = (end - start) + 1
#define POINT_IN_RANGE_AND_INCREMENT(p, range) ((p++ - range.start) < range.diff)

Ltmp1313:
 ldr    r0, [sp, #176] @ 4-byte Reload
 ldr    r1, [sp, #164] @ 4-byte Reload
 ldr    r0, [r0]
 ldr    r1, [r1]
 sub.w  r0, r9, r0
 cmp    r0, r1
 blo    LBB44_30

STARA DROGA

#define POINT_IN_RANGE_AND_INCREMENT(p, range) (p <= range.end && p++ >= range.start)

Ltmp1301:
 ldr    r1, [sp, #172] @ 4-byte Reload
 ldr    r1, [r1]
 cmp    r0, r1
 bls    LBB44_32
 mov    r6, r0
 b      LBB44_33
LBB44_32:
 ldr    r1, [sp, #188] @ 4-byte Reload
 adds   r6, r0, #1
Ltmp1302:
 ldr    r1, [r1]
 cmp    r0, r1
 bhs    LBB44_36

Całkiem niesamowite, jak redukcja lub eliminacja rozgałęzień może zapewnić tak gwałtowne przyspieszenie.

jjxtra
źródło
28
Dlaczego obawiasz się, że nie jest to dla ciebie wystarczająco szybkie?
Matt Ball
90
Kogo to obchodzi, to ciekawe pytanie. To tylko wyzwanie dla samego wyzwania.
David mówi Przywróć Monikę
46
@SLaks Powinniśmy więc zignorować wszystkie takie pytania na ślepo i powiedzieć „pozwól optymalizatorowi to zrobić?”
David mówi Przywróć Monikę
87
nie ma znaczenia, dlaczego pytanie jest zadawane. Jest to ważne pytanie, nawet jeśli odpowiedź brzmi nie
tay10r
41
To jest wąskie gardło w funkcji w jednej z moich aplikacji
jjxtra,

Odpowiedzi:

527

Jest stara sztuczka, aby to zrobić za pomocą tylko jednego porównania / gałęzi. To, czy rzeczywiście poprawi prędkość, może być kwestią otwartą, a nawet jeśli tak jest, prawdopodobnie jest to zbyt mało, aby zauważyć lub się tym przejmować, ale kiedy zaczynasz od dwóch porównań, szanse na ogromną poprawę są dość niewielkie. Kod wygląda następująco:

// use a < for an inclusive lower bound and exclusive upper bound
// use <= for an inclusive lower bound and inclusive upper bound
// alternatively, if the upper bound is inclusive and you can pre-calculate
//  upper-lower, simply add + 1 to upper-lower and use the < operator.
    if ((unsigned)(number-lower) <= (upper-lower))
        in_range(number);

W przypadku typowego, nowoczesnego komputera (tj. Cokolwiek używającego uzupełnienia dwójkowego) konwersja do niepodpisanego jest naprawdę nop - po prostu zmiana w sposobie wyświetlania tych samych bitów.

Zwróć uwagę, że w typowym przypadku można wstępnie wykonać obliczenia upper-lowerpoza (przypuszczalnie) zapętloną, więc zwykle nie zajmuje to znaczącego czasu. Wraz ze zmniejszeniem liczby instrukcji rozgałęzienia, to także (ogólnie) poprawia przewidywanie rozgałęzień. W takim przypadku brana jest ta sama gałąź, niezależnie od tego, czy liczba znajduje się poniżej dolnego końca, czy powyżej górnego końca zakresu.

Jeśli chodzi o to, jak to działa, podstawowa idea jest dość prosta: liczba ujemna, gdy jest postrzegana jako liczba bez znaku, będzie większa niż cokolwiek, co początkowo było liczbą dodatnią.

W praktyce ta metoda tłumaczy numberi interwał do punktu początkowego i sprawdza, czy numberjest w interwale [0, D], gdzie D = upper - lower. Jeżeli numberponiżej dolnej granicy: ujemny , a jeśli powyżej górnej granicy: większy niżD .

Jerry Coffin
źródło
8
@ TomásBadan: Oba będą jednym cyklem na dowolnej rozsądnej maszynie. Drogi jest oddział.
Oliver Charlesworth,
3
Dodatkowe rozgałęzienie jest wykonywane z powodu zwarcia? Jeśli tak jest, czy lower <= x & x <= upper(zamiast lower <= x && x <= upper) spowoduje to również lepszą wydajność?
Markus Mayr
6
@ AK4749, jxh: Tak fajna jak ta bryłka, jestem niezdecydowana, aby wyrazić zgodę, ponieważ niestety nic nie sugeruje, że jest to szybsze w praktyce (dopóki ktoś nie porówna wynikowego asemblera i informacji profilowania). Z tego, co wiemy, kompilator OP może renderować kod OP z pojedynczym kodem operacyjnym gałęzi ...
Oliver Charlesworth,
152
ŁAŁ!!! Spowodowało to poprawę rzędu mojej wielkości w mojej aplikacji dla tego konkretnego wiersza kodu. Po wstępnym obliczeniu górna-dolna moje profilowanie zmieniło się z 25% czasu tej funkcji do mniej niż 2%! Wąskie gardło to teraz operacje dodawania i odejmowania, ale myślę, że teraz może być wystarczająco dobre :)
jjxtra,
28
Ach, teraz @PsychoDad zaktualizował pytanie, jasne jest, dlaczego jest to szybsze. Prawdziwy kod ma efekt uboczny w stosunku, który jest dlaczego kompilator nie mógł zoptymalizować zwarcie z dala.
Oliver Charlesworth,
17

Rzadko można dokonać znacznych optymalizacji kodu na tak małą skalę. Duży wzrost wydajności wynika z obserwacji i modyfikacji kodu z wyższego poziomu. Możesz być w stanie całkowicie wyeliminować potrzebę testu zasięgu lub wykonać O (n) z nich zamiast O (n ^ 2). Być może będziesz w stanie ponownie zamówić testy, aby zawsze sugerować jedną stronę nierówności. Nawet jeśli algorytm jest idealny, zyski są bardziej prawdopodobne, gdy zobaczysz, jak ten kod testuje zakres 10 milionów razy i znajdujesz sposób na grupowanie ich i użycie SSE do przeprowadzenia wielu testów równolegle.

Ben Jackson
źródło
16
Mimo negatywnych opinii, stoję przy mojej odpowiedzi: wygenerowany zestaw (patrz link do pastebinu w komentarzu do zaakceptowanej odpowiedzi) jest dość okropny dla czegoś w wewnętrznej pętli funkcji przetwarzania pikseli. Przyjęta odpowiedź to fajna sztuczka, ale jej dramatyczny efekt znacznie wykracza poza to, czego można się spodziewać po wyeliminowaniu części gałęzi na iterację. Dominuje jakiś efekt wtórny i nadal oczekuję, że próba zoptymalizowania całego procesu w tym jednym teście pozostawi po sobie sprytne porównanie zasięgu w pyle.
Ben Jackson
17

To zależy od tego, ile razy chcesz wykonać test na tych samych danych.

Jeśli wykonujesz test jednorazowo, prawdopodobnie nie ma znaczącego sposobu na przyspieszenie algorytmu.

Jeśli robisz to dla bardzo skończonego zestawu wartości, możesz utworzyć tabelę odnośników. Wykonywanie indeksowania może być droższe, ale jeśli zmieścisz całą tabelę w pamięci podręcznej, możesz usunąć wszystkie rozgałęzienia z kodu, co powinno przyspieszyć.

Dla twoich danych tabela odnośników wynosiłaby 128 ^ 3 = 2 097 152. Jeśli możesz kontrolować jedną z trzech zmiennych, aby rozważyć wszystkie instancje start = Njednocześnie, wówczas rozmiar zestawu roboczego spada do 128^2 = 16432bajtów, co powinno dobrze pasować w większości nowoczesnych pamięci podręcznych.

Nadal będziesz musiał przeprowadzić analizę porównawczą rzeczywistego kodu, aby sprawdzić, czy tabela wyszukiwania bez rozgałęzień jest wystarczająco szybsza niż oczywiste porównania.

Andrew Prock
źródło
Czylibyś zapisał jakiś rodzaj odnośnika, biorąc pod uwagę wartość, początek i koniec, i zawierałby BOOL informujący, czy jest pomiędzy.
jjxtra
Poprawny. Byłoby tabeli odnośników 3D: bool between[start][end][x]. Jeśli wiesz, jak będzie wyglądał twój wzorzec dostępu (na przykład x rośnie monotonicznie), możesz zaprojektować tabelę tak, aby zachowała lokalizację, nawet jeśli cały stół nie mieści się w pamięci.
Andrew Prock,
Zobaczę, czy uda mi się wypróbować tę metodę i sprawdzić, jak to działa. Planuję zrobić to z wektorem bitowym na linię, gdzie bit zostanie ustawiony, jeśli punkt będzie w okręgu. Myślisz, że będzie to szybsze niż bajt lub int32 w porównaniu do maskowania bitów?
jjxtra
2

Ta odpowiedź ma na celu raportowanie badań wykonanych z zaakceptowaną odpowiedzią. Przeprowadziłem test z zamkniętym zakresem na dużym wektorze posortowanej losowej liczby całkowitej i ku mojemu zdziwieniu podstawowa metoda (low <= num && num <= high) jest w rzeczywistości szybsza niż zaakceptowana powyżej odpowiedź! Test został przeprowadzony na HP Pavilion g6 (AMD A6-3400APU z 6 GB pamięci RAM. Oto podstawowy kod używany do testowania:

int num = rand();  // num to compare in consecutive ranges.
chrono::time_point<chrono::system_clock> start, end;
auto start = chrono::system_clock::now();

int inBetween1{ 0 };
for (int i = 1; i < MaxNum; ++i)
{
    if (randVec[i - 1] <= num && num <= randVec[i])
        ++inBetween1;
}
auto end = chrono::system_clock::now();
chrono::duration<double> elapsed_s1 = end - start;

w porównaniu z poniższą, która jest zaakceptowaną odpowiedzią powyżej:

int inBetween2{ 0 };
for (int i = 1; i < MaxNum; ++i)
{
    if (static_cast<unsigned>(num - randVec[i - 1]) <= (randVec[i] - randVec[i - 1]))
        ++inBetween2;
}

Zwróć uwagę, że randVec jest posortowanym wektorem. Dla dowolnej wielkości MaxNum pierwsza metoda pokonuje drugą na moim komputerze!

rezeli
źródło
1
Moje dane nie są sortowane, a moje testy dotyczą procesora ramienia iPhone'a. Twoje wyniki z różnymi danymi i procesorem mogą się różnić.
jjxtra
posortowane w moim teście było tylko po to, aby upewnić się, że górny limit nie jest mniejszy niż dolny limit.
rezeli
1
Posortowane liczby oznaczają, że przewidywanie rozgałęzień będzie bardzo wiarygodne i wszystkie gałęzie będą prawidłowe, z wyjątkiem kilku w punktach przełączania. Zaletą kodu bez rozgałęzień jest to, że pozbywa się tego rodzaju nieprzewidzianych nieprzewidzianych danych.
Andreas Klebinger
0

W celu sprawdzenia dowolnego zakresu zmiennych:

if (x >= minx && x <= maxx) ...

Szybsza jest operacja bitowa:

if ( ((x - minx) | (maxx - x)) >= 0) ...

Spowoduje to zmniejszenie dwóch gałęzi do jednego.

Jeśli zależy Ci na bezpiecznym typie:

if ((int32_t)(((uint32_t)x - (uint32_t)minx) | ((uint32_t)maxx - (uint32_t)x)) > = 0) ...

Możesz połączyć więcej sprawdzania zmiennego zakresu razem:

if (( (x - minx) | (maxx - x) | (y - miny) | (maxy - y) ) >= 0) ...

Spowoduje to zmniejszenie 4 gałęzi do 1.

Jest 3,4 razy szybszy niż stary w gcc:

wprowadź opis zdjęcia tutaj

skywind3000
źródło
-4

Czy nie jest możliwe wykonanie bitowej operacji na liczbie całkowitej?

Ponieważ musi on zawierać się w przedziale od 0 do 128, jeśli ustawiony jest 8. bit (2 ^ 7), wynosi on 128 lub więcej. Sprawa krawędzi będzie jednak uciążliwa, ponieważ chcesz włączyć porównanie.

schłodzona woda
źródło
3
Chce wiedzieć, czy x <= end, gdzie end <= 128. Nie x <= 128.
Ben Voigt
1
To stwierdzenie „ Ponieważ musi być od 0 do 128, jeśli ustawiony jest 8 bit (2 ^ 7), to jest 128 lub więcej ” jest błędny. Rozważ 256.
Happy Green Kid Naps
1
Tak, najwyraźniej nie przemyślałem tego wystarczająco. Przepraszam.
wody lodowej