Jak pisać branchless code, część pierwsza [pl]

Ten wpis zapoczątkowuje coś, co można nazwać minitutorialem pisania branchless code. Będę to pisał, dopóki będę miał materiał, czas i chęci :P.

Zacznijmy od przypomnienia sobie pojęcia branchless code. Jak sama nazwa nazwa wskazuje, jest to taki code, który jest branchless… No dobra, wiem, że to oczywiste i nic nie wyjaśnia :P. W takim razie jeszcze raz – branchless code to taki kod, który nie używa rozgałęzień. Rozgałęzieniem (zwane gdzieniegdzie, na przykład na PDP-8 i x86 skokiem) nazywa się każde miejsce w programie, w którym procesor może (ewentualnie musi w przypadku skoków bezwarunkowych), zamiast wykonać następną instrukcję, zacząć mielić jakąś inną, znajdującą się w miejscu docelowym skoku (ja się wychowałem na x86, więc ciężko mi to nazywać rozgałęzieniem ;)). Branchless code zwykle wymaga umiejętnego bit twiddlingu (manipulacji bitami).

W takim razie, chcesz się nauczyć pisać branchless code? Ok, nie ma problemu, jednak najpierw muszę cię ostrzec przed kilkoma rzeczami:

• Zanim w ogóle zaczniesz optymalizować, to najpierw zrób, żeby działało! (dotyczy wszystkich rodzajów optymalizacji)
• Zanim zaczniesz tak optymalizować, sprawdź, czy rzeczywiście należy optymalizować (czyt. rób to tylko, jeśli obecna wydajność cię nie zadowala).
• Jeśli skok będzie zwykle poprawnie przewidziany przez branch predictor (czyli będzie well-predicted), to zwykły kod (z rozgałęzieniami) będzie szybszy niż branchless code (nie dotyczy architektur bez branch predictora z oczywistych powodów, chociaż wtedy trzeba wiedzieć, czy skoki na danej architekturze są wolne /wtedy branchless ma sens/ czy też szybkie /wersja ze skokami rulez/) – przydaje się porządny profiler.
• Staraj się napisać sensowne komentarze do kodu branchless, bo on zwykle jest dużo mniej czytelny niż równoważny kod w wersji ze skokami.

Przy pisaniu branchless code ważne jest tworzenie masek bitowych. Najważniejsze jest posiadanie ustrojstw, które pozwolą nam zrobić maskę z wyniku porównania (chociaż to nie będzie takie do końca porównanie, bo żaden operator porównania nie wystąpi – wtedy, nie licząc niektórych architektur, nie byłoby to branchless).

Najprostszym porównaniem, od którego zależą wszystkie inne, jest porównanie liczby na mniejszość z zerem (x < 0). Ta czynność jest już zapewne doskonale ci znana, jeśli śledzisz tą stronę od początku – tak, znowu pojawia się nam funkcja sex. Jako, że nie mam zamiaru się powtarzać, poproszę grzecznie o wybranie sobie implementacji tej funkcji z pierwszej badź drugiej notki o niej.

Kolejnym jest porównanie dwóch liczb na mniejszość (a < b). Prawdopodobnie już się domyśliłeś, czytając poprzedni akapit, że użyjemy funkcji sex. Pozostaje jednak wciąż pytanie, jak uzyskać liczbę ujemną, jeśli a jest mniejsze od b i dodatnią bądź zero w przeciwnym wypadku. Jest pewne działanie, które da nam taki wynik. Jest to odejmowanie, o czym łatwo się przekonać, sprawdzając to na kalkulatorze ;). Funkcja zwracająca -1 gdy a jest mniejsze od b i 0 w przeciwnym przypadku wygląda więc jakoś tak:

inline unsigned int bitmask_lt(int a, int b)
{
  return sex(a - b);
}

a > b przebiega w bardzo podobny sposób – wystarczy sobie przypomnieć, jak jest zdefiniowany std::rel_ops::operator> – używa operator<, tylko argumenty podaje w odwrotnej kolejności. Tak samo zrobimy tutaj:

inline unsigned int bitmask_gt(int a, int b)
{
  return bitmask_lt(b, a);
}

Następne jest “mniejsze bądź równe”. Wykorzystamy napisaną przed chwilą funkcję bitmask_lt i prostą właściwość: jeżeli a jest mniejsze bądź równe b, to a jest mniejsze niż b + 1 (ponownie – możesz sprawdzić na kalkulatorze :>).

inline unsigned int bitmask_le(int a, int b)
{
  return bitmask_lt(a, b + 1);
}

“Większe bądź równe” ma się tak do “mniejsze bądź równe”, jak “większe” do “mniejsze”:

inline unsigned int bitmask_ge(int a, int b)
{
  return bitmask_le(b, a);
}

Zostały nam dwa porównanie – na równość i nierówność. Nie bez powodu zostawiłem je na koniec – nie są tak miłe jak powyższe, trzeba się bardziej natrudzić, aby je osiągnąć. Najpierw napiszmy jednoargumentową funkcję która zwraca -1, jeśli a != 0 i 0 w przeciwnym wypadku, następnie na jej podstawie zaimplementujemy a != b oraz a == b.
Zastanówmy się chwilę, jak osiągnąć liczbę ujemną, jeśli a nie jest zerowe i 0 w przeciwnym wypadku. Przyda się na pewno jakieś działanie, które zwraca zero w przypadku zera i nie-zero w przypadku nie-zera. Na pewno samo a spełnia ten warunek, ale to za mało – wtedy dostaniemy sex. -a także spełnia ten warunek, ale samo w sobie też nie wystarczy – dostaniemy ~sex. Ale obydwa złożone przez bitowe OR do kupy już dają radę – dla niezerowej liczby a wyrażenie a | -a zwraca liczbę ujemną, natomiast dla zera sprowadza się do 0 | 0, co daje zero. I o to chodziło. Napiszmy więc to w C(++):

inline unsigned int bitmask_neq0(int a)
{
  return sex(a | -a);
}

Do zaimplementowania nierówności użyjemy tą samą rzecz, co przy mniejszości – odejmiemy jedną liczbę od drugiej, jeśli wyjdzie 0, to znaczy, że są równe (więc bitmask_neq0 zwróci 0), jeśli coś innego, to równe nie są (czyli dostaniemy -1):

inline unsigned int bitmask_neq(int a, int b)
{
  return bitmask_neq0(a - b);
}

Została nam już tylko równość. Z nią jest niemały problem – jest najbardziej kosztowną operacją, jako że wymaga sześciu operacji (podczas gdy np. sex tylko jednej). Implementacja tego jest bardzo prosta, jeśli mamy już nierówność – wystarczy zwrócić bitowe NOT tego, co tamta funkcja zwróci:

inline unsigned int bitmask_eq(int a, int b)
{
  return ~bitmask_neq(a, b);
}

To by było na dzisiaj tyle, w następnej części będzie trochę o tym, do czego te maski można wykorzystać.

Funkcje nie są overflow-safe i dobrze o tym wiem, ale zwykle nie robi to większej różnicy.

EDIT (16th November 2009): Wziąłem się do roboty i napisałem drugą część tego minitutka – jakby ktoś nie wiedział, bo trafił tu z innej strony czy coś ;)

~ - autor: Fanael w dniu Październik 11, 2009.