Prosty alokator bump
Będzie Pan/Pani liniowo przydzielać pamięć.
Prosty alokator bump to bezpłatna lekcja C Academy na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej C Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs C Academy zawiera 4 lekcji w sumie.
Idea alokatora bump
Alokator bump (lub arena) to najprostszy projekt. Używa jednego dużego bufora i pojedynczego przesunięcia. Każda alokacja zwraca bieżące przesunięcie, a następnie zwiększa je o żądany rozmiar.
Nie ma metadanych poszczególnych bloków ani wyszukiwania. Alokacja sprowadza się zasadniczo do jednego dodawania wskaźników, dzięki czemu jest niezwykle szybka.
Statyczny bufor bazowy
W samodzielnym przykładzie opieramy alokator na statycznej tablicy zamiast na stercie systemu operacyjnego. Program kompiluje się i działa wszędzie, bez użycia sbrk ani mmap.
Tablica zapewnia stałą pulę bajtów, którą można podzielić na mniejsze fragmenty.
#define POOL_SIZE 1024
static unsigned char pool[POOL_SIZE];
static size_t offset = 0;Główna funkcja bump
Alokacja sprawdza, czy pozostało wystarczająco dużo miejsca, zapamiętuje początek, przesuwa offset i zwraca wskaźnik początku. Jeśli żądanie spowodowałoby przepełnienie puli, funkcja zwraca NULL.
To sprawdzenie przepełnienia jest jedynym zabezpieczeniem zapewnianym przez alokator bump.
void *bump_alloc(size_t size) {
if (offset + size > POOL_SIZE)
return NULL; /* out of pool */
void *p = &pool[offset];
offset += size;
return p;
}Kompletny, uruchamialny alokator bump
Oto pełny program. Alokuje on z puli dwie liczby całkowite i krótki łańcuch znaków, a następnie je wypisuje, potwierdzając poprawne działanie alokatora.
Zwróć uwagę, jak niewiele kodu wymaga on w porównaniu z rzeczywistą funkcją malloc.
#include <stdio.h>
#include <stddef.h>
#include <string.h>
#define POOL_SIZE 1024
static unsigned char pool[POOL_SIZE];
static size_t offset = 0;
void *bump_alloc(size_t size) {
if (offset + size > POOL_SIZE) return NULL;
void *p = &pool[offset];
offset += size;
return p;
}
int main(void) {
int *a = bump_alloc(sizeof(int));
int *b = bump_alloc(sizeof(int));
char *s = bump_alloc(6);
*a = 10; *b = 32;
strcpy(s, "hi");
printf("%d %d %s\n", *a, *b, s);
printf("used = %zu\n", offset);
return 0;
}Brak indywidualnego zwalniania
Jest jednak pewien haczyk: alokator bump nie może zwolnić pojedynczej alokacji. Ponieważ nie ma metadanych, nie wie, gdzie kończy się jeden blok, a zaczyna następny, więc nie może ponownie wykorzystać pojedynczego bloku.
Można tylko zresetować całą arenę naraz, ustawiając offset z powrotem na zero.
void bump_reset(void) {
offset = 0; /* frees everything at once */
}Dlaczego resetowanie jest użyteczne
Ten model typu „wszystko albo nic” idealnie nadaje się do pracy fazowej: alokujesz wiele obiektów podczas żądania lub klatki, a następnie resetujesz arenę po zakończeniu fazy.
Silniki gier i kompilatory intensywnie korzystają z aren, ponieważ resetowanie ma złożoność O(1) i eliminuje konieczność śledzenia tysięcy pojedynczych zwolnień.
/* Per-frame pattern */
for (int frame = 0; frame < 3; frame++) {
void *tmp = bump_alloc(128);
/* ... use tmp this frame ... */
bump_reset(); /* reclaim instantly */
}Śledzenie pozostałego miejsca
Warto udostępnić informację o tym, ile miejsca pozostało. To po prostu rozmiar puli pomniejszony o bieżące przesunięcie.
Wywołujący mogą na tej podstawie zdecydować, czy przed żądaniem przydzielenia większej ilości pamięci opróżnić bufor, czy go powiększyć.
size_t bump_remaining(void) {
return POOL_SIZE - offset;
}Uruchamialny przykład resetowania
Ten program zapełnia część puli, wyświetla jej wykorzystanie, resetuje ją i pokazuje, że przesunięcie wraca do zera, dzięki czemu miejsce można ponownie wykorzystać.
#include <stdio.h>
#include <stddef.h>
#define POOL_SIZE 256
static unsigned char pool[POOL_SIZE];
static size_t offset = 0;
void *bump_alloc(size_t s){ if(offset+s>POOL_SIZE) return NULL; void *p=&pool[offset]; offset+=s; return p; }
void bump_reset(void){ offset = 0; }
int main(void) {
bump_alloc(100);
printf("after alloc: used=%zu\n", offset);
bump_reset();
printf("after reset: used=%zu\n", offset);
return 0;
}Wyrównanie w alokatorze bump
Przesuwanie bajt po bajcie może zwracać niewyrównane wskaźniki. Aby tego uniknąć, przed zwróceniem wskaźnika należy zaokrąglić przesunięcie w górę do granicy wyrównania.
Szczegółowo omówimy te obliczenia później, ale wyrównanie ma największe znaczenie właśnie w alokatorze bump, ponieważ w przeciwnym razie nie ma w nim dopełnienia.
static size_t align_up(size_t n, size_t a) {
return (n + a - 1) & ~(a - 1); /* a must be power of 2 */
}Wyrównany alokator bump
Łącząc te elementy, wyrównujemy przesunięcie przed każdym przydzieleniem pamięci. Gwarantuje to, że każdy zwrócony wskaźnik będzie odpowiedni dla dowolnego typowego typu.
Kosztem jest niewielka fragmentacja wewnętrzna wynikająca z bajtów dopełnienia.
#define ALIGN 16
void *bump_aligned(size_t size) {
offset = align_up(offset, ALIGN);
if (offset + size > POOL_SIZE) return NULL;
void *p = &pool[offset];
offset += size;
return p;
}Zalety i ograniczenia
Alokatory bump są niezrównanie szybkie i niezwykle proste, a ponadto nie mają narzutu na pojedynczy obiekt. Idealnie sprawdzają się, gdy obiekty mają wspólny czas życia.
Ich wadą jest brak zwalniania pojedynczych obiektów. Gdy czasy życia są różne, potrzebny jest projekt z listą wolnych bloków, omówiony w następnej lekcji.
Szybkie sprawdzenie
Zastanów się, jak alokator bump odzyskuje pamięć.
Podsumowanie
Alokator bump przydziela pamięć, przesuwając jedno przesunięcie w buforze, dzięki czemu alokacja kosztuje niemal tyle co dodanie wartości do wskaźnika.
W zamian za szybkość i prostotę rezygnuje ze zwalniania pojedynczych obiektów i odzyskuje pamięć tylko przez pełny reset. Wyrównuj przesunięcie, aby zwracane wskaźniki były prawidłowe dla wszystkich typów.
Często zadawane pytania
Czy lekcja „Prosty alokator bump” jest bezpłatna?
Tak — pełny tekst „Prosty alokator bump” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu C Academy, przejdź na CoddyKit PRO. Kurs C Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Prosty alokator bump”?
Będzie Pan/Pani liniowo przydzielać pamięć. Ćwiczysz C Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć C Academy?
Nie wymagamy żadnego doświadczenia. C Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.
Ile czasu zajmuje lekcja „Prosty alokator bump”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji C Academy?
Tak. Każda lekcja C Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Jak działa malloc
- Prosty alokator bump
- Listy wolnych bloków i ponowne użycie
- Wyrównanie i dzielenie