Zliczanie referencji vs Mark and Swap

Odpowiedz Nowy wątek
2020-07-04 22:04

Rejestracja: 5 lat temu

Ostatnio: 24 minuty temu

Lokalizacja: Warszawa

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


Nie pomagam przez PM. Pytania zadaje się na forum.

Pozostało 580 znaków

2020-07-04 22:16

Rejestracja: 12 lat temu

Ostatnio: 59 minut temu

0

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


IT mikromenadżer

Pozostało 580 znaków

2020-07-04 22:42

Rejestracja: 13 lat temu

Ostatnio: 57 minut temu

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.

Pozostało 580 znaków

2020-07-04 22:45

Rejestracja: 15 lat temu

Ostatnio: 2 godziny temu

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ż.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
edytowany 2x, ostatnio: Wibowit, 2020-07-04 22:49

Pozostało 580 znaków

2020-07-04 22:55

Rejestracja: 5 lat temu

Ostatnio: 24 minuty temu

Lokalizacja: Warszawa

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.


Nie pomagam przez PM. Pytania zadaje się na forum.

Pozostało 580 znaków

2020-07-05 04:15

Rejestracja: 2 lata temu

Ostatnio: 1 godzina temu

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
edytowany 1x, ostatnio: slsy, 2020-07-05 04:19
Z odrobiną pracy w Ruscie można mieć tracing GC. Ergonomicznie to też nie wygląda najgorzej. - hauleth 2020-07-06 13:07
Faktycznie, makra czynią cuda - slsy 2020-07-06 16:38

Pozostało 580 znaków

2020-07-05 08:09

Rejestracja: 3 lata temu

Ostatnio: 27 minut temu

Lokalizacja: U krasnoludów - pod górą

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)

jeden i pół terabajta powinno wystarczyć każdemu
edytowany 5x, ostatnio: jarekr000000, 2020-07-05 09:12
Pokaż pozostałe 8 komentarzy
To swoją drogą, ja tu rozważam naiwny RC. Aczkolwiek wydaje mi się, że jak już możemy na przykład zrobić listę podwójnie wiązaną, to pewnie dałoby się tak połączyć kilka list pojedynczo i podwójnie wiązanych, że kompilator nie wyłapałby cyklu (na pewno da się to jakoś zredukować z problemu stopu) i wtedy nawet słabe referencje nie pomogą. - Afish 2020-07-06 17:07
@Afish: kilka razy chciałem coś sprawdzić w gołych bajtach na GHC (głównie przy porównianiu z eta-lang), ale po prostu nie mam tyle życia. Lazy, thunki i cała ta machineria powoduje, że jestem bezradny - są różne narzędzia do debugu... ale nie mam tyle życia. Może to jest (w końcu) ten język, że koncepcja w bajtach nie działa i trzeba sobie dać spokój. - jarekr000000 2020-07-06 23:07
@jarekr000000: Haskellowcy często mówią, że nie potrzebują debuggera, profilera i innych takich, ale nie chce mi się w to wierzyć. Jak tylko pisze się coś większego, to trzeba mieć możliwość wglądu do aplikacji, a gadanie o typach, testach, dowodach i "jak kod w Haskellu się skompiluje, to będzie działał poprawnie" brzmi jak bajki. - Afish 2020-07-07 00:37
@Afish: brzmi jak bajki, ale SQL (zapytań) pewnie też nie debugujesz, co najwyżej sprawdzasz plan. Jakoś działa. - jarekr000000 2020-07-07 06:33
To jest słuszna uwaga, przy czym jednocześnie też sprawdzam, jak działają locki i poziomy izolacji. Jednocześnie zgodzę się, że nie każdy tego potrzebuje, wielu ludzi nigdy nie odpaliło profilera i żyją, a gdzie tam mówić o zrzutach pamięci. - Afish 2020-07-07 07:00

Pozostało 580 znaków

2020-07-06 15:45

Rejestracja: 17 lat temu

Ostatnio: 2 godziny temu

Lokalizacja: Kraków

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.


It's easy to hate code you didn't write, without an understanding of the context in which it was written.

Pozostało 580 znaków

2020-07-20 13:14
Moderator

Rejestracja: 16 lat temu

Ostatnio: 7 godzin temu

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.

edytowany 1x, ostatnio: Krolik, 2020-07-20 13:16

Pozostało 580 znaków

2020-07-20 13:37

Rejestracja: 15 lat temu

Ostatnio: 2 godziny temu

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.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
edytowany 1x, ostatnio: Wibowit, 2020-07-20 13:38

Pozostało 580 znaków

2020-07-20 15:12

Rejestracja: 2 lata temu

Ostatnio: 1 godzina temu

1
Krolik napisał(a):
  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.

IMO to mały problem. Jeżeli nasz kod opiera się głównie na alokacjach, czyli programujemy typowo Javowo tworząc co linię nowy obiekt na heapie to czas dostępu do odpowiedniego poziomu cache i tak nie ma większego znaczenia, ponieważ sam koszt alokacji i często związane kopiowanie/zerowanie jest samo w sobie dużym narzutem. Użyte przeze mnie twierdzenie "darmowa" powinno brzmieć raczej: "dużo taniej niż jakakolwiek inna metoda przy zachowaniu tego samego stylu programowania"

Krolik napisał(a):

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.

Analizująć perf raporty programów napisanych w C++ używających mocno zliczania referencji byłem mocno zdziwiony, że sam koszt użycia licznika jest dość mały. Dużo większym problemem jest samo zwalnianie pamięci poprzez komunikację z alokatorem (nawet jak się wybrało jakiś porządny typu jemalloc czy tcmalloc) i przechodzenie przez drzewo obiektów w celu wywołania destruktorów. Oba te problemy nie występują w javowym modelu pamięci.

Pozostało 580 znaków

Odpowiedz

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