RSS

Ile bajtów zajmuje jeden bajt

Liczba odsłon: 115

Ile miejsca w pamięci zajmuje jeden bajt? Wydawałoby się, głupie pytanie: bajt musi zajmować przecież dokładnie jeden bajt. Gdy jednak zgłębi się sposób działania mechanizmów dynamicznej alokacji pamięci, taka prosta odpowiedź staje się w oczywisty sposób nieprawdziwa.

Przy okazji omawiania mechanizmów automatycznej gospodarki pamięci operacyjną wspominałem, że dwoma miejscami, w których przede wszystkim umieszcza się wszelkie dane potrzebne programowi są stos oraz sterta. Na stosie odkłada się zmienne lokalne podprogramów, tworzone tylko na czas działania procedury lub funkcji, zaś na stercie tworzy się dynamiczne struktury danych, które muszą przetrwać wyjście z podprogramu lub zmieniać swój rozmiar w czasie jego działania.

Ponieważ sterta jest ciągle poddawana zmianom, musi być przystosowana do śledzenia stopnia zajętości poszczególnych jej fragmentów. Niezbędny jest zatem narzut w postaci wskaźników do kolejnych i poprzednich bloków, tworzących listę umożliwiającą odszukanie kolejnego wolnego bloku lub połączenie dwóch sąsiadujących bloków wolnej pamięci. Można dalej wnioskować, że niewielkie dynamiczne alokacje pamięci będą nieekonomiczne z powodu dużego udziału narzutu organizacyjnego — tak czasowego, jak i pojemnościowego. Najważniejszym pytaniem jest jednak jak duży jest ten narzut, jak warto alokować pamieć i jakich alokacji najlepiej jest się wystrzegać.

W celu zmierzenia minimalnego rozmiaru alokowanych bloków pamięci oraz narzutu nakładanego na każdy z alokowanych bloków napisałem prosty program w języku C, którego zadaniem była alokacja kilku serii bloków pamięci o różnym rozmiarze i wyświetlenie różnic pomiędzy ich adresami. Ponieważ większość implementacji systemu dynamicznej alokacji pamięci pracuje w sposób sekwencyjny (to znaczy kolejno alokowane bloki pamięci są umieszczane bezpośrednio po sobie), znajomość adresów umożliwia poznanie realnych rozmiarów bloków pamięci.

Program alokuje bloki o następujących rozmiarach:

  #include <stdio.h>
  #include <stdlib.h>

  struct large0 { char array[1016]; };
  struct large1 { char array[1020]; };
  struct large2 { char array[1024]; };

  int main()
  {
     char *alloc_char[8];
     struct large0 *alloc_large0[8];
     struct large1 *alloc_large1[8];
     struct large2 *alloc_large2[8];
     unsigned int i;
     /* Allocate memory blocks. */
     for (i = 0; i < 8; ++i) 
        alloc_char[i] = (char*) malloc(1);
     for (i = 0; i < 8; ++i)
        alloc_large0[i] = (struct large0*) malloc(sizeof(struct large0));
     for (i = 0; i < 8; ++i)
        alloc_large1[i] = (struct large1*) malloc(sizeof(struct large1));
     for (i = 0; i < 8; ++i)
        alloc_large2[i] = (struct large2*) malloc(sizeof(struct large2));
     /* Print allocation address differences. */
     for (i = 1; i < 8; ++i)
        printf("%3u. %8i %8i %8i %8i\n", i+1,
           (int) (alloc_char[i] - alloc_char[i-1]),
           (int) ((char*) alloc_large0[i] - (char*) alloc_large0[i-1]),
           (int) ((char*) alloc_large1[i] - (char*) alloc_large1[i-1]),
           (int) ((char*) alloc_large2[i] - (char*) alloc_large2[i-1]));
     /* Free memory. */
     for (i = 0; i < 8; ++i) {
        free(alloc_large0[i]);
        free(alloc_large1[i]);
        free(alloc_large2[i]);
        free(alloc_char[i]);
     }
     return 0;
  }

Oto wyniki testu:

Kompilator, środowisko Minimalny rozmiar bloku Narzut na każdy alokowany blok Granulacja
gcc 4.1.2,
Linux 2.6.22-rc3
16 B 4 B 8 B
gcc 3.4.6,
FreeBSD 6.2
16 B 0 B
gcc 3.4.2,
Windows XP ServicePack 2
16 B 8 B 8 B
Visual C++ 2005
Windows XP ServicePack 2
32 B 24 B 8 B

Podstawowy wniosek wypływający z testu jest taki, że wszystkie analizowane środowiska (poza systemem operacyjnym FreeBSD — o nim za chwilę) zachowują granulację alokacji równą osiem bajtów. Oznacza to, że nigdy nowy, dynamicznie alokowany obiekt nie będzie rozpoczynał się od adresu niepodzielnego bez reszty przez osiem. Powodem jest chęć pobierania obiektów od początku za pomocą pełnych cykli magistrali: procesory rodziny x86 mają magistrale danych o szerokości 64 bitów (8 bajtów), zatem granulacja ośmiobajtowa zapewnia, że już pierwszy cykl odczytu będzie dobrze wykorzystany (nie zajdzie konieczność pobierania zbędnego w danym momencie fragmentu poprzedniego obiektu zaalokowanego na stercie).

Bardzo różnie kształtuje się narzut nakładany na każdy z bloków przez poszczególne środowiska. Kompilator Visual C++ jest tutaj zdecydowanie bardziej rozrzutny, dokładając 24 bajty do każdej alokacji. Warto odnotować, że w wersji Debug programu narzuty są jeszcze większe: każdy blok jest dodatkowo otaczany słowami kontrolnymi, ułatwiającymi wykrywanie operacji typu buffer underrun oraz buffer overrun. Z kolei starsza wersja kompilatora gcc, działająca pod kontrolą systemu Windows, wymaga już tylko 8 bajtów na każdy blok pamięci. Rekordy bije jedno z nowszych wydań kompilatora gcc, działające pod kontrolą systemu Linux: zaledwie 4 bajty niezbędne do opisania każdego alokowanego bloku pamięci oznaczają, że biblioteki zarządzające pamięcią przechowują tylko jeden adres łączący ze sobą bloki, oszczędzając w ten sposób pamięć (i znów, wyjątek w postaci FreeBSD zostanie omówiony za chwilę).

Minimalny rozmiar alokowanego bloku pamięci (w programie testowym alokowane były bloki o rozmiarze jednego bajta) w przypadku kompilatora gcc wynosi – niezależnie od platformy – 16 bajtów. To całkiem rozsądna wartość: rzadko kiedy istnieje potrzeba alokowania mniejszych bloków pamięci, tym bardziej, że od tej wartości należy odjąć narzut biblioteki zarządzającej pamięcią (efektywny rozmiar najmniejszego dynamicznie alokowanego bloku kurczy się zatem do 12 lub nawet do 8 bajtów). Jedynie kompilator Visual C++ podnosi granicę minimalnej alokacji do 32 bajtów, wynika to jednak głównie z dużego narzutu nakładanego na każdy z bloków (mimo alokowania co najmniej 32 bajtów, efektywne wykorzystanie najmniejszego bloku pamięci wynosi co najwyżej 8 bajtów).

Wspominałem dwukrotnie o systemie operacyjnym FreeBSD, którego wyniki wyłamują się z ogólnego schematu. System ten nie nakłada bowiem żadnego narzutu na alokowane bloki pamięci, nie wprowadza też żadnej stałej granulacji. W zamian stosuje on najwyraźniej metodę buforów alokacji o stałych rozmiarach, równych potęgom dwójki: duże obszary pamięci są rozbijane na mniejsze zawsze po połowie, by tworzyć wolne bloki o rozmiarze 16 B, 32 B, 64 B, 128 B, 256 B, 512 B i tak dalej, zgodnie z kolejnymi potęgami dwójki. Choć taki sposób alokacji powoduje pozostawianie niewykorzystanych obszarów (na przykład obiekt o rozmiarze 514 bajtów zajmie cały blok 1024-bajtowy), likwiduje narzuty nakładane na każdy blok z osobna i pozostawia zmiennym nieco miejsca na ewentualny rozrost bez konieczności czasochłonnego kopiowania wieluset bajtów danych.

Najważniejszą nauką wypływającą z przeprowadzonego testu jest to, by nigdy nie alokować bardzo małych bloków pamięci. Klasa dynamicznej tablicy (w stylu klasy vector biblioteki STL lub klas ArrayList języków C# oraz Java) w przypadku obsługi niewielkich elementów (na przykład liczb całkowitych) nie może przechowywać ich pojedynczo na stercie: 1 024 elementy, które teoretycznie powinny zająć 4 096 bajtów pamięci, zajmą efektywnie 16 384 B (kompilator gcc) lub 32 768 B (kompilator Visual C++) pamięci, co stanowi czyste marnotrawstwo. Wszelkie klasy operujące na małych elementach należy implementować w sposób gwarantujący przechowywanie danych w dużych, wieloelementowych blokach.

Również w przypadku większych elementów warto zastanowić się nad jednoczesnym alokowaniem całych ich bloków, zamiast niezależnego alokowania pojedynczych obiektów. Suma narzutów nakładanych na każdy blok może w przypadku kilku tysiecy niezależnych obiektów sięgnąć kilkunastu kilobajtów, zwiększając stopień wykorzystania pamięci podręcznej procesora oraz rozmiar zestawu roboczego aplikacji. Czasem lepiej jest alokować obiekty grupowo z pewnym naddatkiem (wykorzystywanym do powiększania zestawu danych w razie potrzeby), niż tworzyć osobną listę wskaźników przechowujących adresy niezależnych obiektów alokowanych dynamicznie na stercie.

Na postawione na początku artykułu pytanie „ile miejsca w pamięci zajmuje jeden bajt” możemy już teraz bez wahania odpowiedzieć: od 16 do 32 bajtów, w zależności od użytego kompilatora, jego wersji oraz odmiany systemu operacyjnego.


zabrakło mi tylko testu w dev-cpp
DevC++ to środowisko programistyczne, a nie kompilator. Wewnętrznie DevC++ używa kompilatora gcc, a ten został opisany w artykule.