![\"Fragment](\"https:\/\/sii.pl\/blog\/wp-content\/uploads\/2022\/03\/picture_1.png\")
<\/a><\/figure>\n\n\n\nKiedy mo\u017ce pojawi\u0107 si\u0119 problem z instrukcjami warunkowymi?<\/h2>\n\n\n\n
Odpowied\u017a nasuwa si\u0119 sama i oczywi\u015bcie chodzi tutaj o krytyczne fragmenty programu, kt\u00f3rych wykonywanie mo\u017ce by\u0107 przez instrukcje warunkowe znacz\u0105co zwolnione. Jednak w celu zrozumienia, dlaczego problem mo\u017ce si\u0119 pojawi\u0107, nale\u017cy zrozumie\u0107 spos\u00f3b dzia\u0142ania procesora.<\/p>\n\n\n\n CPU u\u017cywa bowiem techniki potokowo\u015bci (ang. Instruction Pipelining)<\/strong>, aby zoptymalizowa\u0107 wykonywanie rozkaz\u00f3w procesora. S\u0105 one dzielone na specjalizowane grupy, dzi\u0119ki czemu mog\u0105 jednocze\u015bnie wykona\u0107 cz\u0119\u015b\u0107 pracy zwi\u0105zanej z wykonywaniem rozkazu, niczym na ultraszybkiej ta\u015bmie produkcyjnej. Dzi\u0119ki temu, zanim jeszcze dojdzie do egzekucji instrukcji, s\u0105 one pobierane i dekodowane, a ca\u0142o\u015b\u0107 zaz\u0119bia si\u0119 i wykonuje r\u00f3wnolegle.<\/p>\n\n\n\n W celu optymalizacji procesory pobieraj\u0105 instrukcje z wyprzedzeniem. Je\u015bli program posiada instrukcje warunkowe, CPU tak naprawd\u0119 zgaduje kilka instrukcji naprz\u00f3d. W przypadku napotkania w programie rozga\u0142\u0119zienia \u015bcie\u017cki wykonywania programu (czyli wyst\u0105pienia instrukcji skoku), procesor zak\u0142ada z g\u00f3ry okre\u015blon\u0105 drog\u0119, wi\u0119c dop\u00f3ki idziemy przewidzian\u0105 drog\u0105 wszystko jest w porz\u0105dku, ale problem pojawia si\u0119, kiedy logika programu zmieni kierunek<\/strong> i procesor musi si\u0119 zaadaptowa\u0107 do sytuacji \u2013 czyli w praktyce usun\u0105\u0107 cz\u0119\u015b\u0107 instrukcji i za\u0142adowa\u0107 nowy zestaw ponownie. Wsp\u00f3\u0142cze\u015bnie, szacuje si\u0119, \u017ce skoki zdarzaj\u0105 si\u0119 co kilkana\u015bcie instrukcji.<\/p>\n\n\n\n Z pomoc\u0105 przychodzi idea programowania \u201ebezga\u0142\u0119ziowego\u201d (ang. Branchless Programming). <\/strong>Jej g\u0142\u00f3wnym za\u0142o\u017ceniem jest eliminowanie instrukcji skoku, szczeg\u00f3lnie w przypadkach, je\u015bli znacz\u0105co wp\u0142ywaj\u0105 one na wydajno\u015b\u0107 programu. Mo\u017ce to ostatecznie i tak nie znale\u017a\u0107 zastosowania przy nowoczesnych j\u0119zykach interpretowanych czy coraz bardziej inteligentnych kompilatorach z wieloma opcjami optymalizacji, ale przy zadaniach specjalnych wymagaj\u0105cych najwy\u017cszej wydajno\u015bci i jak najmniejszych op\u00f3\u017anie\u0144, taka technika mo\u017ce okaza\u0107 si\u0119 pomocna.<\/p>\n\n\n\n Rozwa\u017caj\u0105c kod, najlepiej szuka\u0107 funkcji, kt\u00f3re wykonywane s\u0105 cz\u0119sto, w krytycznych fragmentach. Maj\u0105c funkcj\u0119 zwracaj\u0105c\u0105 mniejsz\u0105 z dw\u00f3ch warto\u015bci int:<\/p>\n\n\n\n zastan\u00f3w si\u0119, jak mo\u017cna pozby\u0107 si\u0119 instrukcji skoku w tego typu instrukcjach warunkowych.<\/p>\n\n\n\n Ot\u00f3\u017c mo\u017cna skorzysta\u0107 z instrukcji mno\u017cenia<\/strong>. W ko\u0144cu, je\u015bli wymno\u017cymy dan\u0105 warto\u015b\u0107 razy 1, nic si\u0119 nie zmieni, a zredukowa\u0107 warto\u015b\u0107 mo\u017cna mno\u017c\u0105c przez 0. Suma takich iloczyn\u00f3w zadzia\u0142a w tym przypadku identycznie jak powy\u017csza funkcja.<\/p>\n\n\n\n Znaj\u0105c tak\u0105 sztuczk\u0119, mo\u017cesz zamienia\u0107 dowolne warunki, a nawet skomplikowane switche<\/strong>. Korzystamy wi\u0119c ze schematu mno\u017cenia warto\u015bci przez warunek, kiedy dana warto\u015b\u0107 ma by\u0107 zwracana i dodawaniu kolejnych, analogicznych wyra\u017ce\u0144 dla nast\u0119pnych warunk\u00f3w.<\/p>\n\n\n\n Czasami warto r\u00f3wnie\u017c cache\u2019owa\u0107 warto\u015b\u0107 warunk\u00f3w i korzysta\u0107 z negacji<\/strong>. Program w efekcie daje identyczne wyniki jak wersja z warunkami. Zauwa\u017calna jest natomiast zmiana w czytelno\u015bci kodu i, w przypadku stosowania programowania bez rozga\u0142\u0119zie\u0144, nale\u017cy zadba\u0107 o odpowiedni\u0105 nazw\u0119 funkcji i komentarz z uzasadnieniem wybranego podej\u015bcia.<\/p>\n\n\n\n Maskowanie pomaga zast\u0105pi\u0107 sprawdzanie warunku i przypisywanie warto\u015bci. W analogiczny spos\u00f3b zast\u0119puje si\u0119 operator warunkowy. Wykorzystywa\u0107 mo\u017cna r\u00f3wnie\u017c zasady przepe\u0142niania i operatory przesuwania (ang. shift operator).<\/p>\n\n\n\n Przyk\u0142adowo, funkcja zwracaj\u0105ca wi\u0119ksz\u0105 warto\u015b\u0107 z dw\u00f3ch argument\u00f3w w kodzie silnika graficznego CPUEngine wygl\u0105da nast\u0119puj\u0105co:<\/p>\n\n\n\n Wykorzystuj\u0105c operator modulo<\/strong>, mo\u017cna r\u00f3wnie\u017c w \u0142atwy i szybszy spos\u00f3b pobiera\u0107 warto\u015b\u0107 z tablicy:<\/p>\n\n\n\n Ponadto, warto doszukiwa\u0107 si\u0119 mo\u017cliwo\u015bci zastosowania operacji bitowych, na przyk\u0142ad przy szukaniu maski dla znaku w przypadku funkcji zwracaj\u0105cej warto\u015b\u0107 absolutn\u0105.<\/p>\n\n\n\n Weryfikacja ka\u017cdej zmiany jest bardzo zalecana. Przyk\u0142ad szukania mniejszej warto\u015bci<\/strong> pomaga \u0142atwo zrozumie\u0107 branchless programming, ale nie zawsze taka modyfikacja oznacza, \u017ce kod b\u0119dzie wykonywany szybciej.<\/p>\n\n\n\n Korzystaj\u0105c przyk\u0142adowo z godbolt.org<\/a>, mo\u017cna podejrze\u0107 kod assemblera, kt\u00f3ry w przypadku pierwszej funkcji wygl\u0105da nast\u0119puj\u0105co:<\/p>\n\n\n\n Natomiast w wersji bez rozga\u0142\u0119zie\u0144:<\/p>\n\n\n\n Wynik nie jest spektakularny i wersja warunkowa w tym przypadku wcale nie zawiera mniejszej ilo\u015bci instrukcji (wynik jest zale\u017cny od wybranego kompilatora \u2013 na potrzeby tego artyku\u0142u korzystano z gcc 10.3 x86-64), ale nie zawiera<\/strong> on w tym przypadku instrukcji skoku jge, ani jmp. <\/strong><\/p>\n\n\n\n Ponadto, szybki test wydajno\u015bciowy na quick-bench.com<\/a> pokazuje, \u017ce wersja napisana jako bezga\u0142\u0119ziowa r\u0119cznie, jest czasowo optymalniejsza ni\u017c wersja oryginalna. W te\u015bcie por\u00f3wnywano wykonywanie poni\u017cszych funkcji dla warto\u015bci losowych (0,10) dla pierwszego i warto\u015bci 5 dla drugiego argumentu.<\/p>\n\n\n\n Trzeba mie\u0107 zawsze na uwadze, \u017ce wsp\u00f3\u0142czesne kompilatory radz\u0105 sobie coraz lepiej z optymalizacj\u0105 i cz\u0119sto te\u017c same doszukuj\u0105 si\u0119 (o ile to mo\u017cliwe i pomocne) mo\u017cliwo\u015bci zmiany kodu na kod bez rozga\u0142\u0119zie\u0144. W powy\u017cszym przyk\u0142adzie benchmark nie korzysta\u0142 z optymalizacji kompilatora.<\/p>\n\n\n\n W przypadku optymalizacji O3, r\u00f3\u017cnica wydajno\u015bci obu wersji jest ju\u017c niezauwa\u017calna<\/strong>. Kompilator zna metody usuwania ga\u0142\u0119zi i automatycznie usprawni\u0142 nasz kod pod k\u0105tem wydajno\u015bci. Ponadto, procesory wyposa\u017cane s\u0105 w algorytmy optymalizacji, op\u00f3\u017anionych instrukcji skoku czy skomplikowanych modeli predykcji skok\u00f3w.<\/p>\n\n\n\n Czasami jednak, nadal narz\u0119dzia mog\u0105 za\u0142o\u017cy\u0107 co\u015b innego ni\u017c programista. W krytycznych fragmentach kodu mog\u0105 liczy\u0107 si\u0119 milisekundy<\/strong>. Przyk\u0142adowo, pracuj\u0105c kiedy\u015b nad projektem embeddedowym<\/strong> w zakresie cyfrowego przetwarzania na procesorze, poszukiwa\u0142em rozwi\u0105zania dla implementacji szybkich funkcji trygonometrycznych bez mo\u017cliwo\u015bci u\u017cycia biblioteki.<\/p>\n\n\n\n W tym przypadku implementacje bez rozga\u0142\u0119zie\u0144 pomog\u0142y zredukowa\u0107 czasy oblicze\u0144 do poziomu czas\u00f3w wykonywania analogicznych oblicze\u0144 z u\u017cyciem biblioteki. Nie by\u0142o to oczywi\u015bcie wdra\u017cane bez uprzednich, skrupulatnych pomiar\u00f3w. Warto wi\u0119c sprawdzi\u0107, czy optymalizacja z u\u017cyciem programowania bez rozga\u0142\u0119zie\u0144 faktycznie sprawia, \u017ce kod wykonuje si\u0119 szybciej. A nie zawsze tak jest!<\/p>\n\n\n\n Maj\u0105c takie narz\u0119dzia w zanadrzu, \u0142atwo ulec pokusie zast\u0119powania wszystkich instrukcji wersjami bez rozga\u0142\u0119zie\u0144. Nie jest to jednak dobra praktyka! Do\u015bwiadczony programista zawsze weryfikuje<\/strong>, zanim podejdzie do optymalizacji. Uzasadnieniem usuwania naturalnych rozga\u0142\u0119zie\u0144 powinna by\u0107 zawsze wymierna i sprawdzona korzy\u015b\u0107.<\/strong> Je\u015bli program faktycznie zyskuje na podej\u015bciu bez skok\u00f3w i jest to krytyczny fragment, mo\u017cna pozwoli\u0107 sobie na mniejsz\u0105 czytelno\u015b\u0107 kodu, zyskuj\u0105c na czasie wykonania.<\/p>\n\n\n\n<\/a><\/figure>\n\n\n\nTechnika potokowo\u015bci<\/h3>\n\n\n\n
<\/a><\/figure>\n\n\n\n<\/a><\/figure>\n\n\n\nCzy mo\u017cna zoptymalizowa\u0107 wybieranie \u015bcie\u017cki wykonywania instrukcji?<\/h2>\n\n\n\n
<\/a><\/figure>\n\n\n\nInstrukcja mno\u017cenia<\/h3>\n\n\n\n
<\/a><\/figure>\n\n\n\nJakie jeszcze operacje matematyczne mo\u017cna wykorzysta\u0107 zamiast rozga\u0142\u0119zie\u0144?<\/h2>\n\n\n\n
Maskowanie, zasada przepe\u0142nienia, operatory przesuwania<\/h3>\n\n\n\n
<\/a><\/figure>\n\n\n\n<\/a><\/figure>\n\n\n\nJak zweryfikowa\u0107 wyniki?<\/h2>\n\n\n\n
<\/a><\/figure>\n\n\n\n<\/a><\/figure>\n\n\n\n<\/a><\/figure>\n\n\n\nJak du\u017ce mo\u017ce to mie\u0107 znaczenie?<\/h2>\n\n\n\n
Kiedy korzysta\u0107 z programowania bez rozga\u0142\u0119zie\u0144?<\/h2>\n\n\n\n