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

Integer o zmiennym rozmiarze? Wydajny zapis typu unsigned w C, oszczędzanie pamięci

p.kaczmarek2 14 Kwi 2024 09:08 1728 9
  • Integer o zmiennym rozmiarze? Wydajny zapis typu unsigned w C, oszczędzanie pamięci
    Witajcie, dziś dla odmiany mała zabawa programistyczna. Przedstawię tu jeden prosty trik na oszczędzanie pamięci przy zapisie typu integer w języku C i nie będzie to po prostu rada w stylu "użyj typu 8-bitowego zamiast 32-bitowego". Pokazany tu typ sam dobierze sobie potrzebną ilość bajtów i sprytnie ją zapisze w samej tworzonej liczbie.
    Oczywiście, jak powszechnie wiadomo, nic nie jest za darmo a idealna kompresja nie istnieje, więc całość będzie działać przy pewnym założeniu. A mianowicie zakładam tutaj, że mniejsze wartości liczb występują statystycznie częściej niż większe. Potem wyjaśnię, dlaczego to ważne.

    Prezentacja zostanie dokonana w języku C, nie będę tu raczej korzystać z żadnych mechanizmów powiązanych z daną platformą. Całość przedstawionego systemu strumienia powinno dać się uruchomić na wielu platformach, też na mikrokontrolerach.

    Fundamenty - zapis i odczyt ze strumienia
    Na początku przygotujmy sobie strukturę strumienia w języku C. Całość stanowić będzie absolutne minimum, bez sprawdzania zakresów tablicy, itd. Czytelnik może to sobie dodać, jak również przerzucić całość do C++:
    Kod: C / C++
    Zaloguj się, aby zobaczyć kod

    Strumień definiujemy jako wskaźnik na tablicę bajtów (dane, do interpretacji) oraz pozycję w tej tablicy.

    Teraz zaimplementujmy odczyt i zapis z tego strumienia. W przypadku odczytu kopiujemy N bajtów z danej pozycji na bufor wyjściowy oraz zwiększamy naszą pozycję, w przypadku zapisu kopiujemy w drugą stronę:
    Kod: C / C++
    Zaloguj się, aby zobaczyć kod

    Funkcja memcpy kopiuje N bajtów ze źródła na cel, w przypadku celu korzystam z arytmetyki wskaźników, mogę dodać pozycję do danych gdyż zmienna "data" jest typu bajt (unsigned char), więc jej rozmiar to 1.

    Na bazie tego możemy dodać gotowe funkcje czytające/zapisujące dany typ:
    Kod: C / C++
    Zaloguj się, aby zobaczyć kod



    Testowanie i jego automatyzacja
    Troszkę kodu już napisaliśmy, teraz warto sprawdzić jego działanie w kontrolowanym środowisku.
    Proponuję wykonać prymitywny, lecz automatyczny test naszego strumienia - zapiszmy do niego jakieś wartości a potem je odczytajmy, na koniec porównując automatycznie odczytane wartości z tymi zapisanymi.
    Takie podejście pozwala nam szybko przetestować działanie całości nawet po wykonaniu zmian w implementacji strumienia, bo kod w zasadzie testuje wszystko za nas.
    Czyli kolejno, zmienne:
    Kod: C / C++
    Zaloguj się, aby zobaczyć kod

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

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

    No i automatyczne porównanie - sprawdzenie, czy wszystko jest ok:
    Kod: C / C++
    Zaloguj się, aby zobaczyć kod

    Powyższy kod został odpalony i wszystko u mnie działa.

    Tytułowy sprytny integer
    Zrobiliśmy już fundamenty pod to, co chciałem tutaj pokazać. Przedstawiony pomysł nie jest nowy i często występuje pod nazwą varint bądź compact integer.
    Idea jest taka, że jak już możemy czytać strumień bajt po bajcie, to czemu by nie zapisywać liczb całkowitych z różnym rozmiarem?
    Normalnie możemy operować na:
    - byte (1 bajt), 2^8 wartości, 256
    - uint16 (2 bajty), 2^16 wartości, 65536
    - uint32 (4 bajty), 2^32 wartości, 4294967296
    - uint64 (8 bajtów), 2^64 wartości, 18446744073709551616
    Ale czy aby na pewno chcemy dokonywać wyboru jakiego typu użyjemy? Co jeśli założymy, że dana wartość będzie jednym bajtem a po trzech miesiącach projektu okaże się, że raz licznik przekroczył 255? Możliwe, że nawet licznik się "przekręci" i będzie liczyć od 0...
    Tutaj pojawia się varint.
    Załóżmy, że:
    - kolejno rozbijamy naszą liczbę całkowitą bez znaku na porcje po 7 bitów
    - odkładamy najmłodsze 7 bitów, sprawdzamy czy została wartość niezerowa
    - jeśli została wartość niezerowa, to ósmy, specjalny bit ustawiamy na 1, jeśli nie, to na 0
    - zapisujemy tak opracowany bajt (7 bitów danych i 1 bit "czy coś zostało")
    - jeśli została wartość niezerowa, to kontynuujemy operacje na kolejnych 7 bitach
    Skutkiem takiego podejścia będzie integer o zmiennym rozmiarze, gdzie w każdym jego bajcie jest 7 bitów danych oraz 1 bit mówiący nam czy czytać dalej

    Mała uwaga - operacje tutaj wykonuję na typie unsigned (bez znaku), dla typu signed potrzebna jest jeszcze mała modyfikacja by to działało, ale o tym w drugiej części.

    Teraz to zaimplementujmy.
    Pamiętacie funkcję Stream_WriteByte?
    Tu się ona nam przyda.
    Dopóki nasza zmienna nie jest zerem (ale jeden przebieg zawsze musi być, bo inaczej byśmy nie zapisali nic):
    Kod: C / C++
    Zaloguj się, aby zobaczyć kod

    Wybieramy z niej najmłodsze 7 bitów:
    Kod: C / C++
    Zaloguj się, aby zobaczyć kod

    Potem przesuwamy pozostałe bity na ich miejsce (przesunięcie bitowe o 7 bitów):
    Kod: C / C++
    Zaloguj się, aby zobaczyć kod

    Potem sprawdzamy, czy to co nam zostało to wartość zerowa. Jeśli nie, to ustawiamy bit czy czytać dalej:
    Kod: C / C++
    Zaloguj się, aby zobaczyć kod

    No i zapisujemy nasz bajt zawierający 7 bitów danych oraz bit czy czytać dalej:
    Kod: C / C++
    Zaloguj się, aby zobaczyć kod

    Analogicznie możemy wykonać odczyt:
    Kod: C / C++
    Zaloguj się, aby zobaczyć kod

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

    Wszystko działa.
    Integer o zmiennym rozmiarze? Wydajny zapis typu unsigned w C, oszczędzanie pamięci


    Podglądamy sprytny integer
    Teraz tylko w ramach lepszego zwizualizowania co się dzieje możemy wyświetlić w konsoli ilość użytych bajtów do zapisu danej wartości:
    Kod: C / C++
    Zaloguj się, aby zobaczyć kod

    W pętli for zapisujemy kolejne liczby:
    Kod: C / C++
    Zaloguj się, aby zobaczyć kod

    Bardzo ładnie widać, że w momencie przekroczenia 128 rozmiar varint rośnie z 1 do 2:
    
    120 used 1 bytes
    121 used 1 bytes
    122 used 1 bytes
    123 used 1 bytes
    124 used 1 bytes
    125 used 1 bytes
    126 used 1 bytes
    127 used 1 bytes
    128 used 2 bytes
    129 used 2 bytes
    130 used 2 bytes
    131 used 2 bytes
    132 used 2 bytes
    133 used 2 bytes
    134 used 2 bytes
    135 used 2 bytes
    136 used 2 bytes
    137 used 2 bytes
    138 used 2 bytes
    139 used 2 bytes
    

    Potem przekroczenie następuje przy 16384 :
    
    16380 used 2 bytes
    16381 used 2 bytes
    16382 used 2 bytes
    16383 used 2 bytes
    16384 used 3 bytes
    16385 used 3 bytes
    16386 used 3 bytes
    16387 used 3 bytes
    



    Ile pamięci oszczędzi sprytny integer
    Jeszcze może zróbmy bardziej praktyczny test. Wylosujmy sobie N liczb całkowitych bez znaku, oczywiście 28-bitowych, bo 4 bity tracimy na znak "czy czytać dalej" (chociaż ostatni można by inaczej traktować...):
    Kod: C / C++
    Zaloguj się, aby zobaczyć kod

    Zapiszmy je sobie w pętli do jednego bufora bez naszej "kompresji", a do drugiego z:
    Kod: C / C++
    Zaloguj się, aby zobaczyć kod

    Odpalamy, ile oszczędzi varint?
    Integer o zmiennym rozmiarze? Wydajny zapis typu unsigned w C, oszczędzanie pamięci
    0.12% oszczędności - co jest, czyżby porażka?
    Na szczęście nie - po prostu tutaj specjalnie pominąłem coś, co podkreślałem na początku tematu:
    p.kaczmarek2 napisał:

    A mianowicie zakładam tutaj, że mniejsze wartości liczb występują statystycznie częściej niż większe.

    Powyższe losowanie z rand() nie spełnia mojego założenia.

    Możemy w takim razie inaczej losować liczby, tutaj dwukrotnie zmniejszam szansę na każdy kolejny bajt:
    Integer o zmiennym rozmiarze? Wydajny zapis typu unsigned w C, oszczędzanie pamięci
    I już oszczędzamy 40% pamięci...

    Podsumowanie
    Ta metoda naprawdę działa i jest używana przykładowo przez Google w Protocol Buffers. Oczywiście, aby był w ogóle sens jej stosować muszą być spełnione pewne założenia, a mianowicie mniejsze liczby muszą występować częściej niż większe, bo inaczej wręcz na tej metodzie stracimy, bo zasadniczo kodując liczby w ten sposób tracimy 1 bit na każde 7 bitów danych. Swoją drogą, nie jest powiedziane że varint może mieć maksymalnie 32-bity, można tworzyć dłuższe, chociażby użyć typu long.
    Dodatkowo warto pamiętać że w przypadku tworzenia struktury danych opartej o integery o zmiennym rozmiarze ciężko będzie ją iterować poprzez arytmetykę wskaźników. Jeśli mamy tablicę struktur gdzie rozmiar struktury jest stały, to łatwo jest przeskoczyć do N-tego elementu takiej tablicy, a tutaj ta operacja nie będzie możliwa.
    Mimo wszystko myślę, że tego typu zapis danych może być przydatny i też przede wszystkim jest tani pod kątem cyklów procesora - na pewno tańszy niż zwykła kompresja...
    Co sądzicie o tego typu oszczędności miejsca? Korzystaliście może z tego w swoich projektach?
    PS: Oczywiście przedstawiony kod należałoby mocno usprawnić przed użyciem go w projekcie. Podstawą będzie dodanie tu sprawdzania zakresów tablicy, czyli dopisanie rozmiaru bufora do struktury strumienia. Pewnie przydałoby się go też przepisać do C++, by było obiektowo, ale to zależy w czym piszemy. Również należałoby zadbać czy np. rozmiar typu int na naszej platformie jest taki jakiego oczekujemy, itd...
    PS2: Właściwie to przydałoby się jeszcze pokazać jak zapisać w ten sposób integer ze znakiem, ale o tym może już w kolejnej części...

    Fajne? Ranking DIY
    Pomogłem? Kup mi kawę.
    O autorze
    p.kaczmarek2
    Moderator Smart Home
    Offline 
  • #2 21044825
    tmf
    VIP Zasłużony dla elektroda
    Ja przy takich "optymalizacjach" zacząłbym od dokładnego zdefiniowania gdzie i kiedy warto je robić. Przesyłając duże ilości danych przez jakieś wolne medium - zdecydowanie tak. W innych przypadkach?
    Ceną jaką płacimy jest od razu szybkość działania programu - jakakolwiek arytmetyka na takim typie to będzie tragedia czasowa. Tragedią będzie też dostęp do niewyrównanych danych na architekturach 16/32/64 bitowych - koszt czasowy dostępu będzie znaczny.
    Natomiast rozwiązanie problemu typu co jeśli w trakcie pisania programu typ 8-bitowy staje się niewystarczający jest bardzo proste - robimy #define mójtyp uint8_t, jak nam zabraknie bitów to zmieniamy na uint16_t i po kłopocie.
  • #3 21044874
    khoam
    Poziom 42  
    p.kaczmarek2 napisał:
    Pewnie przydałoby się go też przepisać do C++, by było obiektowo

    Nie ma takiej potrzeby. W C++ jest już standardowa klasa std::variant z kontrolą typów przechowywanych danych. Nie korzysta z pamięci alokowanej dynamicznie, więc dobrze nadaje się do embedded.

    Dodano po 16 [minuty]:

    tmf napisał:
    Natomiast rozwiązanie problemu typu co jeśli w trakcie pisania programu typ 8-bitowy staje się niewystarczający jest bardzo proste - robimy #define mójtyp uint8_t, jak nam zabraknie bitów to zmieniamy na uint16_t i po kłopocie.

    Sądzę, że lepiej użyć w takiej sytuacji typedef zamiast #define. Wtedy można np. ograniczyć zakres definicji takiego aliasu typu do bloku (#define będzie miało zasięg globalny).
  • #4 21044924
    p.kaczmarek2
    Moderator Smart Home
    Ciekawe komentarze, jednakże zwrócę tu uwagę na kilka rzeczy:
    tmf napisał:

    Przesyłając duże ilości danych przez jakieś wolne medium - zdecydowanie tak.

    Dokładnie o to mi chodziło, w sumie mogłem to dodać na początku, oczywiście samo określenie stream/strumień/serializacja sugeruje, że pewnie jakiś plik lub socket sieciowy to odbiera lub wysyła. Oczywiście nie korzystałbym z tego typu sposobu do trzymania w RAM danych.
    tmf napisał:

    Natomiast rozwiązanie problemu typu co jeśli w trakcie pisania programu typ 8-bitowy staje się niewystarczający jest bardzo proste - robimy #define mójtyp uint8_t, jak nam zabraknie bitów to zmieniamy na uint16_t i po kłopocie.

    Nie upraszczałbym aż tak bardzo tej sytuacji. Mi tu bardziej chodziło o sytuację, gdzie optymalizujemy rozmiar strumienia do przechowania bądź przesłania przez wolne medium. Pokazane w pierwszym poście rozwiązanie ma ten plus, że jest przyszłościowe, a jednocześnie nie zajmuje miejsca. Dodatkowo czemu zakładasz, że możemy łatwo zrekompilować program?

    Miałeś może kiedyś sytuację, gdzie założyłeś że w jakimś strumieniu typ będzie 8-bitowy (np. w C# są takie ładne klasy BinaryWriter/BinaryReader) a potem się okazało, że trzeba czasem przechować większą wartość, a system jest już na produkcji? Wtedy jest wielki problem, trzeba do formatu pliku lub pakietu mieć dodany numer wersji a potem przy parsingu strumienia dodać if i sprawdzać wersję...
    No i raz jeszcze powtórzę - sytuacja o której mówię jest gdy optymalizujemy "wolne medium" a w RAM i tak mamy na zapas dany 32 bitowy typ czy coś.
    Ja tam Varint bardzo lubię, bo jak już i tak musimy czytać ze strumienia w taki sposób jak pokazałem, to varint jest naprawdę bardzo tani czasowo.

    A i tak w ogóle to z tego typu "trików" korzystacie pewnie nawet teraz - np jeśli macie przeglądarkę na silniku Chromium. On korzysta z bazy binarnej LevelDB do przechowywania danych przeglądarki:
    https://en.wikipedia.org/wiki/LevelDB
    A LevelDB właśnie korzysta z tego typu kodowania integerów.
    Integer o zmiennym rozmiarze? Wydajny zapis typu unsigned w C, oszczędzanie pamięci



    khoam napisał:

    Nie ma takiej potrzeby. W C++ jest już standardowa klasa std::variant z kontrolą typów przechowywanych danych. Nie korzysta z pamięci alokowanej dynamicznie, więc dobrze nadaje się do embedded.

    Bardzo ciekawy komentarz, muszę o tym mechanizmie poczytać, chociaż na ten moment po prostu nie mam wiedzy by ocenić, czy on się przyda w tej konkretnej sytuacji którą mam na myśli.
    Powiedzmy, że chcę wysyłać dane przez jakieś wolne medium i zależy mi na szybkim obcinaniu zbędnych bajtów a nie chcę podpinać Snappy czy tam ZLIB, więc mam, upraszczając:
    Kod: text
    Zaloguj się, aby zobaczyć kod

    Ten utworzony bufor bajtów jest potem wysyłany np. socketem.
    Czy w takiej sytuacji ten mechanizm mi jakoś pomoże?

    (oczywiście, po drugiej stronie mam komplementarną klasę BinaryReader...)

    Swoją drogą, powyższy przykład wcale nie jest całkiem zmyślony. Korzystam z tego typu podejścia w projektach, gdzie np. również wysyłam kąty w stopniach (0-360 stopni) odpowiednio upakowane (zmapowane) do jednego bajtu. Analogicznie, jeśli nie potrzeba dużej precyzji, to też nie trzeba wysyłać pełnych danych typu float, można go odpowiednio (stratnie) przerobić i upchać do np 16 bitów, itd.
    Pomogłem? Kup mi kawę.
  • #5 21045234
    khoam
    Poziom 42  
    p.kaczmarek2 napisał:
    Ten utworzony bufor bajtów jest potem wysyłany np. socketem.

    W jaki sposób alokowany jest obszar pamięci, na który wskazuje wskaźnik buffer i w którym momencie?
  • #6 21045632
    p.kaczmarek2
    Moderator Smart Home
    Oto rozwinięcie przykładu które lepiej obrazuje sytuację i odpowiada też na Twoje pytanie. Całość bazowana na rzeczywistej sytuacji z którą mam do czynienia, przykład uwzględnia to skąd bierze się bufor oraz jak korzystam z klasy strumienia:
    Kod: C / C++
    Zaloguj się, aby zobaczyć kod

    Powyższy przykład jest uproszczony w porównaniu do rzeczywistej sytuacji, w praktyce sprawdzane by było więcej rzeczy (długość pakietu, suma kontrolna, ew. fragmentacja) i zasadniczo to samo mogłoby się analogicznie odbywać w języku C. Pakiet jest odbierany jako bufor bajtów o nieznanym znaczeniu a potem jest parsowany.
    Powyższy przykład pokazuje odbieranie, po drugiej stronie jest analogiczna sytuacja, tylko że jest (powiedzmy) klasa BinaryWriter, też jest bufor, i zamiast recv jest send po wypełnieniu bufora.
    Pomogłem? Kup mi kawę.
  • #7 21045982
    William Bonawentura
    Poziom 34  
    p.kaczmarek2 napisał:
    Co sądzicie o tego typu oszczędności miejsca? Korzystaliście może z tego w swoich projektach?


    Na co dzień korzystamy z analogicznego mechanizmu stosując w plikach, zmiennych, transmisji wszechobecne kodowanie UTF-8. Nie ma znaczenia, że chodzi o znaki - to też są liczby. Zakładamy, że w tekście dominują niskie kody (znaki łacińskie), rzadziej dwubajtowe znaki diakrytyczne (ąę) a jeszcze rzadziej trzy i czterobajtowce (greka itp.).

    Pytanie czy nie ma gotowej w C implementacji dla UTF?
  • #8 21046145
    JacekCz
    Poziom 42  
    Binarne protokoły sieciowe tak robią. Pierwszy stopień są liczby np do 16. Bardzo proste, mały narzut kodu, umiarkowana oszczędność.

    Wydajność pomysłu z wątku spada na pysk, z jednorozkazowej do sekwencji rozkazów ze skokiem warunkowym (a co robi skok na współczesnym CPU, to wiemy), tracimy deterministyczny dostęp do N-tego elementu itd...
    Zrobiłem takie coś na studiach, tablica danych inicjacyjnych na 8085. Zaoszczędziłem całe 15-18 bajtów danych. "Się zapomniało", że kod spuchł o 80-120. Czasu nikt nie mierzył, bo tylko 1 raz.

    Lepiej to robią algorytmy kompresyjne "w locie", operujące na drzewie częstości bajtów
    Czyli dana nie jest oceniania statycznie, a w kontekście strumienia, i nie wnikamy czym dana wejściowa jest, "zmarnowany długi integer" będzie miał zera bajtowe. A na przykład strumień pełen -1 jedynek (a bo tak) też się fajnie ściśnie.
    Nawet wieki temu zrobiłem, i nie było to niedziałające. Oczywiście SyperHiperZip to nie będzie, ale warto sobie algorytmikę poćwiczyć.
  • #9 21047464
    Nepto
    Poziom 19  
    Czym to się w praktyce różni od starego dobrego formatu danych TLV (Tag, Length, Value), gdzie Tag mówi o rodzaju danych a Length po prostu określa ilość następujących w części Value bajtów z danymi?
    Powszechnie stosowane w protokołach sieciowych typu TLS, SSH, DHCP czy kontenerach MPEG-4.
  • #10 21061868
    pipiter433
    Poziom 9  
    Do takich rzeczy wymyślono jakiś czas temu CBOR https://cbor.io/ który już jest standardem IETF https://datatracker.ietf.org/doc/html/rfc8949 CBOR potrafi oszczędniej serializować dane niż BER, a kod do serializacji i deserializacji jest niezwykle prosty. CBOR od dawna jest używany w IoT, jest sporo bibliotek które go obsługują. W kwestiach bezpieczeństwa istnieje standard COSE https://datatracker.ietf.org/doc/html/rfc8152 pozwalający na szyfrowanie i podpisywanie opakowanych COSE danych.

    Polecam prezentację twórcy https://youtu.be/nihSTzbs3fs?si=s-WZKITRYmLB61ng

    Oraz sekcję https://datatracker.ietf.org/doc/html/rfc8949#name-comparison-of-other-binary-
REKLAMA