logo elektroda
logo elektroda
X
logo elektroda
Adblock/uBlockOrigin/AdGuard mogą powodować znikanie niektórych postów z powodu nowej reguły.

Optymalizacja dzielenia modulo dla uint32_t w wyświetlaczu 6-segmentowym

krzysztofh 16 Mar 2017 10:12 4671 53
  • #1 16349129
    krzysztofh
    Poziom 29  
    Witam.
    Zgłaszam się znów z prośbą o radę.
    W programie, który staram się zoptymalizować obsługuję zmienne uint32_t.
    Mam świadomość problemów z mnożeniem i dzieleniem takich liczb i próbuję szczególnie dzielenia unikać jak ognia, ale nie zawsze się da.

    Na tapecie jest m.in. sprawa obsługi wyświetlacza 6-segmentowego.
    I pytanie czy jeżeli w celu wyłuskania najmniej znaczącej cyfry robię dzielenie modulo przez 10, liczby np uint16_t optymalnej pod kątem szybkości będzie:

    Kod: C#
    Zaloguj się, aby zobaczyć kod


    czy może:

    Kod: C#
    Zaloguj się, aby zobaczyć kod


    Nie jestem pewny mechanizmu dzielenia modulo. Jeżeli jest tak jak myślę to w pierwszym przypadku liczba operacji dzielenia będzie wielokrotnie większa niż w drugim, gdzie zamaskowałem nieistotne, z punktu widzenia wyłuskania najmłodszej cyfry z najmłodszego bajtu, najstarszy bajt.

    To oczywiście tylko przykład bo zaprezentowałem tylko część kodu.
    W dalszej muszę dzielić modulo także liczbę 32-bitową.
  • #2 16349233
    michalko12
    Specjalista - Mikrokontrolery
    Nie kombinuj, nie jesteś na tyle biegły, żeby pozwolić sobie na zabawy w optymalizację. Tam gdzie logiczne wydaje się użycie typów 32b i dzielenia i mnożenia na nich to tam ich używaj. Nie martw się wydajnością, kompilator i procesor lepiej sobie poradzą z takimi zadaniami niż ty z optymalizacjami.

    krzysztofh napisał:
    value = (value_wysw && 0xff00) %10;

    Nie ten operator chyba chciałeś zastosować. W ramach ćwiczeń skorzystaj sobie z CManiaka i tam zobaczysz jaką bzdurę wymyśliłeś.
  • #3 16349239
    malcompl
    Poziom 13  
    Zależy od kompilatora i jego możliwości. Aby dowiedzieć się jak zrobi to Twój kompilator z Twoimi ustawieniami optymalizacji, musisz popatrzeć na binarkę lub wygenerowanego asma ;)

    BTW masz błąd z podwójnym operatorem & w drugim przypadku.

    EDIT:
    Z powodu pośpiechu i drobnej, acz wielce istotnej pomyłki, jakoby 10 miała tutaj szczególne znaczenie, co jest oczywiście totalną bzdurą, wywaliłem fragmenty mogące wprowadzać w błąd ;)
  • #4 16349275
    krzysztofh
    Poziom 29  
    OK, już poprawiłem oczywisty błąd.
    Tylko dalej nie wiem, czy dzielenie modulo sprowadza się do wielokrotnego dzielenia przez 10 (w tym przypadku) aż do wyłuskania najmłodszej cyfry, bo jeżeli tak to takie działanie byłoby obarczone mniejszą liczbą operacji dzielenia.
    Tak jak już pisałem, w najgorszym przypadku mogę mieć do czynienia z dzielną o wartości 99 mln i co wtedy, ile będzie trwało to dzielenie modulo?
  • #5 16349326
    michalko12
    Specjalista - Mikrokontrolery
    krzysztofh napisał:
    Tylko dalej nie wiem, czy dzielenie modulo sprowadza się do wielokrotnego dzielenia przez 10 (w tym przypadku) aż do wyłuskania najmłodszej cyfry, bo jeżeli tak to takie działanie byłoby obarczone mniejszą liczbą operacji dzielenia.
    Tak jak już pisałem, w najgorszym przypadku mogę mieć do czynienia z dzielną o wartości 99 mln i co wtedy, ile będzie trwało to dzielenie modulo?

    Tyle samo zajmuje czasu co zwykłe dzielenie. Dzieląc przez modulo 10 i tak dzieli przez 10 tylko jako wynik tej operacji brana jest reszta z dzielenia, a nie iloraz. I jak dzieli 1000000 przez 10 to nie oznacza, że wykonuje odejmowanie 100000 razy!
    http://eduinf.ogicom.pl/inf/alg/006_bin/0012.php

    Dodano po 2 [minuty]:

    malcompl napisał:
    Akurat dla modulo 10, wystarczy chyba wiedza o kilku ostatnich bitach liczby...

    Nieprawda.
  • #6 16349337
    malcompl
    Poziom 13  
    michalko12 napisał:
    malcompl napisał:
    Akurat dla modulo 10, wystarczy chyba wiedza o kilku ostatnich bitach liczby...
    Nieprawda.

    Arghh racja, ale wtopa, za dużo wysokopoziomowych shitów ostatnio na głowie ;)
  • #7 16349371
    krzysztofh
    Poziom 29  
    Może odrobinę więcej światła na ten temat, proszę.

    Może w takim razie coś takiego uprości obliczenia?

    Kod: C#
    Zaloguj się, aby zobaczyć kod


    zmienna value jest zadeklarowana jako uint8_t, a value_wysw jako uint32_t.
  • Pomocny post
    #8 16349394
    dondu
    Moderator na urlopie...
    Zastanów się jaka wartość wyjdzie zawsze z tego i dlaczego:
    Kod: C / C++
    Zaloguj się, aby zobaczyć kod

    Poćwicz sobie w Cmaniaku: http://mikrokontrolery.blogspot.com/p/cmaniak-kompilator-jezyka-c-online.html
    Kod: C / C++
    Zaloguj się, aby zobaczyć kod

    Przy okazji kurs C w CManiaku: http://mikrokontrolery.blogspot.com/2011/02/kurs-jezyka-c-spis-tresci.html
  • #9 16349595
    krzysztofh
    Poziom 29  
    No tak, ale wstyd. Wszystko dlatego, że za rzadko siadam do C.

    Już wiem, że aby zamaskować najbardziej znaczące bity, trzeba tak:

    Kod: C#
    Zaloguj się, aby zobaczyć kod


    Jeżeli spodziewamy się liczby 32 bitowej, to 0x000000ff.
    Kod na sens pod warunkiem, że liczba w najmłodszym bajcie będzie większa niż >=10.
    Trzeba jeszcze nad tym popracować.
    Nie potrafię tylko odpowiedzieć sobie czy taki kod będzie szybszy niż zwykłe dzielenie całej liczby %10.
  • Pomocny post
    #10 16349605
    grko
    Poziom 33  
    Może i będzie szybszy. Ale nie da na pewno oczekiwanego rezultatu. Nic lepszego nie wymyślisz od tradycyjnego:

    Kod: C / C++
    Zaloguj się, aby zobaczyć kod
  • #11 16349609
    michalko12
    Specjalista - Mikrokontrolery
    krzysztofh napisał:
    Nie potrafię tylko odpowiedzieć sobie czy taki kod będzie szybszy niż zwykłe dzielenie całej liczby %10.

    Czy Ty czytasz to co się Tobie pisze?!
    Ten kod i te optymalizacje to jest bzdura! Nie będzie Ci to w ogóle działało!
  • #12 16349939
    krzysztofh
    Poziom 29  
    Dziękuję wszystkim za pomocne posty.
    Kolego michalko12, czytam to co piszesz, czytam, ale nie znajduję na wszystko jasnej odpowiedzi, albo może nie przyszło ci do głowy, że nie dysponuję taką wiedzą jak Ty i dlatego ten temat, aby coś więcej się nauczyć.

    Tyle jest na Elce o unikaniu dzielenia w AVRach. Toż to najgorsza zmora. Próbowałem coś zoptymalizować. Fakt, że trochę błądzę i zaprezentowany kod na początku był całkiem nietrafiony a nawet ten ostatni mój przykład niestety nie jest poprawny. Przyznać jednak muszę że liczyłem na większe wsparcie. Nie na zasadzie nie bo nie i już. Wiem że takiego kodu nie zastosuję bo nie jest optymalny i to moja nauka ale dlaczego maskowanie części zmiennej nie jest poprawne już nikt nie wyjaśnił. I nie chodzi tu o mój przykład bo faktycznie jest obarczony błędem, ale zamaskowanie dwóch bajtów w 32 bitowej zmiennej daje zapis jako 16 bit. Dlaczego takie działanie nic nie da, nie wiem. Uczę się na błędach, ale ile ta nauka byłaby efektywniejsza gdybym zrozumiał sedno sprawy.
    Asemblera nie znam i nie zamierzam się uczyć, bo mi życia zbraknie. To co robię to tylko w ramach hobby.
    Jak już pisałem będę miał do czynienia z liczbą bliską 100 mln w najgorszym przypadku, ale program też takie przypadki będzie musiał obsłużyć. Aby obsłużyć najbardziej znaczącą cyfrę będzie dzielona modulo dłuugo. Ale skoro nic innego nie można zastosować, trudno.
  • #13 16349969
    Freddie Chopin
    Specjalista - Mikrokontrolery
    krzysztofh napisał:
    Jak już pisałem będę miał do czynienia z liczbą bliską 100 mln w najgorszym przypadku, ale program też takie przypadki będzie musiał obsłużyć. Aby obsłużyć najbardziej znaczącą cyfrę będzie dzielona modulo dłuugo.

    Sprawdziłeś jak długo, czy tylko tak Ci się wydaje?
  • Pomocny post
    #15 16350034
    michalko12
    Specjalista - Mikrokontrolery
    krzysztofh napisał:
    Tyle jest na Elce o unikaniu dzielenia w AVRach.

    Nie spotkałem się, może nie ta "elka".
    krzysztofh napisał:
    Aby obsłużyć najbardziej znaczącą cyfrę będzie dzielona modulo dłuugo.

    Nie czytasz! Nie interesuje Cię to co się do Ciebie pisze.
    Jeszcze raz Ci to napiszę, czy w zmiennej 32b będzie wartość 10 czy 1000000000 potrwa to mniej więcej tyle samo czasu, a konkretniej to AVR obrobi to w około 600 cykli ( około 200 cykli dla liczby 16b) . Czy to dużo czy mało, to zależy od konkretnej sytuacji.
  • #16 16350050
    grko
    Poziom 33  
    @krzysztofh To w takim razie po co sie tym martwisz? Prezentujesz postawę dość popularną na tym forum: "nie zastosuję dzielenia/floata/printf/scanf/c/etc" bo to nie jest optymalne i w zajmie to tych parę bajtów pamięci więcej. Nieważne, że tego typu osoby robią co chwilę delay_ms albo nie potrafią porządnie napisać drivera do uarta na przerwaniach. Tymczasem warto się zastanowić gdzie się stosuje dany mechanizm i jaki będzie wpływ wydajność całego systemu.
  • #17 16350054
    krzysztofh
    Poziom 29  
    Ok przyjmuję to skoro ta piszesz, ale skoro tak że 16 bit liczba będzie wymagała trzykrotnie mniej cykli to czy nie ma sensu rzutować 32bit do 16 jak przy modulo ważne są młodsze bity? Tego nie pojmuję. Mam 6 cyfr i dla każdej trzeba daną wyłuskać.

    Dodano po 3 [minuty]:

    grko napisał:
    @krzysztofh To w takim razie po co sie tym martwisz? Prezentujesz postawę dość popularną na tym forum: "nie zastosuję dzielenia/floata/printf/scanf/c/etc" bo to nie jest optymalne i w zajmie to tych parę bajtów pamięci więcej. Nieważne, że tego typu osoby robią co chwilę delay_ms albo nie potrafią porządnie napisać drivera do uarta na przerwaniach. Tymczasem warto się zastanowić gdzie się stosuje dany mechanizm i jaki będzie wpływ wydajność całego systemu.

    Akurat w całym programie nie użyłem _delay_ms ani razu
  • #18 16350066
    grko
    Poziom 33  
    Cytat:
    Ok przyjmuję to skoro ta piszesz, ale skoro tak że 16 bit liczba będzie wymagała trzykrotnie mniej cykli to czy nie ma sensu rzutować 32bit do 16 jak przy modulo ważne są młodsze bity?


    Zależy czy Twoja dana wejściowa (ta 32 bitowa) przekracza zakres uint16_t (65536). Jeżeli tak, to rzutowanie na uint16_t da błędny wynik. Jeżeli nie, to po co użyłeś uint32_t?
  • Pomocny post
    #20 16350107
    grko
    Poziom 33  
    No to możesz próbować czegoś w stylu:

    Kod: C / C++
    Zaloguj się, aby zobaczyć kod


    Może zaozczędzisz parę cykli ;P
  • #21 16350128
    krzysztofh
    Poziom 29  
    Faktycznie sprawdziłem to rzutowanie i teraz wiem, gdzie popełniałem błąd.
    Patrzyłem na liczbę 32 bit jako na High Word i Low Word rozdzielnie.
    Błędnie sądziłem że jak zamaskuję starsze bajty to w młodszych nic się nie zmieni skoro Low Word nie ulegnie zmianie.
  • #22 16350139
    grko
    Poziom 33  
    Mozna się jeszcze pobawić z look up table i napisać procedurę na tym bazującą. Być może będzie to trochę szybsze.
  • #23 16351167
    krzysztofh
    Poziom 29  
    @grko zastosowałem Twój kod i po kompilacji program rośnie o 16 bytes w stosunku do dzielenia moduo bez warunków (if). Jeszcze nie miałem okazji sprawdzić tego programując Atmegę, ale czy to oznacza dłuższą obsługę dzielenia w tym przypadku, czy nie koniecznie wielkość programu po kompilacji musi oznaczać dłuższe działanie.
  • #25 16351214
    Freddie Chopin
    Specjalista - Mikrokontrolery
    Teraz tłumaczenie artykułu na polski. Użycie reszty z dzielenia sprawiło, że jedna iteracja obliczeń zajmowała 3000 cykli czyli 20 mikrosekund przy zegarze 16MHz. Co za marnotrawstwo - 20 mikrosekund raz na niewiadomoile <: No bo na pewno nie będzie to liczone częściej niż 1x na sekundę (bo nie ma to sensu). W takim wypadku te obliczenia obciążają układ w ~0.02%!
  • #26 16351232
    BlueDraco
    Specjalista - Mikrokontrolery
    Dodajmy, że problem zbyt wolnego dzielenia, o ile rzeczywiście występuje, można rozwiązać zastępując drogi i wolny AVR przez tańszy i szybszy uC z 32-bitowym rdzeniem. ;)
  • #27 16351322
    Konto nie istnieje
    Konto nie istnieje  
  • #28 16351499
    malcompl
    Poziom 13  
    krzysztofh napisał:
    @grko zastosowałem Twój kod i po kompilacji program rośnie o 16 bytes w stosunku do dzielenia moduo bez warunków (if).

    Jest większe bo będzie więcej kodu.

    Normalnie dla 32bit byłby prawdopodobny call do udivmodsi4, niezaleznie jaka wartość znajdowałaby się w zmiennej. Kod @grko bada jaka realnie wartość znajduje się w zmiennej i wywołuje dedykowaną wersję zalezną od rozmiaru typu, dla 16bit udivmodhi4, dla 8bit udivmodqi4.

    Dziwnie, że sam kompilator takiego kodu nie generuje dla Os.
    Na x86/x64 dosyć dużo podobnych tricków jest używanych przez optymalizatory, wykorzystując różne ciekawe możliwości lub intrinsic.

    Czy będzie to szybsze, zależy jak zaimplementowano oraz jaki kod wygeneruje kompilator do tych funkcji. Można naiwnie założyć, że dla każdego większego typu będzie to 2x więcej niż dla 2x mniejszego. Ale żeby być pewnym to wypadałoby to zbadać. Bo całkiem możliwe, że różnice nie będą porywające, więc jeśli to nie krytyczne, to jak koledzy mówili wyżej, olać sprawę. A jak mimo tych tricków dalej będzie klapa, to jak wyżej może warto zmienić architekturę jeśli to możliwe ;)

    krzysztofh napisał:

    czy nie koniecznie wielkość programu po kompilacji musi oznaczać dłuższe działanie.

    Nie zawsze mniejszy kod == szybszy.

    Czasami nawet różne instrukcje mogą w rezultacie dać pożądany wynik różnymi sposobami, np. pod x86 wyzerowanie rejestru poprzez standardowe mov eax, 0 jest wolniejsze niż xor-owanie: xor, eax, eax ;)
  • #29 16351533
    Konto nie istnieje
    Konto nie istnieje  
  • #30 16351561
    malcompl
    Poziom 13  
    Piotrus_999 napisał:
    Nie wiem skąd bierzesz takie rewelacje, ale się mylisz
    A temat nie dotyczy AVR-a? ;)

    Rozmiary w bitach z mojej wypowiedzi odnosiły się do długości typu, a nie platformy, a funkcje pochodzą z libc, czy tam avrlibc...
REKLAMA