Wydajny menedżer sterty dla ciężkich odejść, małe alokacje?

Question

Poszukuję pomysłów na menedżera sterty, który poradzi sobie w bardzo konkretnej sytuacji: wiele bardzo małych przydziałów, od 12 do 64 bajtów. Cokolwiek większego, przejdę do zwykłego zarządcy sterty, więc tylko małe klocki muszą być zaspokojone. Wymagane jest tylko wyrównanie 4-bajtowe.

Moje główne obawy są

1. Overhead. Zwykła kupka libc zazwyczaj zaokrągla alokację do wielokrotności 16 bajtów, a następnie dodaje kolejny 16-bajtowy nagłówek - oznacza to ponad 50% narzut na alokację 20-bajtową, która jest do bani.
2. Wydajność

Jeden pomocny aspektem jest to, że Lua (który jest użytkownikiem tej sterty) powie Ci rozmiar bloku to uwolnienie, gdy nazywa free() - może to umożliwić pewne optymalizacje.

Opublikuję moje bieżące podejście, które działa dobrze, ale chciałbym go poprawić, o ile to możliwe. Jakieś pomysły?

Answer 1

Możliwe jest zbudowanie menedżera sterty, który jest bardzo wydajny dla obiektów, które są tego samego rozmiaru. Możesz utworzyć jedno z tych stert dla każdego rozmiaru obiektu, którego potrzebujesz, lub jeśli nie masz nic przeciwko użyciu odrobiny przestrzeni, utwórz jeden dla 16-bajtowych obiektów, jeden dla 32, a drugi dla 64. Maksymalny narzut będzie 31 bajtów dla alokacji 33 bajtów (która trafiłaby na 64 stosy bloków).

Answer 2

Odpowiedź może zależeć od wzorców cyklu życia tych obiektów. Jeśli wszystkie obiekty są tworzone instancjami, a następnie wszystkie są usuwane za jednym zamachem, może być rozsądne utworzenie bardzo prostego menedżera stosu, który alokuje pamięć, po prostu zwiększając wskaźnik. Następnie, kiedy skończysz, rozwal całą stertę.

Raymond Chen złożył interesting post, który może ci zainspirować. :)

Answer 3

Jeśli grono pamięć została przydzielona, ​​używany i uwolniony przed przejściem do następnej rundy alokacji, polecam stosując najprostszą przydzielania możliwe:

typedef struct _allocator { 
    void* buffer; 
    int start; 
    int max; 
} allocator; 

void init_allocator(size_t size, allocator* alloc) { 
    alloc->buffer = malloc(size); 
    alloc->start = 0; 
    alloc->max = size; 
} 

void* allocator_malloc(allocator* alloc, size_t amount) { 
    if (alloc->max - alloc->start < 0) return NULL; 
    void* mem = alloc->buffer + alloc->start; 
    alloc->start += bytes; 
    return mem; 
} 

void allocator_free(allocator* alloc) { 
    alloc->start = 0; 
} 

Answer 4

Aby rozwinąć na jakiej Greg Hewgill mówi, że jednym ze sposobów na zrobienie ultra-wydajnego stosu o stałej wielkości jest:

1. Podziel duży bufor na węzły. Rozmiar węzła musi wynosić co najmniej sizeof (void *).
2. Połącz je w postaci pojedynczo połączonej listy ("wolna lista"), używając jako pierwszego odnośnika pierwszego sizeof (void *) bajtów każdego wolnego węzła. Przydzielone węzły nie będą potrzebowały wskaźnika łącza, więc narzut na węzeł wynosi 0.
3. Przydziel, usuwając nagłówek listy i zwracając go (2 ładunki, 1 magazyn).
4. Bezpłatne poprzez wstawienie na początku listy (1 ładunek, 2 sklepy).

Oczywiście krok 3 musi również sprawdzić, czy lista jest pusta, a jeśli tak, to zrobić dużo pracy, otrzymując nowy duży bufor (lub awarię).

Jeszcze bardziej wydajne, jak powiadają Greg D i hazzen, jest przydzielanie poprzez zwiększanie lub zmniejszanie wskaźnika (1 ładunek, 1 sklep) i nie oferowanie w ogóle sposobu na uwolnienie pojedynczego węzła.

Edycja: W obu przypadkach za darmo można poradzić sobie z komplikacją "cokolwiek większego, co przekazuję zwykłemu zarządcy sterty" przez pomocny fakt, że odzyskasz rozmiar w rozmowie za darmo. W przeciwnym razie patrzysz na flagę (narzut pewnie 4 bajty na węzeł) lub szukanie w jakimś rekordzie buforów, z których korzystałeś.

Answer 5

Ja lubię jedną odpowiedź.

Możesz również rozważyć The buddy system dla swoich zestawów stałych stosów wielkości.

Answer 6

Używam głównie menedżera pamięci O (1) małego bloku (SBMM). Zasadniczo działa to w następujący sposób:

1) Przydziela większe superbloki z systemu operacyjnego i śledzi adresy początkowy i końcowy jako zakres. Rozmiar SuperBlock jest regulowany, ale 1 MB ma całkiem niezły rozmiar.

2) SuperBlocks są podzielone na Bloki (również regulowane w rozmiarach ... 4K-64K jest dobre w zależności od aplikacji). Każdy z tych bloków obsługuje alokacje o określonym rozmiarze i przechowuje wszystkie elementy w bloku jako pojedynczo połączoną listę. Po przydzieleniu SuperBlock tworzysz listę darmowych bloków.

3) Przydzielenie przedmiotu oznacza A) Sprawdzenie, czy istnieje Blok z Wolnymi Przedmiotami, który obsługuje ten rozmiar - a jeśli nie, przydzielenie nowego Bloku z SuperBlocków. B) Usuwanie przedmiotu z wolnej listy bloku.

4) Zwolnienie pozycji po adresie oznacza A) Znalezienie SuperBlock zawierającej adres (*) B) Odnalezienie bloku w SuperBlock (odejmowanie adresu początkowego SuperBlock i dzielenie według rozmiaru bloku) C) Przesunięcie elementu z powrotem na listę Wolnego przedmiotu bloku.

Jak stwierdziłem, ten SBMM jest bardzo szybki, ponieważ działa z wydajnością O (1) (*). W wersji, którą zaimplementowałem, używam AtomicSList (podobnego do SLIST w Windows), aby była to nie tylko wydajność O (1), ale także ThreadSafe i LockFree w implementacji. Możesz faktycznie zaimplementować algorytm za pomocą Win32 SLIST, jeśli chcesz.

Co ciekawe, algorytm alokacji bloków z SuperBlocks lub Elementów z Blocks daje prawie identyczny kod (oba są przydziałami O (1) poza Wolną Listą).

(*) SuperBloki są rozmieszczone w ramce o średniej (O) (O) średniej wydajności (ale potencjalny O (Lg N) dla najgorszego przypadku, gdzie N to liczba SuperBlocków). Szerokość rangemap zależy od znajomości w przybliżeniu, ile pamięci będziesz potrzebować, aby uzyskać wydajność O (1). Jeśli przeregulujesz, zmarnujesz trochę pamięci, ale nadal uzyskasz wydajność O (1). Jeśli wykonasz undershoot, osiągniesz O (Lg N), ale N będzie dla SuperBlock - nie liczy się przedmiot. Ponieważ liczba SuperBlock jest bardzo niska w porównaniu do liczby Przedmiotów (o około 20 binarnych rzędów wielkości w moim kodzie), nie jest tak krytyczna jak reszta alokatora.