Niestandardowe malloc dla wielu małych, stałych bloków wielkości?

Question

Potrzebuję przydzielić i zwolnić wiele stałych rozmiarów, małych (16-bajtowych) bloków pamięci, bez stałej kolejności. Mogę po prostu nazwać malloc i za darmo dla każdego, ale to prawdopodobnie będzie bardzo nieefektywne. Lepszym rozwiązaniem będzie prawdopodobnie wywoływanie malloc i darmowe dla większych bloków, a obsługa alokacji w samych blokach.

Pytanie brzmi, jak najlepiej to zrobić?

Wydaje się, że nie powinien to być bardzo nietypowy problem lub rzadki problem, i że powinien on zostać "rozwiązany", ale nie mogę niczego znaleźć. Jakieś wskazówki?

W celu wyjaśnienia, mam świadomość, że biblioteki pul pamięci i co nie istnieje, ale te również mają parametr wielkości. Jeśli rozmiar jest stały, dostępne są różne opcje bardziej wydajnych algorytmów, czy są jakieś ich implementacje?

Answer 1

Przed rozpoczęciem uciążliwego zadania przepisania malloc obowiązuje standardowa rada. Profiluj swój kod i upewnij się, że to rzeczywiście jest problem!

Answer 2

Najlepszym sposobem, aby to zrobić, nie jest założenie, że będzie to nieefektywne. Zamiast tego wypróbuj rozwiązanie z malloc, zmierz wydajność i udowodnij, że jest wydajne lub nie. Wtedy, gdy okaże się, że jest on niewystarczający (prawdopodobnie nie będzie), to jedyny czas, w którym powinieneś przenieść się do niestandardowego przydziału. Bez dowodu nigdy się nie dowiesz, czy twoje rozwiązanie jest szybsze, czy nie.

Answer 3

To, czego szukasz, nazywa się pulą pamięci. Istnieją już implementacje, choć nie jest to trudne (i dobra praktyka) tworzenie własnych.

Najprostszą implementacją dla puli danych o tym samym rozmiarze jest tylko opakowanie zawierające bufor o rozmiarze n * i stos n wskaźników. "malloc" z puli wyskakuje z góry. "free" do puli powoduje powrót wskaźnika do stosu.

Answer 4

dla Twojego wymagania Twój niestandardowy przydział będzie naprawdę prosty. po prostu wywołaj dużą pamięć wielościenną

calloc(N * 16) 

, a następnie możesz po prostu rozdawać wpisy w tablicy. Aby śledzić, które lokalizacje macierzy są w użyciu, można użyć prostej bitmapy, a następnie za pomocą kilku sprytnych operacji na bitach i odejmowania wskaźnika niestandardowe operacje malloc/free powinny być dość łatwe. jeśli zabraknie Ci miejsca, możesz po prostu realloc trochę więcej, ale posiadanie odpowiedniej stałej wartości domyślnej byłoby trochę łatwiejsze.

chociaż powinieneś najpierw użyć najpierw malloc. malloc tworzy pule wolnych bloków pamięci o różnych rozmiarach, założę się, że istnieje pula dla 16-bajtowych bloków pamięci (różne implementacje mogą lub nie, ale jest to dość powszechna optymalizacja), a ponieważ wszystkie twoje przydziały są tej samej wielkości fragmentacji nie powinno być problemem. (plus debugowanie twojego przydziału może być trochę koszmarem.)

Answer 5

Masz rację, to częsty problem [Edycja: jak zrobić przydzielanie o stałej wielkości, mam na myśli. "malloc spowalnia moją aplikację" jest mniej powszechne niż mogłoby ci się wydawać.

Jeśli Twój kod jest zbyt wolny, a malloc wiarygodnym winowajcą, to prosty przydział komórek (lub "pula pamięci") może poprawić sytuację. Niemal na pewno możesz go gdzieś znaleźć lub łatwo napisać:

Przydziel duży blok i umieść pojedynczy węzeł na początku każdej 16-bajtowej komórki. Połącz je wszystkie razem.Aby przydzielić, zdejmij głowę z listy i zwróć ją. Aby zwolnić, dodaj komórkę do nagłówka listy. Oczywiście, jeśli spróbujesz przydzielić i lista jest pusta, musisz przydzielić nowy duży blok, podzielić go na komórki i dodać wszystkie do wolnej listy.

Możesz tego uniknąć, jeśli chcesz. Po przydzieleniu dużego bloku, po prostu przechowuj wskaźnik na jego końcu. Aby przydzielić, przenieś wskaźnik o 16 bajtów przez blok i zwróć nową wartość. Chyba że był już na początku bloku [*], oczywiście. Jeśli tak się stanie, a wolna lista jest pusta, potrzebujesz nowego dużego bloku. Bezpłatne nie zmienia się - wystarczy dodać węzeł do bezpłatnej listy.

Masz opcję, czy najpierw wyjść z bloku, i sprawdzić listę darmową, jeśli jest wyczerpana, lub najpierw sprawdzić wolną listę i zlikwidować blok, jeśli jest pusty. Nie wiem, który wydaje się być szybszy - dobrą rzeczą w ostatniej darmowej liście jest to, że jest ona przyjazna dla pamięci podręcznej, ponieważ używasz pamięci, która była ostatnio używana, więc prawdopodobnie spróbowałbym tego pierwszy.

Należy zauważyć, że węzeł listy nie jest potrzebny, gdy komórka jest przydzielona, ​​więc zasadniczo narzut na komórkę wynosi zero. Całkiem poza szybkością, jest to prawdopodobnie przewaga nad malloc lub innymi alokatorami ogólnego przeznaczenia.

Należy pamiętać, że upuszczenie całego przydziału jest w zasadzie jedynym sposobem zwalniania pamięci z powrotem do systemu, więc użytkownicy, którzy planują przydzielić dużo komórek, korzystać z nich i uwolnić ich wszystkich, powinni utworzyć własne alokator, użyj go, a następnie zniszcz. Zarówno dla wydajności (nie musisz zwolnić wszystkich komórek), jak i dla zapobieżenia efektowi fragmentacji, w którym cały blok musi być zachowany, jeśli którakolwiek z jego komórek jest w użyciu. Jeśli nie możesz tego zrobić, twoje wykorzystanie pamięci będzie znaczącą wartością wody w czasie, w którym program był uruchomiony. W przypadku niektórych programów, które stanowią problem (na przykład długotrwały program ze sporadycznymi dużymi skokami w użyciu pamięci, w systemie, w którym pamięć jest ograniczona). Dla innych jest to absolutnie w porządku (na przykład, jeśli liczba używanych komórek zwiększa się do bardzo bliskiej końca programu lub zmienia się w zakresie, w którym naprawdę nie obchodzi cię, że zużywasz więcej pamięci, niż to możliwe). Dla niektórych jest to pożądane (jeśli wiesz, ile pamięci chcesz użyć, możesz przydzielić wszystko z góry i nie musisz się martwić o awarie). W związku z tym niektóre implementacje z malloc mają trudności z przywracaniem pamięci z procesu do systemu operacyjnego.

[*] Gdzie "początek bloku" prawdopodobnie oznacza "początek bloku, plus rozmiar jakiegoś węzła używanego do utrzymania listy wszystkich bloków, dzięki czemu wszystkie mogą zostać uwolnione, gdy alokator komórek jest zniszczony".

Answer 6

Możesz spróbować zastąpić malloc/free with an alternative implementation, który nadaje się do wielu małych przydziałów.

Answer 7

Wilson, Johnstone, Neely i Boles napisali: a nice paper surveying all sorts of different allocators.

Z mojego doświadczenia wynika, wydajność i napowietrznych różnica między dobrym ustalonej puli podzielnika i tylko opierając się na dlmalloc może być masywny w przypadkach, gdy wprowadzamy wiele, wiele krótkotrwałych małych przydziałów w ograniczonej przestrzeni adresowej (na przykład system bez pliku stronicowania). W aplikacji, nad którą pracuję w tej chwili, nasza główna pętla przeskakuje od 30ms do> 100ms, jeśli zamieniam nasz przydział bloków na proste wywołania na malloc() (i ostatecznie ulega awarii z powodu fragmentacji).

Answer 8

Poniższy kod jest dość brzydki, ale celem nie jest piękno, ale odkrycie, jak duży jest blok przydzielony przez malloc.
Prosiłem o 4 bajty, a malloc zażądał i otrzymał 135160 bajtów z systemu operacyjnego.

#include <stdio.h> 
#include <malloc.h> 


int main() 
{ 
    int* mem = (int*) malloc(sizeof(int)) ; 
    if(mem == 0) return 1; 
    long i=1L; 

    while(i) 
    { 
     mem[i-1] = i; 
     printf("block is %d bytes\n", sizeof(int) * i++); 
    }//while 

    free(mem); 
    return 0 ; 
} 

$ g ++ -o plik file.cpp
$ ./file
...
blok jest 135144 bajtów
blok jest 135148 bajtów
blok jest 135152 bajtów
blok jest 135156 bajtów
blok to 135160 bajtów
Nieprawidłowości segmentacji

Ta lloc to poważna sprawa.
realloc nie wykonuje żadnego wywołania systemowego, jeśli żądany rozmiar jest mniejszy niż dostępny z powodu wewnętrznego pulowania.
Po ponownym przeniesieniu pamięci do większej strefy, nie niszczy ona poprzedniego bloku, ani nie zwraca go bezpośrednio do systemu. To może być nadal dostępne (oczywiście całkowicie niebezpieczne). To wszystko nie ma sensu, ktoś potrzebuje dodatkowej puli pamięci.

Answer 9

Ze względu na zainteresowania naukowe pracowałem nad rozwiązaniem tego problemu kilka dni temu. Implementacja jest bardzo prosta, ale kompletna i wspomniałeś, że szukasz zastępczego zamiennika, więc myślę, że moja implementacja mogłaby dla ciebie działać.

Zasadniczo działa jak opisany patros, z tym że automatycznie żąda większej ilości pamięci, jeśli nie ma już wolnych bloków. Kod został przetestowany z dużą połączoną listą (około 6 milionów węzłów, każde 16 bajtów w rozmiarach) przeciwko naiwnemu schematowi malloc()/free() i wykonywany około 15% szybciej. Przypuszczalnie jest to użyteczne dla twojej intencji. Łatwo jest dostosować go do różnych rozmiarów bloków, ponieważ rozmiar bloku określony podczas tworzenia tak dużego kawałka pamięci.

Kod jest dostępny na github: challoc

Przykład użycia:

int main(int argc, char** argv) { 
    struct node { 
      int data; 
     struct node *next, *prev; 
    }; 
    // reserve memory for a large number of nodes 
    // at the moment that's three calls to malloc() 
    ChunkAllocator* nodes = chcreate(1024 * 1024, sizeof(struct node)); 

    // get some nodes from the buffer 
    struct node* head = challoc(nodes); 
    head->data = 1; 
    struct node* cur = NULL; 
    int i; 
    // this loop will be fast, since no additional 
    // calls to malloc are necessary 
    for (i = 1; i < 1024 * 1024; i++) { 
      cur = challoc(nodes); 
     cur->data = i; 
     cur = cur->next; 
    } 

    // the next call to challoc(nodes) will 
    // create a new buffer to hold double 
    // the amount of `nodes' currently holds 

    // do something with a few nodes here 

    // put a single node back into the buffer 
    chfree(nodes,head); 

    // mark the complete buffer as `empty' 
    // this also affects any additional 
    // buffers that have been created implicitly 
    chclear(nodes); 

    // give all memory back to the OS 
    chdestroy(nodes); 

    return 0; 
}