Czy istnieje obciążenie pamięci związane z alokacją pamięci sterty (np. Znaczniki w stercie)?

Question

Myśląc w szczególności o C++ w systemie Windows przy użyciu najnowszego kompilatora Visual Studio C++, zastanawiam się nad implementacją sterty:

Zakładając, że używam kompilatora wydania i nie chodzi mi o fragmentację/pakowanie pamięci problemy, czy istnieje obciążenie pamięci związane z przydzielaniem pamięci na stercie? Jeśli tak, to z grubsza ile bajtów na przydział może to być? Czy byłby większy w 64-bitowym kodzie niż w wersji 32-bitowej?

Nie wiem zbyt wiele o nowoczesnych implementacjach sterty, ale zastanawiam się, czy istnieją znaczniki zapisane w stercie przy każdej alokacji, czy też jakaś tabela jest utrzymywana (jak tablica alokacji plików).

W powiązanym punkcie (ponieważ myślę przede wszystkim o funkcjach biblioteki standardowej, takich jak "map"), implementacja biblioteki standardowej firmy Microsoft używa w dowolnym momencie własnego przydziału (dla takich elementów, jak węzły drzewa) w celu optymalizacji kupy stosowanie?

Answer 1

Tak, absolutnie.

Każdy blok przydzielonej pamięci będzie miał stały narzut "nagłówka", a także małą zmienną część (zazwyczaj na końcu). Dokładnie to, ile to zależy od używanej biblioteki wykonawczej C. W przeszłości eksperymentalnie odkryłem, że jest to około 32-64 bajty na przydzielenie. Częścią zmienną jest poradzenie sobie z wyrównaniem - każdy blok pamięci zostanie dopasowany do jakiegoś miłego, nawet 2^n adresu bazowego - zwykle 8 lub 16 bajtów.

Nie jestem zaznajomiony z wewnętrznym projektem std::map lub podobnymi pracami, ale bardzo wątpię, że mają tam specjalne optymalizacje.

dość łatwo można przetestować narzutu przez:

char *a, *b; 

a = new char; 
b = new char; 

ptrdiff_t diff = a - b; 

cout << "a=" << a << " b=" << b << " diff=" << diff; 

[Uwaga dla pedantów, który jest prawdopodobnie najbardziej tutejszych bywalców, powyższe wyrażenia ab wywołuje niezdefiniowanej zachowanie, ponieważ odjęcie adresu jednym kawałku przydzielonego i adres innego, jest niezdefiniowanym zachowaniem. Ma to na celu poradzenie sobie z maszynami, które nie mają liniowych adresów pamięci, np. pamięć segmentowana lub "różne typy danych są przechowywane w lokalizacjach w oparciu o ich typ". Powyższe powinno zdecydowanie działać na każdym systemie operacyjnym opartym na procesorze x86, który nie używa segmentowego modelu pamięci z wieloma segmentami danych dla sterty - co oznacza, że ​​działa na systemach Windows i Linux w trybie 32- i 64-bitowym].

Możesz go uruchomić z różnych typów. - po prostu pamiętać, że edycja jest „numerem typu, więc jeśli je będzie w«czterech jednostek bajtów»Można zrobić reinterpret_cast<char*>(a) - reinterpret_cast<char *>(b);

[diff może być ujemna, a jeśli uruchomić to w pętli (bez usuwania a i b), może się okazać, nagłe skoki gdzie jedna duża część pamięci jest wyczerpana, a runtime library przeznaczono inny duży blok]

Answer 2

Program Visual C++ osadza informacje sterujące (łącza/rozmiary i prawdopodobnie niektóre sumy kontrolne) w pobliżu granic przydzielonych buforów. atch przepełnienia bufora podczas alokacji pamięci i dealokacji.

Poza tym należy pamiętać, że malloc() potrzeby powrotu wskaźników odpowiednio wyrównane dla wszystkich podstawowych typów (char, int, long long, double, void*, void(*)()) oraz że wyrównanie jest zwykle od wielkości największego typu, tak może to być 8 lub nawet 16 bajtów. Jeśli przydzielimy pojedynczy bajt, od 7 do 15 bajtów można utracić tylko w przypadku wyrównania. Nie jestem pewien, czy operator new ma takie samo zachowanie, ale może tak być.

To powinno dać ci pomysł. Dokładne marnowanie pamięci może zostać określone tylko na podstawie dokumentacji (jeśli istnieje) lub testu. Standard językowy nie definiuje go w żadnych kategoriach.

Answer 3

Tak. Wszystkie praktyczne dynamiczne podzielniki pamięci mają minimalną ziarnistość . Na przykład, jeśli ziarnistość wynosi 16 bajtów, a żądasz tylko 1 bajta, to mimo wszystko przydzielane jest całe 16 bajtów. Jeśli poprosisz o 17 bajtów, przydzielony zostanie blok o wielkości 32 bajty itp.

Istnieje również (powiązany) problem wyrównania.

Sporo podzielniki wydają się być połączeniem Wielkość mapy i wolnych list - one podzielone potencjalnych wielkości alokacji z „wiadra” i zachować oddzielną listę darmowy dla każdego z nich. Spójrz na Doug Lea's malloc. Istnieje wiele innych technik alokacji z różnych kompromisów, ale to wykracza poza zakres tutaj ...

---

Zwykle 8 lub 16 bajtów. Jeśli alokator używa wolnej listy, musi zakodować dwa wskaźniki w każdym wolnym gnieździe, aby wolny slot nie był mniejszy niż 8 bajtów (w wersji 32-bitowej) lub 16-bajtowej (w 16-bitach). Na przykład, jeśli program przydzielający próbował podzielić 8-bajtowe gniazdo w celu zaspokojenia żądania 4-bajtowego, pozostałe 4 bajty nie miałyby wystarczającej przestrzeni do zakodowania wskaźników wolnej listy.

Na przykład, jeśli long long na platformie jest 8 bajtów, to nawet jeśli wewnętrzne struktury danych podzielnika mogą obsługiwać bloki mniejsze niż, że faktycznie alokacji mniejszy blok może pchnąć następny przydział 8-bajtowy do niewyrównanego adresu pamięci.