Poza próbą napisania jak najsprytniejszego kodu robiącego wszystko w jednej linijce o czym pisałem ostatnio, drugim największym grzechem programistów C jest próba optymalizowania wszystkiego i wszędzie. Jest to koronny argument usprawiedliwiający nieczytelny kod. A ta optymalność bardzo często jest fikcją. Nie jest poparta żadnymi pomiarami dla naszego konkretnego przypadku. Bazuje tylko na legendach i przekazach ustnych kultywowanych przez kolejne pokolenia programistów C. O ile kiedyś – w zamierzchłych czasach – te zasady miały jakiś sens, teraz najczęściej kompilatory mogą wykonać tą robotę za nas. Albo nie musimy w ogóle się tym przejmować, bo już nam wystarczy RAMu. A my możemy cieszyć się kodem, który da się rozczytać.
Na czym polega problem?
Jakiś czas temu na znanym branżowym portalu natknąłem się na taki oto artykuł o optymalizacji kodu w C na mikrokontrolery:
Składa się on w całości z antywzorców, które przy okazji pokazują częste wśród programistów lowlevelowych podejście do optymalizacji. Czyli skupienie na małych usprawnieniach w pojedynczych linijkach – mikrooptymalizacjach.
Mamy tutaj dosyć hardkorowy zestaw. A używanie wielokrotnego dodawania zamiast mnożenia to już prawdziwa desperacja. Mam nadzieję, iż aż takie nastawienie na mikrooptymalizacje jest mimo wszystko rzadkością.
Ale zwracam tutaj uwagę na jeden interesujący szczegół. Wszystkie te optymalizacje były zrobione na kompilatorze Microchipa XC8 do PICów w darmowej wersji. Czyli wszystkie te zbrodnie na kodzie zostały popełnione, żeby nie kupować licencji PRO mającej dodatkowe opcje optymalizacji. Przecież to bez sensu! Ile będzie kosztować napisanie, pomiary, testy i utrzymanie tego bałaganu? Przecież pensje i czas programistów będą całe rzędy wielkości wyższe.
Ale przecież to nie jest wydumany problem z jakiegoś artykułu. Każdy z nas ma z takimi „usprawnieniami” do czynienia na co dzień. Poniżej kilka moich ulubionych przykładów.
Przesunięcie bitowe zamiast dzielenia przez dwa
Kiedyś tak podstawowa operacja jak dzielenie była bardzo kosztowna. Nie było instrukcji dzielenia wykonywanej w pojedynczym takcie zegara. Trzeba było kombinować. Powstawały specjalne algorytmy dzielenia.
I wtedy odkryto, iż zamiast dzielenia przez potęgi dwójki można zrobić przesunięcie bitowe. Natomiast operacja AND może zastąpić modulo, czyli resztę z dzielenia. Dlatego w kodzie zaczęły pojawiać się takie oto konstrukcje:
result = val >> 3; //dzielenie przez 8 result = val & (0x7); //modulo 8Oczywiście bardzo często te operacje bitowe były częścią jakiś większych obliczeń wykonywanych w jednym wyrażeniu:
//divide it by four and make sure it is positive return i > 0 ? i >> 2 : ~(i >> 2) + 1;Domyślilibyście się co robi ta linijka, gdyby nie było komentarza? Ile by to Wam zajęło?
Dzisiaj często są już instrukcje dzielenia wykonywane w jednej instrukcji procesora (co nie zawsze odpowiada jednemu taktowi zegara – dzięki Piotr Fusik za komentarz). Zanim weźmiesz się za tego typu optymalizację najpierw sprawdź listę komend swojego procesora! A choćby o ile nie ma, to akurat ta optymalizacja jest na tyle prosta, iż w dzisiejszych czasach powinien ją zrobić każdy szanujący się kompilator. Poza tym kompilator zna również wiele innych tricków optymalizujących dzielenie, o których choćby nam się nie śniło. Natomiast o ile będziemy chcieli na siłę wyręczyć kompilator, to skąd on ma wiedzieć, iż chodziło nam o dzielenie?
A poza tym wiecie jak działa przesunięcie bitowe na liczbach ujemnych? Polecam sprawdzić.
Instrukcje dzielenia w procesorach i optymalizacje kompilatora są już z nami od dawna. Jednak ten mit ciągle ma się dobrze. Poza tym jest dalej chętnie powielany na przykład na uczelniach. U mnie na studiach na przykład to był bardzo „chodliwy” temat.
Pętle iterujące po tablicach do zera
Ta optymalizacja bazuje na fakcie, iż procesory często mają instrukcję porównania z zerem, natomiast nie mają porównania z dowolną liczbą. Dlatego o ile zamiast tradycyjnej pętli iterującej po tablicy:
for (i = 0; i < MAX; i++)zapiszemy to tak:
for (i = MAX; i >= 0; i--)To oszczędzimy jedną instrukcję asemblerową na każdej iteracji. JEDNĄ INSTRUKCJĘ ASEMBLEROWĄ! Za cenę odwrócenia całej logiki operacji na tablicach do góry nogami.
Obsługiwanie indeksów w odwrotnej kolejności jest nieintuicyjne, a przez to drastycznie wzrasta szansa popełnienia błędu. Szczególnie przy późniejszych modyfikacjach. Czy ta jedna instrukcja asemblerowa to naprawdę tak wielki zysk? Czy warto dla tej jednej instrukcji robić to sobie i innym? Szczerze wątpię.
Jeżeli jednak faktycznie ma to dla nas aż takie znaczenie – po raz kolejny zacznijmy od sprawdzenia, czy faktycznie nie ma tej instrukcji asemblerowej do zwykłego porównania.
Nieużywanie funkcji, żeby oszczędzić na instrukcji skoku
Aby wykonać funkcję procesor wykonuje instrukcję skoku do miejsca, gdzie znajduje się kod funkcji. Następnie kiedy skończy jej przetwarzanie – wykonuje skok powrotny do miejsca wywołania. o ile funkcja ma jakieś argumenty albo zwracane wartości, to są one również przekazywane dzięki rejestrów albo stosu. Całość więc może zajmować kilka instrukcji. Aby oszczędzić te instrukcje wystarczy zrezygnować z użycia funkcji.
Efektem są bardzo długie procedury bez funkcji pomocniczych, czy wklejanie w wielu miejscach tego samego kodu. Czasem duplikacja wynika z tego, iż nie zauważymy, albo nam się nie chce. Jednak tutaj mamy do czynienia z dużo gorszym problemem. Osoba tak postępująca dobrze zna alternatywę, jest święcie przekonana, iż ma rację i próbuje nas przekonać swoimi argumentami.
Dlaczego tak robiono? W zamierzchłych czasach częstotliwość taktowania procesorów była niska i czasem mogło to mieć wpływ na szybkość działania programu. Jednak optymalizacja skoków do funkcji jedna z głównych rzeczy, jaką twórcy procesorów starali się usprawnić. Dlatego mamy dziś na przykład specjalne rejestry przechowujące adres powrotu. Dzięki temu skok trwa mniej instrukcji. A z drugiej strony częstotliwości taktowania tak przyspieszyły, iż teraz pojedyncze instrukcje to często kwestia nanosekund.
Poza tym znowu – tę optymalizację powinien ogarnąć każdy szanujący się kompilator. Zwykle możemy mu sami zasugerować takie rozwiązanie dzięki dyrektywy inline. Ale tutaj uwaga – inline to tylko sugestia – kompilator może ją zignorować, może też samodzielnie inline’ować w innych miejscach. Najlepiej poczytać jak to obsługuje nasz kompilator i przetestować.
Kolejna kwestia jest taka, iż te instrukcje skoku to i tak nie jest czysty zysk. Zużywamy więcej pamięci programu, a poza tym nowoczesne procesory mają cache’owanie instrukcji. I często może się okazać np. przy obsłudze switch-case, iż dzięki funkcjom dla poszczególnych case’ów kod zadziała szybciej.
Macra zamiast funkcji
Kolejna odsłona tego samego problemu to używanie makr zamiast funkcji. Skoro duplikacja jest takim problemem – zrobimy macro, a preprocesor wklei kod bez skoków. Wilk syty i owca cała – ktoś może pomyśleć. Jednak macra to nie do końca to samo co funkcje. Nie mają kontroli typów, przez co kompilator nie wykryje części błędów. Poza tym trudno je debugować. Macra powinny być używane tylko w szczególnych przypadkach. Natomiast lepsze już są omawiane wcześniej funkcje inline.
Loop unrolling
Żeby instrukcje w pętli wykonywały się szybciej, bez straty czasu w obsługę iteratorów i warunków wyjścia, możemy manualnie skopiować zawartość pętli kilka razy.
To jest kolejna optymalizacja, którą od dawna robią kompilatory. Nie ma żadnej potrzeby robić tego manualnie i ryzykować, iż się wyłożymy na zmienionej obsłudze warunków wyjścia, na copy paste albo na późniejszej edycji.
Wykorzystanie tej samej zmiennej do różnych celów
Skoro mamy w funkcji jakąś zmienną tymczasową, użyliśmy ją i już jej więcej nie potrzebujemy, to przecież możemy ją użyć do przechowywania innych tymczasowych wartości. Dlaczego ma się marnować? Czasem możemy posłużyć się niejawnym rzutowaniem jak potrzebujemy różnych typów zmiennych. No ale ostatecznie przecież oszczędzamy pamięć.
Sam na początku bardzo często stosowałem tą technikę. Dopiero po dłuższym czasie dotarło do mnie, iż to bez sensu. Kompilator widzi jaka zmienna lokalna jest używana w jakim miejscu i poradzi sobie z ich czasem życia. My natomiast możemy stworzyć różne zmienne i nadać im nazwy adekwatne do wykonywanej roli zamiast tmp1.
Minimalizowanie rozmiaru zmiennych
Na początku nauki C dowiadujemy się o zmiennych 8, 16 i 32-bitowych. Jest to zaproszenie do wybierania zawsze najmniejszego typu nadającego się do naszych obliczeń. Tak samo z decyzją, czy chcemy użyć zmiennej ze znakiem czy bez.
Problem w tym, iż czasem nasze przewidywania się nie sprawdzą. A zmiana rozmiaru zmiennej, czy dodanie znaku mogą mieć spore konsekwencje w dużym projekcie.
Jednak okazuje się, iż w większości przypadków możemy używać rozmiaru natywnego dla naszego procesora – czyli np. dla ARMów będą to 32 bity. Co więcej będzie to bardziej optymalne – mamy pewność, iż wszystkie instrukcje działają na tym rozmiarze zmiennej i kompilator nie doda żadnych offsetów, paddingów i innych cudów.
Kiedyś usłyszałem taką poradę dotyczącą wyboru typu zmiennych na ARMach: „Jeżeli zmienna służy do operacji arytmetycznych to wybieraj int32, a jak do operacji bitowych to uint32.”
No dobrze, ale przecież marnujemy RAM. W dzisiejszych czasach RAMu i tak mamy najczęściej w nadmiarze. A poza tym te zmienne są bardzo często lokalne dla funkcji – czyli o ile nie przepełnimy stosu, rozmiar nie będzie miał aż takiego znaczenia. Wtedy nie możemy się pomylić, bo typ opieramy na rodzaju wykonywanych operacji. A nie używamy tej samej zmiennej do operacji arytmetycznych i bitowych, prawda?
Oczywiście są wyjątki od tej reguły. Ale kiedy nie będzie ona pasowała do twojego zastosowania, od razu to zobaczysz. Na przykład jak chcesz coś zapisać do pamięci, wysłać po protokole komunikacyjnym, używasz dużych tablic, czy masz niesamowicie mało RAMu.
W takim razie jak powinniśmy optymalizować?
Przede wszystkim powinniśmy pisać solidny i czytelny kod. o ile dobrze wywiążemy się z tego zadania, to czas wykonania powinien być bliski optymalnemu. Dajmy kompilatorom wykonywać ich robotę.
Bjarne Stroustrup dobrze ujął zależność między dobrze napisanym kodem a optymalizacją:
„Clean code is easy to read with performance close to optimal so as not to tempt people to make the code messy with unprincipled optimizations.”
Z kolei Steve McConnel w mojej ulubionej książce o programowaniu – „Code complete” – napisał:
Optymalizacja to zmiana przyspieszająca działanie kodu kosztem czytelności. o ile zmiana przyspiesza działanie bez pogorszenia czytelności, jest to po prostu dobra praktyka. I nie ma żadnych wymówek, żeby jej nie stosować.
Jeżeli konieczna jest optymalizacja, to zanim cokolwiek zmienimy musimy wykonać pomiary potwierdzające naszą tezę. Pomiary pomogą nam też zidentyfikować miejsca, gdzie powinniśmy szukać zysków. Zwykle to są pojedyncze fragmenty odpowiadające za cały performance. Zasada Pareto ma tutaj zastosowanie.
Mając już bottlenecki poszukaj typowych winowajców spadku wydajności:
- oczekiwanie na zasoby
- synchronizacja
- komunikacja
- złożoność obliczeniowa
Te problemy dużo łatwiej rozwiązać mądrze zmieniając koncepcję działania danego fragmentu systemu, a nie szukając oszczędności pojedynczych cykli procesora i to często w zupełnie nieistotnych miejscach.
Czasem też się zdarza, iż założenia są niemożliwe do zrealizowania. Wtedy czeka nas trudna rozmowa.
No dobra, a co jeżeli muszę robić mikrooptymalizacje?
Tutaj po raz kolejny polecam książkę „Code Complete” i rozdział dotyczący optymalizacji. Ten rozdział to lektura obowiązkowa przed rozpoczęciem walki o pojedyncze instrukcje.
Steve McConnell pokazuje tam różne przykłady z różnych języków, gdzie te same zmiany w różnych miejscach powodują różne efekty. Bardzo często efektem jest pogorszenie wydajności. Czasem na jednej wersji kompilatora kod jest szybszy, a na innej wolniejszy. Po prostu nie da się doszukać tam jakiegoś sensownego zestawu reguł. Musimy opierać się w 100% na pomiarach i testowaniu kolejnych hipotez.
Właśnie dlatego powstały słynne zasady optymalizacji:
Rule 1: Don’t do it.
Rule 2: (for experts only): Don’t do it yet.”
A jakie Ty znasz mikrooptymalizacje przynoszące więcej problemów niż korzyści? Koniecznie podziel się nimi w komentarzach.
o ile chcesz dowiedzieć się więcej o tym, jak pisać dobry kod w C – zapisz się na newsletter przez formularz poniżej. Przygotowuję właśnie szkolenie online „C dla zaawansowanych” i na liście mailowej informacje na ten temat na pewno Cię nie ominą.
