Zliczanie referencji vs Mark and Swap

0

Cześć, zastanawia mnie porównanie zliczania referencji stosowanego np. w C++ oraz Mark and Sweep stosowanego w JVM. Teoretycznie wydaje się że zliczanie referencji jest efektywniejsze, bowiem nie ma pauz na GC - koszt zwalniania zaalokowanego miejsca jest bardziej rozłożony w czasie i równomierny. Z drugiej strony wadą jest słabe radzenie sobie z cyklicznymi referencjami, z czym akurat sobie umie w miare dobrze popradzić M&S. Czy to że M&S jest tak popularny wynika z tego że łatwiej sobie poradzić z cyklicznymi referencjami? A może performance M&S nie jest taki słaby? Haskell stosuje Garbage Collector a nie zliczanie referencji, mimo że raczej tam nie ma cyklicznych zależności.
@Shalom @mar-ek1 @jarekr000000

0

Nie rozumiem. Przecież jak masz cykliczne referencje, to zliczanie z definicji odpada. Druga sprawa - dlaczego twierdzisz, że zliczanie referencji implikuje brak pauz GC?

0

Zliczanie referencji nie rozwiąże cykli, a przynajmniej nie w naiwnym podejściu.

Jest masa publikacji naukowych odnośnie wydajności zliczania referencji i zazwyczaj jest to wolniejsze. Poszukaj i poczytaj.

6

CMS (Concurrent Mark and Sweep) został oznaczony jako przestarzały w Javie 9 ( https://openjdk.java.net/jeps/291 ), a w Javie 14 został usunięty ( https://openjdk.java.net/jeps/363 ). G1 GC w najnowszych wersjach Javy jest na tyle dopracowany, że może zastąpić z powodzeniem CMSa.

Zliczanie referencji w C++ w środowisku wielowątkowym jest kosztowne, a obecnie nawet dość błędogenne. W C++20 mają dość atomic referencje, które będą bardziej solidne: https://www.modernescpp.com/index.php/atomic-smart-pointers

Źle zrobiony destruktor może wysadzić stos jeśli źle ustawisz zależności destruktorów: https://softwareengineering.s[...]-large-list-overflow-my-stack Przy tracing GC to nie występuje, bo tam nie ma tego typu zależności (GC ma swoją kolejkę śmieci i je obrabia jak chce, nie trzeba wywoływać destruktorów/ finalizerów w żadnej specjalnej kolejności). Nawet jeśli stos nie wybuchnie to i tak przy destrukcji dużej struktury danych nastąpi duża pauza, bo destruktory działają synchronicznie. Niskopauzowe GC usuwają obiekty bez zatrzymywania programu (np http://openjdk.java.net/projects/shenandoah http://openjdk.java.net/projects/zgc ).

Niektóre GC są compacting tzn defragmentują pamięć. Jeśli np w danej (np 4-kilobajtowej) stronie pamięci masz zaalokowane 10 bajtów to nie możesz jej np oddać systemowi. Jeśli GC nie przesuwa obiektów ze stron prawie pustych do stron bardziej zapełnionych (to jest to kompaktowanie) to ogólnie tracisz użytkową pamięć. Chyba wszystkie GC Javowe oprócz CMSa są compacting. Firefox też ma compacting GC: https://hacks.mozilla.org/201[...]e-collection-in-spidermonkey/ Inne przeglądarki czy platformy programistyczne pewnie też.

0

CMS (Concurrent Mark and Sweep) został oznaczony jako przestarzały w Javie 9 ( https://openjdk.java.net/jeps/291 ), a w Javie 14 został usunięty ( https://openjdk.java.net/jeps/363 ). G1 GC w najnowszych wersjach Javy jest na tyle dopracowany, że może zastąpić z powodzeniem CMSa.

@Wibowit może źle się wyraziłem. Nie chodziło mi konkretnie o nazwę GC w Javie tylko o odśmiecanie przez zaznacznie używanych obszarów pamięci(używanie rootów GC) i dealokacje pamieci juz niedostępnej.

Zliczanie referencji w C++ w środowisku wielowątkowym jest kosztowne, a obecnie nawet dość błędogenne.

W sumie to wydaje się bardzo logiczne - problemem jest sensowne współdzielenie referencji przez wątki i aktualizacja licznika.

3

Nie chodziło mi konkretnie o nazwę GC w Javie tylko o odśmiecanie przez zaznacznie używanych obszarów pamięci(używanie rootów GC) i dealokacje pamieci juz niedostępnej.

Tracing GC. Mark and Sweep jest dużo bardziej szczegółowym pojęciem określającym pewien algorytm.

Co do zliczania referencji to raczej nie stosuje się go, jeżeli infrastruktura pozwala na tracing. Największym problem są wspomniane cykle i duży koszt tworzenia, manipulacji licznikiem i niszczenia. W takiej Javie koszt alokacji jest praktycznie zerowy, sama dealokacja też jest darmowa, jeżeli obiekt szybko ginie.

Kiedy zliczanie referencji ma sens:

  • nie da się użyć tracingu (C++, Rust). Wysoko wydajnościowy tracing wymaga dużo założeń np. możliwość przeniesienia pamięci, albo określona struktura sterty w celu ułatwienia skanowania. W C++ istnieją algorytmy wykorzystujące tracing np. https://chromium.googlesource[...]m/heap/BlinkGCAPIReference.md . Inna sprawa, że użycie jest niewygodne i tutaj brak wymaganego runtime sprawia, że zliczanie referencji jest po prostu wygodniejsze
  • krótsze pauzy. W dzisiejszych czasach mamy takie algorytmy jak ZGC, ale jakieś 10 lat temu sprawa wyglądała inaczej. Co ciekawe ZGC działa trochę analogicznie jak zliczanie referencji tj. dużo pracy wykonywanej jest w czasie używania danej zmiennej w porównaniu do innych algorytmów, gdzie wszystko dzieje się na boku.
  • deterministyczna kolejność niszczenia obiektów, da się bez tego żyć, ale to na pewno jakiś plus
  • możliwość dowolnego przedłużenia czasu życia pamięci. Ma to sens, jeżeli nasza aplikacja działa przykładowo w trybie request response. W tym wypadku możemy przedłużyć czas życia jakiegoś dużego obiektu do momentu, kiedy zwróciliśmy już response wykonując dealokację, gdy nikt na nas nie czeka
2

Zliczanie referencji też może skutkować długimi pauzami - czasami usunięcie korzenia jakiegoś grafu wyzwala kaskadowo setki tysięcy małych delete i bywa to odczuwalne. Jest natomiast detetministyczne.

Uzywałem RC w kodzie C++ - koniec lat 90-tych. Era fascynacji programowaniem obiektowym, wzorcami i UMLem. W takim - imperatywnym - kodzie walka z cyklicznymi referencjami nie była jakimś specjalnym, ani uciążliwym wyzwaniem.

Nie wyobrażam sobie natomiast takiej walki we wspołczesnym, choćby lekko funkcyjnym kodzie, ale nie próbowałem - więc może tylko mi się zdaje.

Bardzo jest dla mnie dziwna decyzja o użyciu RC w Swifcie. Najgorsze, że to niestety w środowisku Apple, więc nijak nie ufam opowieściom, że nie stanowi to żadnego problemu - dla fanboyów nawet objective C był zupełnie spoko językiem.

EDIT:
Tu jeszcze taka uwaga, że niemutowalność nie chroni przed cyklami. Łatwo sobie sprawdzisz w Kotlinie.
A tu haskell

data A = A B
data B = B A

c::A
c = A ( B c)
3

W Pro .NET Memory Management, jest wprawdzie krótki, ale teroretyczny rodział o zliczaniu referencji i róznych jego odmianach, strona 42 "Reference Counting", polecam lekturę, a tutaj podsumowanie z tego rodziału:

Advantages
• Deterministic deallocation moment - we know that deallocation will
happen when an object’s reference counter will drop to zero. Therefore,
as long as it is no longer needed, the memory will be reclaimed.
• Less memory constraint - as memory is reclaimed as fast as objects
are no longer used, there is no overhead of memory consumed by the
objects waiting to be collected.
• Can be implemented without any support from the runtime.

Disadvantages:
• Such a naive implementation as at Listing 1-8 introduces very big
overhead on Mutator.
• Multithreading operations on reference counters require well-thought
synchronization, which can introduce additional overhead.
• Without any additional enhancements, circular references cannot be
reclaimed.

3

W takiej Javie koszt alokacji jest praktycznie zerowy

Jako praktyk Javy zostałem wywołany do tablicy... no i nie mogę się z tymi twierdzeniami zgodzić.

Mit "praktycznie zerowego kosztu alokacji" wziął się stąd, że faktycznie SAMA alokacja jest banalnie prosta - "sprawdź, czy jest wystarczająco dużo miejsca i przesuń wskaźnik do przodu". Wygląda to faktycznie nieco taniej niż "znajdź odpowiedni kawałek wolnej pamięci na free-list" i faktycznie w szczególnych przypadkach (zwłaszcza w mikrobenchmarkach) bywa tańsze.

Jednak prawdziwy koszt tworzenia obiektu następuje chwilę później, jest dość nieoczywisty i czasami zaskakująco duży:

  1. Alokuje się po to, aby tej pamięci użyć. W przypadku scalających GC, przy alokacji dostajemy zawsze pamięć, która nie była dotykana co najmniej od poprzedniego cyklu sprzątania. Oznacza to, że ta pamięć na pewno nie jest w cache L1, L2, a może nawet w L3. Wskaźnik na nową pamięć dostajemy praktycznie natychmiast, ale robimy pierwszy dostęp do niej i mamy na dzień dobry cache-miss. I tak z kilku cykli CPU robi się co najmniej kilkadziesiąt. Dodatkowo jako bonus - wypychamy inne dane, które były wcześniej z cache.

  2. Każda kolejna alokacja przybliża moment, kiedy TLAB się skończy i trzeba będzie zaalokować nowy z globalnej puli. A te w globalnej puli też się skończą i wtedy (w uproszczeniu) włącza sie GC. Im więcej alokujesz, tym częściej działa GC. Koszt GC należy doliczyć do kosztów alokacji.

sama dealokacja też jest darmowa, jeżeli obiekt szybko ginie.

To "jeśli" to w praktyce niestety duży problem. Najlepsza metoda na zabicie GC to zaimplementowanie struktur typu cache - mnóstwo obiektów o średnim i długim czasie życia, ale nie permanentnym.

Co do zliczania referencji, to ono jest drogie jako uniwersalna metoda działająca w runtime, bez wsparcia kompilatora / języka. Natomiast potrafi być zaskakująco tanie, jeśli język wspiera coś takiego jak przesuwanie lub pożyczanie obiektów - w takiej sytuacji po pierwsze prawie nigdy nie potrzebujesz zliczania referencji, a tam gdzie potrzebujesz, aktualizacje liczników referencji mogą być bardzo rzadkie. Aktualizacja licznika to jeden cykl CPU, więc dopóki nie robi się tego tysiącami, to jest niezauważalne.

1

Alokuje się po to, aby tej pamięci użyć. W przypadku scalających GC, przy alokacji dostajemy zawsze pamięć, która nie była dotykana co najmniej od poprzedniego cyklu sprzątania. Oznacza to, że ta pamięć na pewno nie jest w cache L1, L2, a może nawet w L3. Wskaźnik na nową pamięć dostajemy praktycznie natychmiast, ale robimy pierwszy dostęp do niej i mamy na dzień dobry cache-miss. I tak z kilku cykli CPU robi się co najmniej kilkadziesiąt. Dodatkowo jako bonus - wypychamy inne dane, które były wcześniej z cache.

Liniowa alokacja to raczej najprostszy scenariusz dla hardware prefetching znanego od lat 90-tych: https://en.wikipedia.org/wiki/Cache_prefetching
Równie dobrze można powiedzieć, że jeśli często pchasz kopie danych na stos (zamiast wskaźników do nich) i ten tak ci rośnie że sumarycznie stosy zajmują kilka razy więcej pamięci niż cache to ogólnie tracisz na całym procederze. Czy na pewno?
Jeśli w danym momencie używasz dużo małych obiektów rozsianych po stercie to cache (mające pewną ziarnistość znacznie większą niż bajt, np 64 bajty) będzie działało mniej efektywnie niż gdyby te małe obiekty były obok siebie.
Możliwych scenariuszy jest wiele, w każdym przypadku trzeba sobie zrobić rachunek zysków i kosztów.

Aktualizacja licznika to jeden cykl CPU, więc dopóki nie robi się tego tysiącami, to jest niezauważalne.

Jeśli licznik jest atomic to na pewno nie trwa jeden cykl.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0