Wyślij zapytanie Dołącz do Sii

Rozgałęzienie w programowaniu to najpopularniejsza forma definiowania kierunku wykonywania programu. Wszystkie instrukcje warunkowe (if, switch, operator ?: ) i pętle (for, while, do while) są podstawą każdego kodu źródłowego wykonywanego na maszynach zgodnych z modelem Turinga. Nie wyobrażamy sobie programowania bez instrukcji warunkowych, jednak w pewnych warunkach możemy szukać opcji zoptymalizowania czasu wykonywania naszego skomplikowanego programu.

Fragment kodu: BranchlessProgramming

Kiedy może pojawić się problem z instrukcjami warunkowymi?

Odpowiedź nasuwa się sama i oczywiście chodzi tutaj o krytyczne fragmenty programu, których wykonywanie może być przez instrukcje warunkowe znacząco zwolnione. Jednak w celu zrozumienia, dlaczego problem może się pojawić, należy zrozumieć sposób działania procesora.

Schemat działania procesora: IF, ID, EX, MEM, WB

Technika potokowości

CPU używa bowiem techniki potokowości (ang. Instruction Pipelining), aby zoptymalizować wykonywanie rozkazów procesora. Są one dzielone na specjalizowane grupy, dzięki czemu mogą jednocześnie wykonać część pracy związanej z wykonywaniem rozkazu, niczym na ultraszybkiej taśmie produkcyjnej. Dzięki temu, zanim jeszcze dojdzie do egzekucji instrukcji, są one pobierane i dekodowane, a całość zazębia się i wykonuje równolegle.
Graficznie przedstawiona technika potokowościW celu optymalizacji procesory pobierają instrukcje z wyprzedzeniem. Jeśli program posiada instrukcje warunkowe, CPU tak naprawdę zgaduje kilka instrukcji naprzód. W przypadku napotkania w programie rozgałęzienia ścieżki wykonywania programu (czyli wystąpienia instrukcji skoku), procesor zakłada z góry określoną drogę, więc dopóki idziemy przewidzianą drogą wszystko jest w porządku, ale problem pojawia się, kiedy logika programu zmieni kierunek i procesor musi się zaadaptować do sytuacji – czyli w praktyce usunąć część instrukcji i załadować nowy zestaw ponownie. Współcześnie, szacuje się, że skoki zdarzają się co kilkanaście instrukcji.

Grafika przedstawiająca skoki w technice potokowosci

Czy można zoptymalizować wybieranie ścieżki wykonywania instrukcji?

Z pomocą przychodzi idea programowania „bezgałęziowego” (ang. Branchless Programming). Jej głównym założeniem jest eliminowanie instrukcji skoku, szczególnie w przypadkach, jeśli znacząco wpływają one na wydajność programu. Może to ostatecznie i tak nie znaleźć zastosowania przy nowoczesnych językach interpretowanych czy coraz bardziej inteligentnych kompilatorach z wieloma opcjami optymalizacji, ale przy zadaniach specjalnych wymagających najwyższej wydajności i jak najmniejszych opóźnień, taka technika może okazać się pomocna.

Rozważając kod, najlepiej szukać funkcji, które wykonywane są często, w krytycznych fragmentach. Mając funkcję zwracającą mniejszą z dwóch wartości int:
Grafika funkcji zwracającąej mniejszą z dwóch wartości intzastanów się, jak można pozbyć się instrukcji skoku w tego typu instrukcjach warunkowych.

Instrukcja mnożenia

Otóż można skorzystać z instrukcji mnożenia. W końcu, jeśli wymnożymy daną wartość razy 1, nic się nie zmieni, a zredukować wartość można mnożąc przez 0. Suma takich iloczynów zadziała w tym przypadku identycznie jak powyższa funkcja.

Grafika wykorzystania funkcji mnożenia

Znając taką sztuczkę, możesz zamieniać dowolne warunki, a nawet skomplikowane switche. Korzystamy więc ze schematu mnożenia wartości przez warunek, kiedy dana wartość ma być zwracana i dodawaniu kolejnych, analogicznych wyrażeń dla następnych warunków.

Czasami warto również cache’ować wartość warunków i korzystać z negacji. Program w efekcie daje identyczne wyniki jak wersja z warunkami. Zauważalna jest natomiast zmiana w czytelności kodu i, w przypadku stosowania programowania bez rozgałęzień, należy zadbać o odpowiednią nazwę funkcji i komentarz z uzasadnieniem wybranego podejścia.

Jakie jeszcze operacje matematyczne można wykorzystać zamiast rozgałęzień?

Maskowanie, zasada przepełnienia, operatory przesuwania

Maskowanie pomaga zastąpić sprawdzanie warunku i przypisywanie wartości. W analogiczny sposób zastępuje się operator warunkowy. Wykorzystywać można również zasady przepełniania i operatory przesuwania (ang. shift operator).

Przykładowo, funkcja zwracająca większą wartość z dwóch argumentów w kodzie silnika graficznego CPUEngine wygląda następująco:

Grafika przedstawiająca funkcję zwracającą większą wartość z dwóch argumentów w kodzie silnika graficznego CPUEngine

Wykorzystując operator modulo, można również w łatwy i szybszy sposób pobierać wartość z tablicy:

Wykorzystanie operator modulo

Ponadto, warto doszukiwać się możliwości zastosowania operacji bitowych, na przykład przy szukaniu maski dla znaku w przypadku funkcji zwracającej wartość absolutną.

Jak zweryfikować wyniki?

Weryfikacja każdej zmiany jest bardzo zalecana. Przykład szukania mniejszej wartości pomaga łatwo zrozumieć branchless programming, ale nie zawsze taka modyfikacja oznacza, że kod będzie wykonywany szybciej.

Korzystając przykładowo z godbolt.org, można podejrzeć kod assemblera, który w przypadku pierwszej funkcji wygląda następująco:

Kod assemblera w funkcji z rozgałęzieniami

Natomiast w wersji bez rozgałęzień:

Kod assemblera w wersji bez rozgałęzień

Wynik nie jest spektakularny i wersja warunkowa w tym przypadku wcale nie zawiera mniejszej ilości instrukcji (wynik jest zależny od wybranego kompilatora – na potrzeby tego artykułu korzystano z gcc 10.3 x86-64), ale nie zawiera on w tym przypadku instrukcji skoku jge, ani jmp.

Ponadto, szybki test wydajnościowy na quick-bench.com pokazuje, że wersja napisana jako bezgałęziowa ręcznie, jest czasowo optymalniejsza niż wersja oryginalna. W teście porównywano wykonywanie poniższych funkcji dla wartości losowych (0,10) dla pierwszego i wartości 5 dla drugiego argumentu.

Grafika przedstawiająca wyniki testu wydajnościowego

Jak duże może to mieć znaczenie?

Trzeba mieć zawsze na uwadze, że współczesne kompilatory radzą sobie coraz lepiej z optymalizacją i często też same doszukują się (o ile to możliwe i pomocne) możliwości zmiany kodu na kod bez rozgałęzień. W powyższym przykładzie benchmark nie korzystał z optymalizacji kompilatora.

W przypadku optymalizacji O3, różnica wydajności obu wersji jest już niezauważalna. Kompilator zna metody usuwania gałęzi i automatycznie usprawnił nasz kod pod kątem wydajności. Ponadto, procesory wyposażane są w algorytmy optymalizacji, opóźnionych instrukcji skoku czy skomplikowanych modeli predykcji skoków.

Czasami jednak, nadal narzędzia mogą założyć coś innego niż programista. W krytycznych fragmentach kodu mogą liczyć się milisekundy. Przykładowo, pracując kiedyś nad projektem embeddedowym w zakresie cyfrowego przetwarzania na procesorze, poszukiwałem rozwiązania dla implementacji szybkich funkcji trygonometrycznych bez możliwości użycia biblioteki.

W tym przypadku implementacje bez rozgałęzień pomogły zredukować czasy obliczeń do poziomu czasów wykonywania analogicznych obliczeń z użyciem biblioteki. Nie było to oczywiście wdrażane bez uprzednich, skrupulatnych pomiarów. Warto więc sprawdzić, czy optymalizacja z użyciem programowania bez rozgałęzień faktycznie sprawia, że kod wykonuje się szybciej. A nie zawsze tak jest!

Kiedy korzystać z programowania bez rozgałęzień?

Mając takie narzędzia w zanadrzu, łatwo ulec pokusie zastępowania wszystkich instrukcji wersjami bez rozgałęzień. Nie jest to jednak dobra praktyka! Doświadczony programista zawsze weryfikuje, zanim podejdzie do optymalizacji. Uzasadnieniem usuwania naturalnych rozgałęzień powinna być zawsze wymierna i sprawdzona korzyść. Jeśli program faktycznie zyskuje na podejściu bez skoków i jest to krytyczny fragment, można pozwolić sobie na mniejszą czytelność kodu, zyskując na czasie wykonania.

Ocena:
Autor
Avatar
Paweł Jarosz

Software Developer i Technical Leader z ponad 7-letnim doświadczeniem w robotyce, ICT i embedded. Zafascynowany światem nowych technologii. Hobbystyczny robotyk i twórca gier. Amator perkusji i fotografii. Prywatnie dumny mąż i ojciec dwóch małych łobuziaków w tym samym wieku.

Zostaw komentarz

Twój adres e-mail nie zostanie opublikowany.

  • Fajny artykuł!

    Warto wspomnieć również o instrukcjach SSE/AVX/PTX (w sumie każda architektura ma takie), które również preferują branchless programming w wersji zwektoryzowanej. 😀

    Np.:
    __m256i _mm256_cmpgt_epi32 (__m256i a, __m256i b)
    __m256i _mm256_cmpeq_epi64 (__m256i a, __m256i b)
    __device__ unsigned int __vcmpgtu4 ( unsigned int a, unsigned int b )

    (oraz wiele innych instrukcji wykonujących max/min/abs itp)

    Warto także wspomnieć, iż (niestety) w większości kodu na świecie rozgałęzienia są używane jako tzw. „last-time-decision-making, czego niezbyt nasze procesory lubią. Jeśli przykładowo iterujemy po kolekcji elementów i w zależności od warunku wykonujemy jedną akcję albo drugą, to o wiele lepiej, zarówno z punktu widzenia optymalizacji szybkości/miejsca/czytelności posortować sobie tą kolekcję na dwa zbiory i na każdym z nich wykonać odpowiednią dla nich funkcję. 🙂 Ale jak to ze wszystkim bywa, istnieje pewna krzywa, która mówi „kiedy opłaca się takie coś zrobić”. Wszystko zależy od liczności, entropii itd. 😉

    Przykładowo taką pętelkę:

    foreach(item : Items)
    if(IsSquare(item))
    RenderSquare(item);
    else if(IsCircle(item))
    RenderCircle(item)

    można zamienić na taką:

    foreach(square : Squares)
    RenderSquare(square)

    foreach(circle : Circles)
    RenderCircle(circle)

    Według mnie o wiele bardziej czytelna. O wiele łatwiej testowalna oraz procesor się cieszy. 😉

  • Cześć Adam!
    Wielkie dzięki za opinię i cenne uzupełnienie! 🙂 Dobrze, że zwracasz uwagę na to, że zawsze „to zależy” – mam nadzieję, że wydźwięk artykułu też jest podobny i za optymalizację zabieramy się wtedy kiedy faktycznie jest to potrzebne i korzystne 🙂

    1. Cześć Marcin!
      Jeśli chodzi o ARM, to mamy tutaj szerokie pole popisu dla optymalizacji, przede wszystkim z użyciem właśnie neonowego SIMD, ale to temat na cały osobny artykuł! 😀

Może Cię również zainteresować

Pokaż więcej postów

Bądź na bieżąco

Zapisz się do naszego newslettera i otrzymuj najświeższe informacje ze świata Sii.

Otrzymaj ofertę

Jeśli chcesz dowiedzieć się więcej na temat oferty Sii, skontaktuj się z nami.

Wyślij zapytanie Wyślij zapytanie

Natalia Competency Center Director

Get an offer

Dołącz do Sii

Znajdź idealną pracę – zapoznaj się z naszą ofertą rekrutacyjną i aplikuj.

APLIKUJ APLIKUJ

Paweł Process Owner

Join Sii

ZATWIERDŹ

This content is available only in one language version.
You will be redirected to home page.

Are you sure you want to leave this page?