Elektroda.pl
Elektroda.pl
X

Wyszukiwarki naszych partnerów

Wyszukaj w ofercie 200 tys. produktów TME
Kategoria: Kamery IP / Alarmy / Automatyka Bram
Montersi
Proszę, dodaj wyjątek elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

Działania na dużych liczbach

krzysztofh 16 Mar 2017 10:12 2721 53
  • #1 16 Mar 2017 10:12
    krzysztofh
    Poziom 28  

    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: csharp
    Zaloguj się, aby zobaczyć kod


    czy może:

    Kod: csharp
    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 16 Mar 2017 11:07
    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 16 Mar 2017 11:08
    malcompl
    Poziom 12  

    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 16 Mar 2017 11:26
    krzysztofh
    Poziom 28  

    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 16 Mar 2017 11:54
    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 16 Mar 2017 11:59
    malcompl
    Poziom 12  

    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 16 Mar 2017 12:17
    krzysztofh
    Poziom 28  

    Może odrobinę więcej światła na ten temat, proszę.

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

    Kod: csharp
    Zaloguj się, aby zobaczyć kod


    zmienna value jest zadeklarowana jako uint8_t, a value_wysw jako uint32_t.

  • Pomocny post
    #8 16 Mar 2017 12:31
    dondu
    Moderator Mikrokontrolery Projektowanie

    Zastanów się jaka wartość wyjdzie zawsze z tego i dlaczego:

    Kod: c
    Zaloguj się, aby zobaczyć kod

    Poćwicz sobie w Cmaniaku: http://mikrokontrolery.blogspot.com/p/cmaniak-kompilator-jezyka-c-online.html
    Kod: 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 16 Mar 2017 14:28
    krzysztofh
    Poziom 28  

    No tak, ale wstyd. Wszystko dlatego, że za rzadko siadam do C.

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

    Kod: csharp
    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 16 Mar 2017 14:32
    grko
    Poziom 31  

    Może i będzie szybszy. Ale nie da na pewno oczekiwanego rezultatu. Nic lepszego nie wymyślisz od tradycyjnego:

    Kod: c
    Zaloguj się, aby zobaczyć kod

  • #11 16 Mar 2017 14:34
    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 16 Mar 2017 18:10
    krzysztofh
    Poziom 28  

    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 16 Mar 2017 18:21
    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 16 Mar 2017 19:01
    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 16 Mar 2017 19:08
    grko
    Poziom 31  

    @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 16 Mar 2017 19:12
    krzysztofh
    Poziom 28  

    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 16 Mar 2017 19:13
    grko
    Poziom 31  

    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 16 Mar 2017 19:27
    grko
    Poziom 31  

    No to możesz próbować czegoś w stylu:

    Kod: c
    Zaloguj się, aby zobaczyć kod


    Może zaozczędzisz parę cykli ;P

  • #21 16 Mar 2017 19:33
    krzysztofh
    Poziom 28  

    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 16 Mar 2017 19:36
    grko
    Poziom 31  

    Mozna się jeszcze pobawić z look up table i napisać procedurę na tym bazującą. Być może będzie to trochę szybsze.

  • #23 17 Mar 2017 08:04
    krzysztofh
    Poziom 28  

    @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 17 Mar 2017 08:38
    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 17 Mar 2017 08:47
    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 17 Mar 2017 09:47
    Piotrus_999
    Poziom 39  

    Wytłumaczę to inaczej. Jak liczysz tylko na polach, nie możesz w słupku,a do danych pomocniczych masz tylko palce u stóp, to możesz sobie wyobrazić złożoność dzielenia np 34574325przez 53454.

    Dodano po 11 [minuty]:

    A jak weźmiesz cortexa to masz kartkę, długopis i często kalkulator

  • #28 17 Mar 2017 11:00
    malcompl
    Poziom 12  

    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 17 Mar 2017 11:19
    Piotrus_999
    Poziom 39  

    malcompl napisał:
    Normalnie dla 32bit byłby prawdopodobny call do udivmodsi4, niezaleznie jaka wartość znajdowałaby się w zmiennej.
    Nie wiem skąd bierzesz takie rewelacje, ale się mylisz

    Kod: armasm
    Zaloguj się, aby zobaczyć kod


    a,b,c - int
    d,e,f - uint16

    Tak samo porównania do x86 nie mają tu najmniejszego sensu.

  • #30 17 Mar 2017 11:34
    malcompl
    Poziom 12  

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

Szybka odpowiedź lub zadaj pytanie
Dziękuję Ci. Ta wiadomość oczekuje na moderatora.
 Szukaj w ofercie
Wyszukaj w ofercie 200 tys. produktów TME