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++
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++
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++
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++
Zapis do strumienia:
Kod: C / C++
Odczyt:
Kod: C / C++
No i automatyczne porównanie - sprawdzenie, czy wszystko jest ok:
Kod: C / C++
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++
Wybieramy z niej najmłodsze 7 bitów:
Kod: C / C++
Potem przesuwamy pozostałe bity na ich miejsce (przesunięcie bitowe o 7 bitów):
Kod: C / C++
Potem sprawdzamy, czy to co nam zostało to wartość zerowa. Jeśli nie, to ustawiamy bit czy czytać dalej:
Kod: C / C++
No i zapisujemy nasz bajt zawierający 7 bitów danych oraz bit czy czytać dalej:
Kod: C / C++
Analogicznie możemy wykonać odczyt:
Kod: C / C++
Zmodyfikujmy nasz kod demonstracyjny:
Kod: C / C++
Wszystko działa.
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++
W pętli for zapisujemy kolejne liczby:
Kod: C / C++
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++
Zapiszmy je sobie w pętli do jednego bufora bez naszej "kompresji", a do drugiego z:
Kod: C / C++
Odpalamy, ile oszczędzi varint?
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:
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ę.
