Używam niestandardowej implementacji sterty w jednym z moich projektów. Składa się z dwóch głównych części:Sterty zoptymalizowane do (bez ograniczenia) użycia jednowątkowego
Naprawiono stertę wielkości bloku. To znaczy. sterty, która przydziela bloki tylko określonego rozmiaru. Przydziela większe bloki pamięci (strony pamięci wirtualnej lub z innego sterty), a następnie dzieli je na jednostki przydzielania energii atomowej.
Szybko wykonuje alokację/uwolnienie (w O (1)) i nie ma narzutów na pamięć, nie biorąc pod uwagę rzeczy narzuconych przez stertę zewnętrzną.
Zasobnik ogólnego zastosowania ogólnego przeznaczenia. Składa się z wiader z wyżej wymienionych (stałych) hałd. WRT żądany rozmiar alokacji wybiera odpowiedni zasobnik i wykonuje alokację za jego pośrednictwem.
Ponieważ cała aplikacja jest (mocno) wielowątkowa - globalna sterty blokuje odpowiednią łyżkę podczas jej pracy.
Uwaga: w przeciwieństwie do tradycyjnych hałdów, ta sterta wymaga wielkości alokacji nie tylko dla przydziału, ale także dla uwolnienia. Pozwala to na identyfikację odpowiedniego zasobnika bez przeszukiwania lub dodatkowego obciążenia pamięci (np. Zapisanie rozmiaru bloku przed przydzielonym blokiem). Choć nieco mniej wygodne, w moim przypadku jest OK. Ponadto, ponieważ "konfiguracja kubełkowa" jest znana w czasie kompilacji (zaimplementowana za pośrednictwem szablonu voodoo C++) - odpowiednia łyżka jest określana w czasie kompilacji.
Do tej pory wszystko wygląda (i działa) dobrze.
Ostatnio pracowałem nad algorytmem, który wykonuje operacje sterty ciężko i naturalnie wpływa znacząco na wydajność sterty. Profilowanie ujawniło, że jego działanie jest znacząco ograniczone przez blokowanie blokowania. Oznacza to, że sama sterta działa bardzo szybko (typowa alokacja wymaga tylko kilku instrukcji do dereferencji pamięci), ale ponieważ cała aplikacja jest wielowątkowa - odpowiednia łyżka jest chroniona przez sekcję krytyczną, która opiera się na instrukcjach połączonych, które są znacznie cięższe.
Naprawiłem to tymczasem, nadając temu algorytmowi własną wydzieloną stertę, która nie jest chroniona przez krytyczną sekcję. Wymaga to jednak kilku problemów/ograniczeń na poziomie kodu. Takich jak potrzeba przekazywania informacji kontekstowych głęboko w stosie, gdziekolwiek sterty mogą być konieczne. Można również użyć TLS, aby tego uniknąć, ale może to powodować problemy z ponownym wejściem w moim konkretnym przypadku.
Zastanawiam się: czy istnieje znana technika optymalizacji stosu do (ale nie ogranicza się do) użycia jednowątkowego?
EDIT:
Specjalne podziękowania dla @Voo dla sugeruje sprawdzanie tcmalloc przez Google.
Wydaje się działać podobnie do tego, co zrobiłem mniej lub bardziej (przynajmniej dla małych obiektów). Ale dodatkowo rozwiązują dokładnie ten sam problem, utrzymując w pamięci wątku buforowanie.
Ja też myślałem w tym kierunku, ale myślałem o zachowaniu w wątku hałdy. Następnie zwolnienie bloku pamięci przydzielonego ze sterty należącego do innego wątku jest nieco trudne: należy go wstawić w rodzaj zablokowanej kolejki, a ten inny wątek powinien zostać powiadomiony i asynchronicznie uwolnić oczekujące alokacje. Asynchroniczna dealokacja może powodować problemy: jeśli wątek jest zajęty z jakiegoś powodu (na przykład wykonuje agresywne obliczenia) - w rzeczywistości nie ma deallokacji pamięci. Dodatkowo w scenariuszu wielowątkowym koszt dealokacji jest znacznie wyższy.
OTOH pomysł z buforowaniem wydaje się znacznie prostszy i bardziej wydajny. Spróbuję to rozpracować.
Wielkie dzięki.
P.S .:
Rzeczywiście tcmalloc Google jest wielki. Uważam, że jest zaimplementowany w sposób podobny do tego, co zrobiłem (przynajmniej część o stałej wielkości).
Ale to pedantyczna sprawa, w której moja kupa jest lepsza. Według dokumentów, tcmalloc nakłada narzut około 1% (asymptotycznie), podczas gdy mój narzut wynosi 0,0061%. Dokładnie 4/64K.
:)
To pamięta Moje strony do testów zrobiłem rok temu. Powszechnie stosowany "słaby" standardowy mechanizm zajmuje ponad 100 razy dobrą, "niestandardową" implementację. –
Chciałbym zobaczyć, co zrobiłeś, jeśli jest szybszy niż standardowy alokator pamięci. Ponieważ większość standardowych implementacji już robi to, co twierdzi twój (i wiele więcej). Uważam, że roszczenie O (1) jest ciekawe, szczególnie gdy nie dochodzisz roszczenia (jestem pewien, że zrobisz niezłą monetę, gdy twój patent na to przechodzi). –
Cały pomysł na wiadro to w zasadzie tcmalloc google'a (chociaż ponieważ jest to ogólny alokator, musi on dynamicznie decydować, którego kubełka użyć). tcmalloc używa lokalnej pamięci wątku, aby uniknąć dokładnie problemu i rzadko przydziela się z ogólnej sterty, a tym samym unika blokad. – Voo