Elektroda.pl
Elektroda.pl
X

Wyszukiwarki naszych partnerów

Wyszukaj w ofercie 200 tys. produktów TME
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 17 Mar 2017 11:39 3066 53
  • #32 17 Mar 2017 12:03
    krzysztofh
    Poziom 29  

    Koledzy, procesor to Atmega 16 taktowana zegarem 16MHz i nie mogę jej zamienić na coś innego.
    Nie włączam się do dyskusji, bo to nie mój poziom, ale czytam wszystkie posty.

  • #33 17 Mar 2017 12:48
    Piotrus_999
    Poziom 39  

    krzysztofh napisał:
    Koledzy, procesor to Atmega 16 taktowana zegarem 16MHz i nie mogę jej zamienić na coś innego.
    Nie włączam się do dyskusji, bo to nie mój poziom, ale czytam wszystkie posty.


    Musisz w takim razie się pogodzić. Wszystko co ma wiecej niz 8 bitów zajmuje więcej czasu i przestrzeni bo to taki procesor po prostu. Dzielenie jest dość wolne bo niestety programowe i na danych więcej niż 8 bitów sporo operacji musi być wykonane,

  • #34 17 Mar 2017 22:30
    Sparrowhawk
    Poziom 21  

    Sprawdziłem jak umiałem (z pomocą timera), czas wykonania konwersji liczby INT32_MAX na Atmega168PB [16MHz]. Moja własna naiwna implementacja:

    Kod: c
    Zaloguj się, aby zobaczyć kod
    wykonuje się w najlepszym razie na -03: 343µs. W najgorszym na -Os: 781µs.
    Natomiast AVR Libc dostarcza nam gotową funkcję, która nie zależnie od wybranej optymalizacji wykonywała się w czasie: 223µs.

    W aktualnym numerze EP(03/17) pojawił się artykuł pt. "Osobliwości kompilatora AVR-GCC i mikrokontrolerów AVR (1)", w którym również przedstawiona jest funkcja na wzór ltoa(). Artykuł dostępny jest na stronie Elektroniki praktycznej.

    Przetestowałem i tę funkcję i otrzymałem od -03: 328µs do -Os: 347.

  • #35 18 Mar 2017 01:31
    malcompl
    Poziom 12  

    Szybciej niż z libc-a raczej nie da się osiągnąć, w jakimś sensowny czasie. Patrzyłem na ten kod, jest sprawnie napisany w asm-ie i niezależnie od ustawień kompilatora, czas wykonania będzie stały, który dałoby się oszacować. Funkcje te wykonują te same instrukcje różniące się jedynie obsługa większych rozmiarów, iteracyjnie w powtórzeniach równych co do rozmiaru typu. Niezależnie czy będzie 0x00000001, czy 0xFFFFFFFF, czas wykonania będzie taki sam. Ale można przyjąć, że 32- jest 2+ razy wolniejsze niż 16-, a te również 2+ razy niż 8-bit int.

    Jedyny zysk na cyklach można osiągnąć właśnie wykorzystując ten fakt, z kodem jaki już wyżej wspominaliśmy, aby zależnie od wartości wołać dedykowaną funkcję 32-, 16- czy 8- bitową. To oczywiście może być znacznie zauważalne, jeśli przetwarzane dane będą najczęściej trafiać w zakres 16- lub 8-, niż w 32-bitowy.

    Sam przez chwilę myślałem, że może dotknąć mnie ten problem w planowanym radiowym liczniku częstotliwości, który może przejdzie z pomysłu i planu do realizacji w jakimś sensownym czasie ;) Ale patrząc realnie, nawet przy czasie bramkowania 10ms, 6-ciu cyfrach, przeoranie 32-bitowych danych nawet z jakaś obróbką, czy uśrednianiem, będzie niezauważalne z punktu działania całości układu.

    Autor musiałby nieźle walić danymi do obróbki, aby mieć problem. A jakby chciał na żywo przetwarzać jakieś dane/sygnały z większą częstotliwością niż ewentualna ich prezentacją to chyba nie ta platforma ;)

    BTW Funkcje dzielnia z libc-a zwracają wynik z dzielenia i resztę, więc jeśli w pobliżu będzie operacja / i % na tych samych danych (co jest raczej pewne, przy rozbijaniu liczby na cyfry), to optymalizator kompilatora ładnie z tego faktu skorzysta, generując tylko jeden call.

  • #36 18 Mar 2017 08:17
    Wertyuud
    Poziom 20  

    Widzę, że autor chce zrobić konwersję liczby binarnej na BCD. Jest do tego specjalny algorytm, który nie używa mnożenie i dzielenia, tylko przesuwanie bitów i dodawanie warunkowe. Można poszukać w google pod nazwą "bin to bcd conversion algoriht", "Double-Dabble", "Shift-and-add-3 algorithm". Tutaj przykład. Zapewne jest gdzieś w sieci implementacja na AVR.

    Co do dzielenia modulo, to nie zawsze korzystanie z bibliotek standardowych jest optymalnie, bo wykonują one działania dla wszystkich możliwych przypadków (dzielenie przez dowolną liczbę !=0). Można napisać algorytm, który będzie dzielił tylko przez jedną możliwą liczę np. przez dziesięć, przez co będzie działał szybciej. Optymalizacja dzielenia jest dobrze opisana np. tu. Skleiłem dwa algorytmy z powyższej strony, żeby uzyskać wynik z dzielenia przez 10 i dzielenia modulo 10, ale nie wiem jaka będzie jego szybkość:

    Kod: c
    Zaloguj się, aby zobaczyć kod

  • #37 18 Mar 2017 11:42
    tmf
    Moderator Mikrokontrolery Projektowanie

    Tak czytam i oczom niedowierzam. Mamy proste zadanie jakim jest konwersja z bin na bcd w celu wyświetlenia liczby na wyświetlaczu najpewniej 7-segmentowym (w pierwszym poście autor omyłkowo zapewne pisze o 6-segmentowym). Konwersja wykonywana sporadycznie, bo przecież człowiek i tak nie zauważy zmieniającej się np. 1000-razy na wyświetlaczu liczby. Ile razy więc taką konwersję dokonujemy? 10-, 20-razy na sekundę? To i tak aż nadto. I teraz hit - mamy 36 postów o tym jak przyśpieszyć konwersję, która nie ma najmniejszego znaczenia dla szybkości działania i obciążenia mikrokontrolera. Idę o zakład, że autor rozważający marginalne oszczędności, w innej części programu ma miejsca, których optymalizacja da pewnie setki razy większe oszczędności, ale tego nie dostrzega.
    Panowie, zacznijcie pisać programy zamiast skupiać się na bzdurach. O optymalizacji warto myśleć jeśli widzimy, że zbliżamy się do kresu możliwości użytego MCU. Wcześniej - wystarczy tylko poprawnie pisać kod.

  • #38 18 Mar 2017 12:30
    malcompl
    Poziom 12  

    @Wertyuud: O czymś podobnym myślałem, ale się wstrzymywałem po ostatniej wpadce ;)
    Ten Twój kod u mnie zajął około 160-170 cykli (O3, Os), a typowy udivmodsi4 około 600 cykli.

    @tmf: Z praktycznego punktu widzenia to już ustalono, że raczej nie będzie miało to sensu w projekcie autora. Ale jest to dobra zabawa głównie w celach edukacyjnych, bo nudzić może ciągłe tworzenie kodu.

    Może się nieraz to przydać przy analizowaniu binarek, zabezpieczeń, czy innych shittów przy reverse engineeringu, choć raczej nie na tej małej platformie :)

  • #39 19 Mar 2017 14:10
    grko
    Poziom 32  

    @tmf Jakbyś przeczytał cały temat to wiedziałbyś, że wiele osób powtarzało to, że optymalizacje tego typu są bez sensu (w 99% przypadków). Sugerowałem to min ja oraz FCh więc wypadałoby być sprawiedliwym w ocenach postów z tego tematu. Poza tym jeżeli autor nadal chce sobie to optymalizować to nie widzę żadnych przeszkód aby w tym temacie było o tym nawet 1000 postów (w końcu o tym jest ten temat).

  • #40 19 Mar 2017 16:46
    linuxtorpeda
    Poziom 17  

    Wszyscy powtarzają, że optymalizacja jest bez sensu, ale poza paroma osobami nikt nic sensownego nie zaproponował (LUT i double dabble).

    Ja bym przemyślał też, czy nie byłoby sensowne w tym konkretnym przypadku reprezentowanie liczby w formacie BCD, wtedy operacja modulo sprowadzałaby się do założenia odpowiedniej maski na liczbę. Oczywiście, wtedy niektóre pozostałe operacje będą wykonywane dłużej.

  • #41 30 Mar 2017 13:50
    krzysztofh
    Poziom 29  

    Witam ponownie.
    Ciągnę wątek zamiany bin na BCD, głównie po to aby się czegoś nauczyć, bo program w zasadzie jest skończony i działa zgodnie z oczekiwaniami (obsługa generatora).
    Jak skończę całość to temat pewnie pojawi się na Elektrodzie w DIY.
    Sprawdziłem pracę kodu wyświetlającego dane na sześciu wyświetlaczach siedmio-segmentowych i w każdym przypadku działanie jest poprawne.
    W pierwszym przypadku zastosowałem kod:

    Kod: csharp
    Zaloguj się, aby zobaczyć kod


    Dla potrzeb sprawdzenia ile cykli procesor potrzebuje na obsługę tego kodu zainstalowałem Atmel Studio, bo na co dzień (cokolwiek by to miało znaczyć) piszę w C korzystając z Eclipse.
    Obsługa powyższego kodu zajmuje 5998 cykli zegara.

    Teraz drugi kod:

    Kod: csharp
    Zaloguj się, aby zobaczyć kod


    Dla obsługi tego kodu procesor potrzebuje 1325 cykli i to dla liczby value_wysw = 99999999, z czego 623 cykle są poświęcone na pierwsze dzielenie value_wysw /= 10;
    Przy odejmowaniu wiadomo, im mniejsze cyfry obsługa kodu będzie szybsza.

    Winien jestem też dodatkowe informacje. Wyświetlana liczba jest dostarczona o rząd wielkości większa, dlatego na początku jest od razu dzielona przez 10. Wynika to z potrzeby wyświetlenia na sześciu cyfrach liczb w zakresie setek z jednym miejscem po przecinku, ale i dziesiątek mln wtedy najmniej reprezentatywna cyfra wyświetla setki Hz. Ponadto na potrzeby obliczeń aby zachować należytą dokładność obliczana wielkość jest jeszcze zawyżona o jeden rząd dla uniknięcia liczb zmiennoprzecinkowych.

    Przedstawiony kod prezentuje oczywiście tylko jednego ifa dla określonego zakresu liczby, co nie zmienia postaci rzeczy że widać różnicę w ilości cykli procesora.
    Kod oparty na odejmowaniu zajmuje więcej pamięci procesora, więc trzeba wybierać.
    W moim przypadku jak pisałem wyżej oba kody się sprawdzają a program nie zajmuje więcej niż 40% pamięci.

    Chciałbym przetestować podaną metodę z przesuwaniem bitów, której ideę rozumiem, bo przetestowałem na piechotę na kartce, ale nie potrafię tego zapisać w C. Dlatego prośba o pomoc w tej kwestii. Byłaby to dla mnie kolejna cegiełka wiedzy w programowaniu.
    Dzięki.

  • #42 30 Mar 2017 14:56
    malcompl
    Poziom 12  

    Też się tym tematem jeszcze interesuje. Robiłem jakieś testy i zabawy, miedzy innymi z czymś podobnym do idei przedstawionej wyżej przez kol. Wertyuud-a. Może uda mi się zebrać dane i dokończyć kod, który raczej będzie generyczny w modern C++. Ale idea jest bardzo prosta, od biedy w C można ręcznie napisać tych kilka linijek.

    Z nawału różnych innych rzeczy, raczej na pewno nie wcześniej niż przed weekendem tego nie ogarnę ;)

  • #44 30 Mar 2017 16:11
    Freddie Chopin
    Specjalista - Mikrokontrolery

    Piotrus_999 napisał:
    A co to jest? Czy jest ancient C++?

    Jest. Wszystko co było przed C++11.

  • #45 30 Mar 2017 17:56
    krzysztofh
    Poziom 29  

    malcompl napisał:
    Też się tym tematem jeszcze interesuje. Robiłem jakieś testy i zabawy, miedzy innymi z czymś podobnym do idei przedstawionej wyżej przez kol. Wertyuud-a. Może uda mi się zebrać dane i dokończyć kod, który raczej będzie generyczny w modern C++. Ale idea jest bardzo prosta, od biedy w C można ręcznie napisać tych kilka linijek.

    Z nawału różnych innych rzeczy, raczej na pewno nie wcześniej niż przed weekendem tego nie ogarnę ;)

    Próbowałem ogarnąć ten kod ale bez rezultatu. Nie bardzo mogę go rozkminić.

  • Pomocny post
    #46 30 Mar 2017 20:13
    Piotrus_999
    Poziom 39  

    No to jak rozkminiacie różne programy to ja Wam dam procedurkę dzielenia przez 10 liczby 32 bitowej ponad 2 razy szybszą niż dzielenie

    Kod: c
    Zaloguj się, aby zobaczyć kod


    Możesz sobie łatwo przerobić na dzielenie przez 100 1000 czy cokolwiek innego, lub inną długość danych.

  • #47 31 Mar 2017 00:09
    trol.six
    Poziom 30  

    Piotrus_999 napisał:
    malcompl napisał:
    modern C++
    A co to jest? Czy jest ancient C++?

    Ja pisze w archaicznym C, aż dziw że nie mówię po sumeryjsku ;)

    Wertyuud napisał:
    "Shift-and-add-3 algorithm"

    krzysztofh napisał:
    Chciałbym przetestować podaną metodę z przesuwaniem bitów, której ideę rozumiem, bo przetestowałem na piechotę na kartce, ale nie potrafię tego zapisać w C


    Taki sobie kod roboczy, czyli powinien działać, choć może nie super optymalnie.
    To jest dla 32 bitów. Dla liczb mniej bitowych trzeba (można) zmienić kod.
    Bo przesunięć jest tyle ile bitowa jest liczba. Tu jest na sztywno.
    Kod uwzględnia 9 cyfr, liczba 32-bit ma 10. Więc w pełnym zakresie będzie kilka instrukcji więcej.

    Kod: c
    Zaloguj się, aby zobaczyć kod

  • #48 31 Mar 2017 21:24
    krzysztofh
    Poziom 29  

    Piotrus_999 napisał:
    No to jak rozkminiacie różne programy to ja Wam dam procedurkę dzielenia przez 10 liczby 32 bitowej ponad 2 razy szybszą niż dzielenie

    Kod: c
    Zaloguj się, aby zobaczyć kod


    Możesz sobie łatwo przerobić na dzielenie przez 100 1000 czy cokolwiek innego, lub inną długość danych.


    Dzięki za procedurkę, sprawdziłem w Cmaniaku i działa poprawnie. Nie wiem dlaczego nie chce mi jej obsłużyć Atmel Studio, abym się zorientował ile to zajmuje mikroprocesorowi.
    Sprawdziłem ją też na piechotę w Excelu przy działaniach na bitach i też się zgadza, ale nie bardzo rozumiem jaka idea przyświecała autorowi aby podstawić akurat taką liczbę. Dlatego że nie rozumiem idei nie potrafię jej zastosować dla dzielenia przez sto czy tysiąc.

  • Pomocny post
    #49 31 Mar 2017 21:53
    Freddie Chopin
    Specjalista - Mikrokontrolery

    krzysztofh napisał:
    nie bardzo rozumiem jaka idea przyświecała autorowi aby podstawić akurat taką liczbę

    Ideą która temu przyświeca jest to, że jest to 1/10 wartości (1 << 32) czyli 0x100000000. Wykorzystywana jest następująca zależność:

    a / x = b => (a / x) * p = b * p

    przy czym "a" to liczba którą chcesz podzielić, "x" to dzielnik (10), "b" to wynik dzielenia, a "p" to dowolny współczynnik. Tutaj ten współczynnik został dobrany akurat tak, że można dzielnie przez niego zastąpić przesunięciem bitowym.

  • Pomocny post
    #50 31 Mar 2017 21:55
    Piotrus_999
    Poziom 39  

    Idea jest bardzo prosta - to zwykłe skalowanie liczby:

    maxuint32 + 1 to 0x100000000 dzielone przez 10 to 0x1999999A albo 0x19999999 zalezy jak zaokrąglić

    Następnie dzielę przez 0x100000000 ( a to akurat >> 32)

    Czyli (X * (Y/10)) / Y = X / 10

    Y = 0x100000000


    Algorytm ma sens oczywiście dla platform, które mają mnozenie sprzętowe (nawet małych liczb), a nie maja dzielenia.

    Dla platform ze sprzętowym dzieleniem lepiej robić "normalnie" - czyli dzielić

  • #51 01 Maj 2017 00:15
    malcompl
    Poziom 12  

    Finalnie po babraniu się w wolnych chwilach, udało mi się wreszcie porównać (przetestować) kilka algorytmów do konwersji zapisu binarnego do reprezentacji w kodzie BCD. Zrezygnowałem z jakiś własnych hacków i implementacji, ale skupiłem się na kilku popularnych metodach.

    Szczegóły można znaleźć w moich notatkach. A później zestawienie zbiorcze z otrzymanych wyników na atmedze 16:

    Działania na dużych liczbach

    Uwaga: skala logarytmiczna i na pierwszy rzut może wydawać się ze większość ma podobną złożoność czasową wykonania.

    Do testów użyłem najnowszego toolchaina wyekstrahowanego z Atmel Studio - avr-gcc 5.4.0, kody kompilowane z optymalizacja O2. Testowe dane jakie użyłem w benchmarku to dla każdego typu unsigned to ciąg wartości:

    Code:
    [ 0, Max<T>/16, Max<T>/8, Max<T>/4, Max<T>/2, Max<T> ]


    Spodziewałem się, że metoda zastępowania dzielenia za pomocą aproksymacji i mnożenia wzajemnego (ApproxMul), także ukazana w ostatnich postać przez kolegów @Wertyuud, @Piotrus_999 i @Freddie Chopin będzie będzie najlepsza. Ale testy zweryfikowały poglądy i ku zaskoczeniu typowa konstrukcja brute-force (sukcesywnie odejmowanie poszczególnych pozycji dziesiętnych) okazała się najszybsza.

    A jej implementacja w miarę bardzo prosta:
    Kod: c
    Zaloguj się, aby zobaczyć kod


    Tutaj jej porównanie do czasu, jaki wymagałby hipotetycznego algorytm z zastosowaniem dzielenia, gdyby sprzętowe ALU wspierało taką operację.

    Działania na dużych liczbach

    Kod źródłowy właśnie wrzuciłem na githubowego gista. W pliku bcd.h znajdują się generyczne implementacje algorytmów w C++, jeśli ktoś za bardzo nie na tego języka, kod może wydawać się dziwny i straszny ;) Plik avr.cpp zawiera kod dla AVR-ków z benchmarkiem. Testy jednostkowe utwierdzające w poprawnym działaniu algorytmów wrzuciłem do piku test.cpp, bazuje on na booost-owych testach, można go skompilować i uruchomić na dowolnym komputerze.

    Można pokusić się o jakieś dodatkowe optymalizacje, niektóre algorytmy na pewno da się jeszcze trochę bardziej wycisnąć. Można tez przetestować inne konstrukcje, ja z braku czasu póki co zatrzymałem się na tym.

    Funkcje maja fajny interfejs , więc idealnie nadają się do jakieś biblioteki, ich użycie dzięki dostępnym traitsom, jest bajeczne i proste.
    Kod: c
    Zaloguj się, aby zobaczyć kod


    Może komuś także się przydadzą te implementacje do bezpośredniego użycia lub chociażby jako inspiracja:)

    Otrzymane zaskakujące wyniki i rezultat uświadomił mnie, że warto robić różne testy i eksperymenty, bo nie zawsze to co się wydaje będzie odzwierciedleniem rzeczywistości. Rzeczywistość lubi często zaskakiwać.

  • #52 01 Maj 2017 09:08
    Freddie Chopin
    Specjalista - Mikrokontrolery

    Zaraz się dowiesz, że wyszły Ci takie wyniki przez C++, bo jakbyś to zrobił w C to metoda X byłaby 1315x szybsza niż w C++ (;

    W każdym razie mam pewne wątpliwości co do "próby" danych testowych. Nie da się ukryć, że jest ona dosyć specyficzna i użycie jakiegoś losowego zestawu dałoby lepsze efekty. Metoda "brutalna" którą przedstawiłeś jest szybka jeśli operuje na "niskich" cyfrach - np. 10000 będzie super szybkie, ale 99999 już niekoniecznie. Tymczasem dla trzech użytych typów masz:
    - uin8_t - 0, 15, 31, 63, 127, 255
    - uin16_t - 0, 4095, 8191, 16383, 32767, 65535
    - uint32_t - 0, 268435455 536870911, 1073741823, 2147483647, 4294967295

    Cyfra 9 pojawia się ledwo 6x (z czego 3x w jednej liczbie), cyfra 8 tak samo tylko 6x. Spróbuj te testy przeprowadzić na danych losowych, np. wygeneruj sobie je na stronce random.org, np. z tego generatora - https://www.random.org/bytes/ - musisz tylko hexy odpowiednio "poskładać" w liczby. Inne generatory się średnio nadadzą, bo większość ma limit wartości wynoszący 1000000000, czyli mniej niż 1/4 uint32_t.

  • #53 01 Maj 2017 10:13
    malcompl
    Poziom 12  

    Freddie Chopin napisał:
    Zaraz się dowiesz, że wyszły Ci takie wyniki przez C++, bo jakbyś to zrobił w C to metoda X byłaby 1315x szybsza niż w C++ (;

    Wiadomo, C jest poza prawami fizyki ;)

    Freddie Chopin napisał:
    W każdym razie mam pewne wątpliwości co do "próby" danych testowych. Nie da się ukryć, że jest ona dosyć specyficzna i użycie jakiegoś losowego zestawu dałoby lepsze efekty.


    Tak, random byłby zdecydowanie lepszy, z braku czasu ograniczyłem sie tylko do tych kilku prostych przypadków. Popróbuje w wolnym czasie wygenerować nieco więcej losowych danych, bardziej miarodajnych. Pewnie będzie tak, że dla wielu '9' brute-force może wypaść gorzej niż ApproxMul, a dla tych wartości z mniejszą ich ilością lepiej. Ciekawe jak wtedy jakaś średnia wyjdzie ;)

    Dzieki za sugestie z online-generatorem.

  • #54 01 Maj 2017 16:19
    trol.six
    Poziom 30  

    malcompl napisał:
    Popróbuje w wolnym czasie wygenerować nieco więcej losowych danych, bardziej miarodajnych.

    Czas wykonania metodą z odejmowaniem jest zależna od danych wejściowych a głównie od sumy cyfr BCD.
    więc może, oprócz zestawu losowego, np tak:
    Kod: c
    Zaloguj się, aby zobaczyć kod


    A zgrubne szacunki dla BIN -> BCD, dla liczby 16 bit, 59999

    metoda odejmowania
    odjęcie ze sprawdzeniem i skokiem 5 cykli
    ilość operacji 32 = 5 + 9 + 9 + 9 (reszta jednostki)
    pobranie liczby 6 cykli
    cykli 204 = 32 * 6 + 4 * 6

    dla metody z przesunięciem i dodawaniem
    5 sprawdzeń z dodaniem 3 cykli
    5 przesunięć z dodaniem 3 cykli
    5 and 1 cykl
    sprawdzenie liczby i przesuniecie 4
    39 = 15 + 15 + 5 + 4
    razy 16 bitów
    cykli 624 = 16 * 39

 Szukaj w ofercie
Zamknij 
Wyszukaj w ofercie 200 tys. produktów TME