Ciekawe przykłady niestandardowych alokatorów w C ++?

Jakie są naprawdę dobre powody, aby zrezygnować std::allocatorz niestandardowego rozwiązania? Czy spotkałeś się z sytuacjami, w których było to absolutnie konieczne dla poprawności, wydajności, skalowalności itp.? Jakieś naprawdę sprytne przykłady?

Niestandardowe podzielniki zawsze były cechą Biblioteki Standardowej, której nie potrzebowałem. Zastanawiałem się tylko, czy ktoś tutaj na SO mógłby podać kilka przekonujących przykładów uzasadniających ich istnienie.

Jak wspomniałem tutaj , widziałem niestandardowy alokator STL Intel TBB znacznie poprawiający wydajność aplikacji wielowątkowej, po prostu zmieniając pojedynczy

std::vector<T>

do

std::vector<T,tbb::scalable_allocator<T> >

(jest to szybki i wygodny sposób przełączania alokatora na sprytne prywatne stosy wątków TBB; patrz strona 7 w tym dokumencie )

Jednym z obszarów, w którym mogą być przydatne niestandardowe alokatory, jest tworzenie gier, szczególnie na konsolach do gier, ponieważ mają one tylko niewielką ilość pamięci i nie mają możliwości wymiany. W takich systemach chcesz mieć pewność, że masz ścisłą kontrolę nad każdym podsystemem, tak aby jeden bezkrytyczny system nie mógł ukraść pamięci z krytycznego. Inne rzeczy, takie jak alokatory puli, mogą pomóc w zmniejszeniu fragmentacji pamięci. Długi, szczegółowy artykuł na ten temat można znaleźć pod adresem:

EASTL - biblioteka standardowych szablonów Electronic Arts

Pracuję nad alokatorem mmap, który umożliwia wektorom korzystanie z pamięci z pliku mapowanego na pamięć. Celem jest posiadanie wektorów używających pamięci, które są bezpośrednio w pamięci wirtualnej mapowanej przez mmap. Naszym problemem jest poprawienie odczytu naprawdę dużych plików (> 10 GB) do pamięci bez narzutu na kopiowanie, dlatego potrzebuję tego niestandardowego alokatora.

Do tej pory mam szkielet niestandardowego alokatora (który pochodzi od std :: alokator), myślę, że jest to dobry punkt wyjścia do pisania własnych alokatorów. Możesz swobodnie używać tego fragmentu kodu w dowolny sposób:

#include <memory>
#include <stdio.h>

namespace mmap_allocator_namespace
{
        // See StackOverflow replies to this answer for important commentary about inheriting from std::allocator before replicating this code.
        template <typename T>
        class mmap_allocator: public std::allocator<T>
        {
public:
                typedef size_t size_type;
                typedef T* pointer;
                typedef const T* const_pointer;

                template<typename _Tp1>
                struct rebind
                {
                        typedef mmap_allocator<_Tp1> other;
                };

                pointer allocate(size_type n, const void *hint=0)
                {
                        fprintf(stderr, "Alloc %d bytes.\n", n*sizeof(T));
                        return std::allocator<T>::allocate(n, hint);
                }

                void deallocate(pointer p, size_type n)
                {
                        fprintf(stderr, "Dealloc %d bytes (%p).\n", n*sizeof(T), p);
                        return std::allocator<T>::deallocate(p, n);
                }

                mmap_allocator() throw(): std::allocator<T>() { fprintf(stderr, "Hello allocator!\n"); }
                mmap_allocator(const mmap_allocator &a) throw(): std::allocator<T>(a) { }
                template <class U>                    
                mmap_allocator(const mmap_allocator<U> &a) throw(): std::allocator<T>(a) { }
                ~mmap_allocator() throw() { }
        };
}

Aby z tego skorzystać, zadeklaruj kontener STL w następujący sposób:

using namespace std;
using namespace mmap_allocator_namespace;

vector<int, mmap_allocator<int> > int_vec(1024, 0, mmap_allocator<int>());

Może być używany na przykład do logowania, gdy przydzielana jest pamięć. Niezbędna jest struktura rebind, w przeciwnym razie kontener wektorowy używa metod alokacji / cofnięcia alokacji nadklas.

Aktualizacja: Alokator mapowania pamięci jest teraz dostępny pod adresem https://github.com/johannesthoma/mmap_allocator i jest LGPL. Zapraszam do wykorzystania go w swoich projektach.

Pracuję z silnikiem pamięci masowej MySQL, który używa C ++ do swojego kodu. Używamy niestandardowego alokatora do korzystania z systemu pamięci MySQL zamiast konkurować z MySQL o pamięć. Pozwala nam to upewnić się, że używamy pamięci jako skonfigurowanej przez użytkownika MySQL, a nie „dodatkowej”.

Przydatne może być użycie niestandardowych alokatorów w celu użycia puli pamięci zamiast sterty. To jeden z wielu przykładów.

W większości przypadków jest to z pewnością przedwczesna optymalizacja. Ale może być bardzo przydatny w niektórych kontekstach (urządzenia wbudowane, gry itp.).

Nie napisałem kodu C ++ z niestandardowym alokatorem STL, ale mogę sobie wyobrazić serwer WWW napisany w C ++, który używa niestandardowego alokatora do automatycznego usuwania tymczasowych danych potrzebnych do odpowiedzi na żądanie HTTP. Alokator niestandardowy może zwolnić wszystkie dane tymczasowe naraz po wygenerowaniu odpowiedzi.

Innym możliwym przypadkiem użycia niestandardowego alokatora (którego użyłem) jest napisanie testu jednostkowego, aby udowodnić, że zachowanie funkcji nie zależy od jakiejś części jej danych wejściowych. Alokator niestandardowy może wypełnić obszar pamięci dowolnym wzorem.

Podczas pracy z procesorami GPU lub innymi koprocesorami czasami korzystne jest przydzielenie struktur danych w pamięci głównej w specjalny sposób . Ten specjalny sposób przydzielania pamięci można w wygodny sposób zaimplementować w niestandardowym alokatorze.

Powód, dla którego niestandardowa alokacja za pośrednictwem środowiska wykonawczego akceleratora może być korzystna podczas korzystania z akceleratorów, jest następujący:

1. dzięki niestandardowej alokacji środowisko wykonawcze akceleratora lub sterownik jest powiadamiany o bloku pamięci
2. dodatkowo system operacyjny może upewnić się, że przydzielony blok pamięci jest zablokowany na stronie (niektórzy nazywają to przypiętą pamięcią ), to znaczy podsystem pamięci wirtualnej systemu operacyjnego może nie przenosić ani usuwać strony w pamięci lub z pamięci
3. jeśli 1. i 2. zatrzymają się i żądany jest transfer danych między blokiem pamięci z zablokowaną stroną a akceleratorem, środowisko wykonawcze może bezpośrednio uzyskać dostęp do danych w pamięci głównej, ponieważ wie, gdzie się one znajdują i może być pewien, że system operacyjny nie przenieś / usuń
4. zapisuje to jedną kopię pamięci, która wystąpiłaby z pamięcią, która została przydzielona w sposób niezablokowany na stronie: dane muszą być skopiowane z pamięci głównej do obszaru pomostowego z zablokowaną stroną, z akceleratora można zainicjować transfer danych (przez DMA )

Używam tutaj niestandardowych podzielników; można nawet powiedzieć, że chodziło o obejście innego niestandardowego zarządzania pamięcią dynamiczną.

Tło: mamy przeciążenia dla malloc, calloc, free i różne warianty operatora new i delete, a linker szczęśliwie sprawia, że ​​STL używa ich dla nas. To pozwala nam robić takie rzeczy, jak automatyczne gromadzenie małych obiektów, wykrywanie wycieków, wypełnianie alokacji, wypełnianie swobodne, alokacja wypełnienia wartownikami, wyrównanie linii pamięci podręcznej dla niektórych alokacji i wolne od opóźnień.

Problem polega na tym, że pracujemy w środowisku osadzonym - nie ma wystarczającej ilości pamięci, aby faktycznie prawidłowo rejestrować wykrywanie wycieków przez dłuższy czas. Przynajmniej nie w standardowej pamięci RAM - jest jeszcze jedna kupa pamięci RAM dostępna gdzie indziej, dzięki niestandardowym funkcjom alokacji.

Rozwiązanie: napisz niestandardowy alokator, który używa rozszerzonej sterty i używaj go tylko w wewnętrznych elementach architektury śledzenia wycieków pamięci ... Wszystko inne jest domyślnie ustawione na normalne przeciążenia typu new / delete, które wykonują śledzenie wycieków. Pozwala to uniknąć samego śledzenia trackera (i zapewnia trochę dodatkowej funkcjonalności pakowania, znamy rozmiar węzłów trackera).

Używamy tego również do przechowywania danych profilowania kosztów funkcji, z tego samego powodu; pisanie wpisu dla każdego wywołania i powrotu funkcji, a także przełączania wątków, może szybko stać się kosztowne. Niestandardowy alokator ponownie daje nam mniejsze alokacje w większym obszarze pamięci debugowania.

Używam niestandardowego podzielnika do liczenia liczby przydziałów / zwolnień w jednej części mojego programu i mierzenia czasu, jaki to trwa. Można to osiągnąć na inne sposoby, ale ta metoda jest dla mnie bardzo wygodna. Szczególnie przydatne jest to, że mogę używać niestandardowego alokatora tylko dla podzbioru moich kontenerów.

Jedna zasadnicza sytuacja: podczas pisania kodu, który musi działać poza granicami modułu (EXE / DLL), ważne jest, aby alokacje i usunięcia miały miejsce tylko w jednym module.

Tam, gdzie to spotkałem, była architektura wtyczek w systemie Windows. Na przykład w przypadku przekazania std :: string przez granicę biblioteki DLL istotne jest, aby wszelkie ponowne alokacje ciągu następowały ze sterty, z której pochodzi, a NIE ze sterty w bibliotece DLL, która może być inna *.

* W rzeczywistości jest to bardziej skomplikowane, ponieważ w przypadku dynamicznego łączenia z CRT to i tak może działać. Ale jeśli każda biblioteka DLL ma statyczne łącze do CRT, udajesz się do świata bólu, w którym nieustannie występują widmowe błędy alokacji.

Jednym z przykładów, kiedy ich użyłem, była praca z systemami wbudowanymi o bardzo ograniczonych zasobach. Powiedzmy, że masz wolne 2 KB pamięci RAM i Twój program musi zajmować część tej pamięci. Musisz przechowywać powiedzmy 4-5 sekwencji gdzieś, czego nie ma na stosie, a dodatkowo musisz mieć bardzo precyzyjny dostęp do tego, gdzie te rzeczy są przechowywane, jest to sytuacja, w której możesz chcieć napisać własny alokator. Domyślne implementacje mogą pofragmentować pamięć, może to być niedopuszczalne, jeśli nie masz wystarczającej ilości pamięci i nie możesz ponownie uruchomić programu.

Jeden projekt, nad którym pracowałem, polegał na użyciu AVR-GCC na niektórych chipach o małej mocy. Musieliśmy przechowywać 8 sekwencji o zmiennej długości, ale ze znanym maksimum. PlikStandardowa implementacja biblioteki zarządzania pamięciąjest cienkim opakowaniem wokół malloc / free, które śledzi, gdzie umieścić elementy, poprzedzając każdy przydzielony blok pamięci wskaźnikiem tuż za końcem tego przydzielonego fragmentu pamięci. Podczas przydzielania nowego fragmentu pamięci, alokator standardowy musi przejść przez każdy fragment pamięci, aby znaleźć następny dostępny blok, w którym zmieści się żądany rozmiar pamięci. Na platformie stacjonarnej byłoby to bardzo szybkie w przypadku tych kilku elementów, ale należy pamiętać, że niektóre z tych mikrokontrolerów są w porównaniu z nimi bardzo powolne i prymitywne. Ponadto fragmentacja pamięci była ogromnym problemem, co oznaczało, że nie mieliśmy innego wyjścia, jak tylko przyjąć inne podejście.

Więc to, co zrobiliśmy, to zaimplementowanie własnej puli pamięci . Każdy blok pamięci był wystarczająco duży, aby zmieścić największą sekwencję, jakiej byśmy potrzebowali. To przydzieliło z wyprzedzeniem bloki pamięci o ustalonych rozmiarach i oznaczyło, które bloki pamięci są aktualnie używane. Zrobiliśmy to, zachowując jedną 8-bitową liczbę całkowitą, w której każdy bit był reprezentowany, jeśli został użyty określony blok. Zamieniliśmy tutaj użycie pamięci na próbę przyspieszenia całego procesu, co w naszym przypadku było uzasadnione, ponieważ zbliżaliśmy ten mikrokontroler do jego maksymalnej mocy obliczeniowej.

Jest wiele innych przypadków, w których widzę pisanie własnego niestandardowego alokatora w kontekście systemów wbudowanych, na przykład jeśli pamięć dla sekwencji nie znajduje się w głównej pamięci RAM, co może często mieć miejsce na tych platformach .

Obowiązkowy link do wykładu Andrei Alexandrescu na konferencji CppCon 2015 na temat alokatorów:

https://www.youtube.com/watch?v=LIb3L4vKZ7U

Fajne jest to, że samo ich wymyślenie sprawia, że ​​myślisz o tym, jak ich użyjesz :-)

W przypadku pamięci współdzielonej istotne jest, aby nie tylko głowica pojemnika, ale także zawarte w niej dane były przechowywane w pamięci współdzielonej.

Dobrym przykładem jest alokator Boost :: Interprocess . Jednak, jak możesz tutaj przeczytać , to wszystko nie wystarczy, aby wszystkie kontenery STL były kompatybilne z pamięcią współdzieloną (z powodu różnych przesunięć mapowania w różnych procesach wskaźniki mogą się „zepsuć”).

Jakiś czas temu bardzo mi się przydało to rozwiązanie: Szybki alokator C ++ 11 dla kontenerów STL . Nieznacznie przyspiesza kontenery STL na VS2017 (~ 5x), a także na GCC (~ 7x). Jest to alokator specjalnego przeznaczenia oparty na puli pamięci. Może być używany z kontenerami STL tylko dzięki mechanizmowi, o który prosisz.

Osobiście używam Loki :: Allocator / SmallObject do optymalizacji wykorzystania pamięci dla małych obiektów - wykazuje dobrą wydajność i satysfakcjonującą wydajność, jeśli musisz pracować z umiarkowaną ilością naprawdę małych obiektów (od 1 do 256 bajtów). Może być do ~ 30 razy bardziej wydajna niż standardowa alokacja nowych / usuniętych C ++, jeśli mówimy o przydzielaniu umiarkowanych ilości małych obiektów o wielu różnych rozmiarach. Istnieje również rozwiązanie specyficzne dla VC o nazwie „QuickHeap”, które zapewnia najlepszą możliwą wydajność (operacje przydzielania i zwalniania alokacji wystarczy odczytać i zapisać adres bloku, który jest przydzielany / zwracany do sterty, odpowiednio w maksymalnie 99. (9)% przypadków - zależy od ustawień i inicjalizacji), ale kosztem znacznego narzutu - wymaga dwóch wskaźników na zakres i jednego dodatkowego na każdy nowy blok pamięci. To'

Problem ze standardową implementacją C ++ new / delete polega na tym, że zwykle jest to po prostu opakowanie dla C malloc / bezpłatna alokacja i działa dobrze w przypadku większych bloków pamięci, takich jak 1024+ bajtów. Ma znaczący narzut pod względem wydajności, a czasem dodatkową pamięć używaną do mapowania. Dlatego w większości przypadków niestandardowe alokatory są implementowane w sposób maksymalizujący wydajność i / lub minimalizujący ilość dodatkowej pamięci potrzebnej do przydzielania małych (≤1024 bajtów) obiektów.

W symulacji graficznej widziałem niestandardowe podzielniki używane do

1. Wiązania wyrównania, które std::allocatornie były bezpośrednio obsługiwane.
2. Minimalizacja fragmentacji poprzez użycie oddzielnych pul dla przydziałów krótkotrwałych (tylko ta klatka) i długoterminowych.