Niestandardowe alokatory sterty

Większość programów może być dość przypadkowa przy przydzielaniu sterty, nawet w takim stopniu, w jakim funkcjonalne języki programowania wolą alokować nowe obiekty niż modyfikować stare, i niech śmieciarz martwi się o uwolnienie rzeczy.

W programowaniu wbudowanym w sektorze cichym istnieje jednak wiele aplikacji, w których nie można w ogóle używać alokacji sterty, ze względu na ograniczenia pamięciowe i twarde w czasie rzeczywistym; liczba obiektów każdego typu, które będą obsługiwane, jest częścią specyfikacji i wszystko jest przydzielane statycznie.

Programowanie gier (przynajmniej w przypadku tych, które są ambitne w kwestii pchania sprzętu) czasami mieści się pomiędzy: możesz użyć alokacji dynamicznej, ale jest wystarczająca ilość pamięci i miękkie ograniczenia w czasie rzeczywistym, że nie można traktować alokatora jako czarnej skrzynki , nie mówiąc już o korzystaniu z funkcji odśmiecania, więc musisz użyć niestandardowych alokatorów. Jest to jeden z powodów, dla których C ++ jest nadal szeroko stosowany w branży gier; pozwala robić takie rzeczy jak http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html

Jakie inne domeny znajdują się na tym terytorium pośrednim? Gdzie poza grami często stosuje się niestandardowe alokatory?

Za każdym razem, gdy masz aplikację, która ma ścieżkę krytyczną wymagającą dużej wydajności, powinieneś się martwić, jak traktujesz pamięć. Większość aplikacji klienckich użytkowników końcowych nie należy do tej kategorii, ponieważ są one oparte głównie na zdarzeniach, a większość zdarzeń pochodzi z interakcji z użytkownikiem i nie ma tak wielu (jeśli w ogóle) ograniczeń wydajności.

Jednak wiele oprogramowania zaplecza powinno skupić się na sposobie obsługi pamięci, ponieważ wiele z tego oprogramowania można skalować w celu obsługi większej liczby klientów, większej liczby transakcji, większej liczby źródeł danych ... Po uruchomieniu przekraczając granice, możesz zacząć analizować, w jaki sposób pamięć użytkowników oprogramowania i pisać niestandardowe schematy alokacji dostosowane do Twojego oprogramowania, zamiast polegać na całkowicie ogólnym alokatorze pamięci, który został napisany, aby obsłużyć każdy możliwy do wyobrażenia przypadek użycia.

Aby podać kilka przykładów ... w mojej pierwszej firmie pracowałem nad pakietem Historian, oprogramowaniem odpowiedzialnym za gromadzenie / przechowywanie / archiwizację danych kontroli procesu (pomyśl o fabryce, elektrowni jądrowej lub rafinerii ropy naftowej z 10 milionami czujników, będziemy przechowywać te dane). Za każdym razem, gdy analizowaliśmy jakiekolwiek wąskie gardło wydajności, które uniemożliwiało Historianowi przetwarzanie większej ilości danych, przez większość czasu problem polegał na sposobie obsługi pamięci. Dokładamy wszelkich starań, aby upewnić się, że malloc / free nie są nazywane, chyba że są absolutnie konieczne.

W mojej obecnej pracy pracuję nad cyfrowym rejestratorem wideo i pakietem analizy. Przy 30 fps każdy kanał odbiera ramkę wideo co 33 milisekundy. Na sprzedawanym przez nas sprzęcie możemy z łatwością nagrać 100 kanałów wideo. To kolejny przypadek, aby upewnić się, że na ścieżce krytycznej (połączenie sieciowe => przechwytywanie komponentów => oprogramowanie do zarządzania rejestratorem => komponenty pamięci => dysk) nie ma żadnych dynamicznych przydziałów pamięci. Mamy niestandardowy alokator ramek, który zawiera koszyki buforów o stałej wielkości i używa LIFO do ponownego wykorzystania wcześniej przydzielonych buforów. Jeśli potrzebujesz 600 KB pamięci, możesz skończyć z buforem 1024 KB, który marnuje miejsce, ale ponieważ jest on specjalnie dostosowany do naszego użytku, gdzie każda alokacja jest bardzo krótkotrwała, działa bardzo dobrze, ponieważ bufor jest używany,

W typie aplikacji, które opisałem (przenoszenie dużej ilości danych z A do B i obsługa dużej liczby żądań klientów) przechodzenie na stos i z powrotem jest głównym źródłem wąskich gardeł wydajności procesora. Ograniczenie fragmentacji sterty do minimum jest dodatkową korzyścią, jednak, o ile mogę powiedzieć, większość współczesnych systemów operacyjnych już implementuje stosy o niskiej fragmentacji (przynajmniej wiem, że Windows to robi i mam nadzieję, że inni też to zrobią). Osobiście od ponad 12 lat pracując w tego typu środowiskach dość często widziałem problemy z wykorzystaniem procesora związane ze stertą, podczas gdy nigdy nie widziałem systemu, który faktycznie cierpiał na rozdrobnioną stertę.

Przetwarzanie wideo, efekty wizualne, systemy operacyjne itp. Często jednak ludzie je wykorzystują. Struktura danych i alokator nie muszą być oddzielone, aby osiągnąć efektywną alokację.

Na przykład wprowadza wiele dodatkowej złożoności, aby podzielić efektywną alokację węzłów drzewa w oktawie z dala od samego oktetu i polegać na zewnętrznym alokatorze. Niekoniecznie naruszeniem SRP jest połączenie tych dwóch problemów razem i nałożenie na oktodę przydziału wielu węzłów jednocześnie, ponieważ nie zwiększa to liczby powodów do zmiany. W praktyce może to zmniejszyć.

Na przykład w C ++ jeden z opóźnionych skutków ubocznych polegających na poleganiu na tym, że standardowe kontenery polegają na zewnętrznym alokatorze, spowodował, że połączone struktury są std::mapi są std::listuważane za prawie bezużyteczne przez społeczność C ++, ponieważ porównują je zstd::allocatorpodczas gdy te struktury danych alokują jeden węzeł na raz. Oczywiście połączone struktury będą w tym przypadku słabo działać, ale wszystko potoczyłoby się znacznie inaczej, gdyby efektywne przydzielanie węzłów dla połączonych struktur było traktowane raczej jako odpowiedzialność za strukturę danych niż za alokatora. Mogą nadal korzystać z alokacji niestandardowej z innych powodów, takich jak śledzenie / profilowanie pamięci, ale poleganie na alokatorze w celu zwiększenia wydajności połączonych struktur podczas próby alokacji węzłów pojedynczo powoduje, że wszystkie z nich są domyślnie wyjątkowo nieefektywne, co byłoby w porządku, gdyby pojawiło się dobrze znane zastrzeżenie, że połączone struktury potrzebują teraz niestandardowego alokatora, takiego jak darmowa lista, aby być dość wydajnym i unikać wyzwalania błędów pamięci podręcznej po lewej i prawej stronie. Mogłoby być coś znacznie bardziej praktycznegostd::list<T, BlockSize, Alloc>, gdzie BlockSizewskazuje liczbę ciągłych węzłów, które należy przydzielić jednocześnie dla wolnej listy (określenie 1 skutecznie prowadziłoby do std::listobecnego stanu).

Ale nie ma takiego zastrzeżenia, które następnie prowadzi do całej wspólnoty głogów powtarzających kultową mantrę, że połączone listy są bezużyteczne, np.

Innym obszarem, w którym może być potrzebny niestandardowy alokator, jest zapobieganie fragmentacji sterty . Z czasem twoja sterta może alokować małe obiekty rozproszone na całej stercie. Jeśli twój program nie może przechowywać pamięci sterty razem, kiedy program zamierza przydzielić większy obiekt, musi odebrać więcej pamięci z systemu, ponieważ nie może znaleźć wolnego bloku między istniejącą, pofragmentowaną stertą (zbyt wiele małych obiekty przeszkadzają). Całkowite wykorzystanie pamięci twojego programu z czasem wzrośnie, a niepotrzebnie zużyjesz dodatkowe strony pamięci. Jest to więc dość duży problem dla programów, które powinny działać przez długi czas (pomyśl o bazach danych, serwerach itp.).

Gdzie poza grami często stosuje się niestandardowe alokatory?

Facebook

Sprawdź jemalloc, którego Facebook zaczyna używać do poprawy wydajności sterty i zmniejszenia fragmentacji.