Mikrooptymalizacje są bez sensu

14 kwietnia 2020 / / 21 komentarzy

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:

10 simple tricks to optimize your C code in small embedded systems

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ę, że aż takie nastawienie na mikrooptymalizacje jest mimo wszystko rzadkością.

Ale zwracam tutaj uwagę na jeden ciekawy 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, że 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 8

Oczywiś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 nawet jeżeli nie ma, to akurat ta optymalizacja jest na tyle prosta, że 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 nawet nam się nie śniło. Natomiast jeżeli będziemy chcieli na siłę wyręczyć kompilator, to skąd on ma wiedzieć, że 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, że procesory często mają instrukcję porównania z zerem, natomiast nie mają porównania z dowolną liczbą. Dlatego jeżeli 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. Jeżeli funkcja ma jakieś argumenty albo zwracane wartości, to są one również przekazywane za pomocą 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, że 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, że 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, że 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 za pomocą 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, że 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, że 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 na obsługę iteratorów i warunków wyjścia, możemy ręcznie skopiować zawartość pętli kilka razy.

To jest kolejna optymalizacja, którą od dawna robią kompilatory. Nie ma żadnej potrzeby robić tego ręcznie i ryzykować, że 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, że 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, że czasem nasze przewidywania się nie sprawdzą. A zmiana rozmiaru zmiennej, czy dodanie znaku mogą mieć spore konsekwencje w dużym projekcie.

Jednak okazuje się, że 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ść, że 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 jeżeli 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. Jeżeli 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. Jeżeli 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, że założenia są niemożliwe do zrealizowania. Wtedy czeka nas trudna rozmowa.

No dobra, a co jeśli 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.

Jeżeli 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ą.

Categories: Bez kategorii

20 Comments

  1. Hubert

    14 kwietnia 2020 at 19:08

    Fajna optymalizacja dla osób nie wiedzących o short-circuit evaluation.
    Zamiast
    if(a && b && c)
    {
    foo();
    }

    if(a)
    {
    if(b)
    {
    if(c)
    {
    foo();
    }
    }
    }

    Reply
  2. Panicz Godek

    15 kwietnia 2020 at 08:55

    „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.”

    Rzeczywiście byłoby interesującym eksperymentem, żeby zmierzyć to, czy wersja PRO wspomnianego kontrolera generuje satysfakcjonująco zoptymalizowany kod, ale bez pomiarów niestety też nie można tego powiedzieć z pewnością.

    Z tego co patrzyłem na link, to jednak nie ma tam jakichś strasznych „zbrodni na kodzie”. Owszem, kod jest dziwny, ale widziałem w swoim życiu gorsze rzeczy. Na pewno pierwszym i niezbędnym krokiem do optymalilzacji jest pomiar. Zresztą kompilacja potrafi być bardzo nieliniowym procesem, i może się okazać, że w dużym programie opisane w linku techniki i tak nie będą miały pozytywnego wpływu na rozmiar kodu wynikowego.

    Z mojego doświadczenia chyba najlepszą techniką optymalizacji jest „sterowanie danymi”, tzn. technika, o której Kernighan mówi tutaj:
    https://youtu.be/8SUkrR7ZfTA?t=3026

    Język C daje dość ziarnistą kontrolę nad tym, ile pamięci zajmują struktury danych, i to niezależnie od tego, na jakim zestawie instrukcji program zostaje wykonany.

    Co więcej, embedded jest o tyle przyjemną branżą, że mamy całkowitą kontrolę nad sprzętem — i o ile jasne jest, że lepiej, żeby program zajmował mniej flasha, niż więcej (bo czasem możemy wziąć np. tańszy kontroler), o tyle kiedy sprzęt jest już zafiksowany, to minimalizacja rozmiaru programu ma mniejszą wartość, bo w przeciwnym razie wolna pamięć po prostu będzie leżała odłogiem (i jedyne, co możemy zyskać, to ewentualnie krótszy czas upgrade’u firmware’u)

    Reply
  3. Ech

    15 kwietnia 2020 at 21:26

    „To oszczędzimy jedną instrukcję asemblerową na każdej iteracji. JEDNĄ INSTRUKCJĘ ASEMBLEROWĄ!”

    Aż jedną na iteracje, a co jeśli iteracji jest miliard? To aż miliard instrukcji mniej podczas działania kodu za tylko odwrócenie logiki.

    Reply
    • Panicz Godek

      15 kwietnia 2020 at 22:20

      „Aż miliard instrukcji mniej” wcale nie musi nawet oznaczać, że kod będzie działał szybciej. Również pytanie, w jakim czasie mówimy o tym miliardzie. I jaki ten miliard będzie stanowił odsetek wszystkich instrukcji.

      Rozumowanie w kategoriach bezwzględnych jest tu mylące. Jeżeli ów „aż miliard instrukcji mniej” wydłuży czas życia na baterii o jedną sekundę na dziesięć lat, to to nie będzie miało znaczenia. Jeżeli owa jedna instrukcja nie będzie miała wpływu na responsywność urządzenia, to to też nie będzie miało znaczenia.

      Pierwszy krok przed optymalizacją to właśnie określenie, jakie kryteria są dla nas ważne — ze względu na co optymalizujemy.

      Nawet GCC pozwala optymalizować zarówno ze względu na szybkość (-O2 albo -O3), jak i na rozmiar kodu wynikowego (-Os), więc jeżeli program przestaje się mieścić we flashu, to jest nadzieja, że pogrzebanie w opcjach kompilacji nam pomoże.

      GCC daje też możliwość przeprowadzenia „link-time optimization” (-flto), który pomaga zmniejszyć rozmiar ostatecznego kodu po zlinkowaniu wszystkich plików obiektowych.

      Tak więc zanim przejdziemy do „psucia kodu”, zawsze warto najpierw sprawdzić, jakie mamy „wysokopoziomowe” możliwości optymalizacji.

      Reply
    • GAndaLF (Post author)

      16 kwietnia 2020 at 09:50

      Jeżeli w pętli robimy miliard iteracji to w większości przypadków mamy lepsze miejsca, gdzie możemy oszczędzić czas. Choćby sam zapis/odczyt tego miliarda danych do poszczególnych iteracji, albo wysyłanie/odbieranie po protokole komunikacyjnym. To są operacje rzędy wielkości wolniejsze niż pojedyncza instrukcja asemblerowa.

      Tym bardziej, że po pierwsze często takie optymalizacje są robione przy 100 iteracjach, bo kiedyś może być więcej. A po drugie jeżeli istnieje odpowiednia instrukcja asemblerowa – nie ma żadnego zysku, a nieczytelny kod pozostaje.

      Reply
  4. Piotr Fusik

    17 kwietnia 2020 at 08:34

    „Dzisiaj często są już instrukcje dzielenia wykonywane w jednym takcie zegara.”

    W jakim procesorze na przykład?

    Reply
  5. Piotr Fusik

    20 kwietnia 2020 at 12:33

    Dzięki. Instrukcje dzielenia są od lat ’70 (np. https://en.wikipedia.org/wiki/PDP-11_architecture), jeśli nie wcześniej. Ale nie znam ani jednego procesora z instrukcją dzielenia w jednym cyklu.

    Reply
    • GAndaLF (Post author)

      20 kwietnia 2020 at 13:01

      Ok, to się wyjaśniło 🙂

      Nawet nie wiedziałem, że operacja dzielenia była tak wcześnie.

      Reply
  6. Paczkaexpress

    15 maja 2020 at 14:10

    Pamiętam jak w jednej firmie, w której ostatnio pracował, zostałem niejako zmuszony do używania pseudo-optymalizacji w kodzie. Nie odbyło się to bezpośrednio, ale krótkowzroczność zarządu firmy i zespołu elektroników miała bezpośredni wpływ na zaistniałą sytuację.
    Nasza firma zajmowała się rozwojem systemów sterowania do silników bez-szczotkowych. Mieliśmy na celu osiągnięcie jak najlepszych charakterystyk dynamicznych systemu. Do tego celu musieliśmy zaimplementować dość skomplikowany sterownik, który byłby odporny na zakłócenia (wcześniej system był postawiony na dość prostym PID z generatorem trajektorii 2 rzędu).
    Na początku projektu okazało się, że firma wykorzystuje bardzo maja (i przestarzałą) jednostkę DSP z 32 kB pamięci flash z czego 16 kB było zajęte przez bootloader i zmienne trwałe (pamięć flash miała tylko 4 strony, każda po 8 kB). Po zaimplementowaniu podstawowych funkcjonalności takich jak protokół komunikacyjny, sterowniki czujników itp. Itd. Zostało może 4 kB na sterownik samego BLCD … W tej architekturze to oznaczało ze jestem w stanie wykonać 40 operacji na float, gdzie sterownik wymagał co najmniej 160 (zakładając, że chcemy mieć zaimplementowany pełen sterownik, a nie jakieś uproszczenie). Ostatecznie każdy float został zaimplementowany za pomocą przybliżenia intami (IQ math), tam, gdzie się dało mnożenie i dzielenie przez stałą zostawało zastąpione za pomocą przesunięć bitowych itp. Ostatecznie udało się odpalić sterownik w działającej postaci. Jednakże praca przy ograniczonej pamięci i z tak rozległą optymalizacją była bardzo ciężka i zaraz potem opuściłem firmę.

    Reply
    • GAndaLF (Post author)

      15 maja 2020 at 15:23

      Dzięki za komentarz. Opisujesz ciekawą sytuację, którą też parę razy widziałem, a z której „stakeholderzy” nie zdają sobie zwykle sprawy. Zmuszanie do robienia takich akcji – niby możliwych, ale strasznie nieprzyjemnych w utrzymaniu na dłuższą metę powoduje, że ludzie odchodzą, a nowi nie są w stanie zrozumieć co się dzieje i nie da się kontynuować projektu. Więc ostatecznie to oni najgorzej na tym wychodzą.

      Reply
  7. wiczek

    15 maja 2024 at 11:14

    Ja zacząłem definiować konkretne typy danych (np. uint16) po tym jak przesyłając int pomiędzy procesorem 8 bitowym a 32 bitowym dowiedziałem się, że int może mieć różną szerokość. Podobnie robię z przesyłaniem floatów. Mnożę go przez oczekiwaną przeze mnie rozdzielczość, wpisuję w inta o konkretnej szerokości i w zamian gdziekolwiek go odczytuję mam pewność, że odczytując go tą samą metodą mam oczekiwany przeze mnie wynik.

    Reply
  8. wiczek

    15 maja 2024 at 11:16

    Odwrócenie kolejności w pętli, to nie jest jakiś problem, czasem jest to nawet bardziej oczywiste.

    Reply

1 Pingback

  1. Pingback: Style Guide i Coding Standard - czy to już jakość? - ucgosu.pl

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *