Zliczanie referencji vs Mark and Swap

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.

0

Co do cachy, w Javie (I nie tylko) jest coś takiego jak WeakReference, SoftReference i offheap więc to jest rozwiązanie pewnych problemów o których pisałeś @Krolik

2

Liniowa alokacja to raczej najprostszy scenariusz dla hardware prefetching znanego od lat 90-tych

Prefetching może zmniejszyć opóźnienie, ale nie zmniejsza całkowitej ilości pracy do wykonania.
Poza tym prefetching działa tylko w specyficznych przypadkach jak masz faktycznie uporządkowaną sekwencję dostępów (np. przeglądanie wektora).
W przypadku alokacji wcale tak nie musi być, bo pomiędzy alokacjami możesz mieć mnóstwo innych dostępów i wtedy to już z punktu widzenia procesora nie wygląda na sekwencyjny dostęp, a całkiem przypadkowy.

w Javie (I nie tylko) jest coś takiego jak WeakReference, SoftReference i offheap więc to jest rozwiązanie pewnych problemów o których pisałeś

WeakReference i SoftReference raczej rozwiązują inne problemy niż te, o których pisałem.
Offheap faktycznie umożliwia implementację długożyjących cache poza GC - ale próbowałeś? Ręczne rzeźbienie przetwarzania stringów w C z makrami to chyba mniejszy masochizm niż offheap w Javie. Mamy implementację cache off-heap w swoim produkcie. Debugowanie tego to bardzo fajna zabawa. Polecam.

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.

Żeby przejście przez wszystkie destruktory i zwolnienie pamięci zajęło więcej niż przeciętne GC w Javie (nawet takie jak G1), które powiedzmy trwa ok 100 ms, to musiałbyś zwalniać hurtowo miliony obiektów. Poza tym takie zwolnienie i tak nie pauzuje innych wątków - pauzuje jeden wątek, ten zwalniający, natomiast pozostałe np. 47 rdzeni serwera dalej może wykonywać swoją pracę. A nawet w sytuacji gdyby to było problemem - jest banalne wyjście - zwalnianie w tle albo podzielenie zwalniania na paczki. Czyli jeden prosty do rozwiązania i niezbyt poważny problem (dealokacja) C++ został zastąpiony przez Javę innym, znacznie znacznie poważniejszym i znacznie trudniejszym do rozwiązania (pauzy GC).

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

Po pierwsze: A dlaczego miałby być atomic? Przy odpowiednim wsparciu kompilatora wiadomo, które liczniki nigdy nie wyłażą poza jeden wątek, więc te liczniki nie muszą być atomic. W C++ shared_ptr jest atomic, ale już np. w Rust są dwa rodzaje liczników. Atomowy licznik potrzebujesz tylko jeśli zwalniasz obiekt w innym wątku niż go utworzyłeś.
Po drugie: jeden cykl to może nie, ale w optymistycznym przypadku LOCK ADD zajmuje mniej niż 10 cykli (dokładnie 8 uops na Coffee Lake) , a w tym czasie CPU może robić wiele innych rzeczy.

0

Offheap faktycznie umożliwia implementację >długożyjących cache poza GC - ale próbowałeś?

A to nie są jakieś gotowe biblioteki od tego? Zresztą, słyszałem że ponoć GC potrafi się dostosować więc można też użyć innej instancji JVMa do trzymania cachy.

A co do wspieranych przez kompilator liczników referencji, jestem ciekaw czemu ich nie ma w C++ (chyba że sie mylę)

1

Atomowy licznik potrzebujesz tylko jeśli zwalniasz obiekt w innym wątku niż go utworzyłeś.

Raczej jak używam (nie tylko alokuję i dealokuję obiekt, ale też np klonuję wskaźnik) w więcej niż jednym wątku naraz, bo bez atomica licznik się rozjedzie. Oczywiście można kombinować z konwertowaniem między wskaźnikami zliczanymi i nie, ale to chyba sztuka dla sztuki.

Znalazłem benchmark dotyczący alokacji + prefetchingu w Javie: https://www.opsian.com/blog/jvms-allocateprefetch-options/
Nawet w tak patologicznym przypadku jak sama alokacja obiektów prefetching daje zaledwie dwadzieścia kilka % zysku. Gdyby dorzucić logikę biznesową to pewnie różnica znacznie by się zmniejszyła:

Putting the results in context
It’s worth interpreting these benchmarks and their results. For starters, these are microbenchmarks - they are testing one specific operation and it’s highly unlikely you will see a performance impact of the magnitude these tests show. To put some of the allocation numbers in context the CacheSizedObjmicrobenchmark with allocation prefetching enabled is allocating 8.5 gigabytes a second and essentially nothing else. That it is bottlenecked by the store buffer is unsurprising given that stores are all it’s doing. In a bigger application there’s a good chance that some operations will actually be performed on the allocated objects, so giving more time for the store buffer to drain.

Co do:

Po drugie: jeden cykl to może nie, ale w optymistycznym przypadku LOCK ADD zajmuje mniej niż 10 cykli (dokładnie 8 uops na Coffee Lake) , a w tym czasie CPU może robić wiele innych rzeczy.

To chyba jednak nie. Na https://stackoverflow.com/a/39396999 jest napisane:

Note that the lock prefix also turns an instruction into a full memory barrier (like MFENCE), stopping all run-time reordering and thus giving sequential consistency.

Hmm, full memory barrier? Samo LFENCE może już zabić wydajność: https://www.phoronix.com/scan[...]tem=lvi-attack-perf&num=1
Obstawiam, że optymalizacje kompilatora (czyli redukowanie zmian atomowego licznika za wszelką cenę) są kluczowe do utrzymania sensownej wydajności. Pytanie tylko ile jest przypadków w których zawodzą?

Najlepsza metoda na zabicie GC to zaimplementowanie struktur typu cache - mnóstwo obiektów o średnim i długim czasie życia, ale nie permanentnym.

Na pewno? Card tables w generacyjnych GC powinny rozwiązywać ten problem do pewnego stopnia: https://stackoverflow.com/que[...]able-and-writer-barrier-works
Jeśli odśmiecanie nowych regionów wystarcza (w sensie zwalnia wystarczającą ilość pamięci) to starych nie trzeba w ogóle wczytywać podczas cyklu GC.

2

Raczej jak używam (nie tylko alokuję i dealokuję obiekt, ale też np klonuję wskaźnik) w więcej niż jednym wątku naraz, bo bez atomica licznik się rozjedzie. Oczywiście można kombinować z konwertowaniem między wskaźnikami zliczanymi i nie, ale to chyba sztuka dla sztuki.

W większości przypadków możesz pożyczyć albo przesunąć wskaźnik bez zmiany liczby referencji.
Pożyczenie wskaźnika (przekazanie przez referencję) nie modyfikuje liczby referencji.
Przekazanie wskaźnika do nowego właściciela (np. do funkcji) i wyrzucenie oryginału też nie zmienia liczby referencji.
Klonowanie jest potrzebne tylko jak zmienia się liczba właścicieli danych - tzn. pojawia się nowy właściciel danych wskazywanych przez wskaźnik, ale w praktyce to dość rzadkie sytuacje. Zwykle koszt utworzenia tego nowego właściciela (alokacja) jest większy niż skopiowanie wskaźnika.

Samo LFENCE może już zabić wydajność

Między "może" a "musi" jest duża różnica. Akurat LFENCE i SFENCE na x86 to praktycznie noop, bo wszystkie dostępy są i tak koherentne i uporządkowane. Koszt występuje gdy linia cache jest faktycznie współdzielona między rdzeniami (i do tego nie musisz mieć wcale bariery - przy zwykłych aktualizacjach współdzielonego licznika też będziesz mieć duże opóźnienie). Koszt jest oczywiście niezerowy, bo atomic wyłącza pewne optymalizacje komplatora (np. out-of--order) i wymusza przesłania (nie można tak sobie licznika w rejestrze trzymać), ale dopóki dwa wątki nie zabijają się o wspólny licznik i nie robią milionów aktualizacji na sekundę, nie zauważysz narzutu.

0

W większości przypadków możesz pożyczyć albo przesunąć wskaźnik bez zmiany liczby referencji.
Pożyczenie wskaźnika (przekazanie przez referencję) nie modyfikuje liczby referencji.
Przekazanie wskaźnika do nowego właściciela (np. do funkcji) i wyrzucenie oryginału też nie zmienia liczby referencji.
Klonowanie jest potrzebne tylko jak zmienia się liczba właścicieli danych - tzn. pojawia się nowy właściciel danych wskazywanych przez wskaźnik, ale w praktyce to dość rzadkie sytuacje. Zwykle koszt utworzenia tego nowego właściciela (alokacja) jest większy niż skopiowanie wskaźnika.

Wspaniała gimnastyka tylko po to, by ułatwić kompilatorowi optymalizacje. Jak dla mnie to rozdwojenie typu pożyczanie kontra przesuwanie jest podobne do rozdwojenia sync vs async w oryginalnym artykule "what color is your function?" Rust nie dość, że koloruje funkcje względem sync/async to jeszcze dokłada kolory borrow/move. Dla prostych przykładów taka gimnastyka pewnie jest względnie prosta, ale dla bardziej skomplikowanych obstawiam, że może być nawet frustrująca. Nie pisałem na tyle w Ruście żeby mieć jakąś solidną opinię, więc nie będę ciągnął tematu. Ze swojej strony czekam na włączenie https://openjdk.java.net/projects/loom/ do głównej wersji Javy. Wtedy nie będzie ani rozjazdu sync/async ani borrow/move (w Golangu już tak jest, ale mnie do niego nie ciągnie). Sama wygoda :)

Między "może" a "musi" jest duża różnica. Akurat LFENCE i SFENCE na x86 to praktycznie noop, bo wszystkie dostępy są i tak koherentne i uporządkowane. Koszt występuje gdy linia cache jest faktycznie współdzielona między rdzeniami (i do tego nie musisz mieć wcale bariery - przy zwykłych aktualizacjach współdzielonego licznika też będziesz mieć duże opóźnienie). Koszt jest oczywiście niezerowy, bo atomic wyłącza pewne optymalizacje komplatora (np. out-of--order) i wymusza przesłania (nie można tak sobie licznika w rejestrze trzymać), ale dopóki dwa wątki nie zabijają się o wspólny licznik i nie robią milionów aktualizacji na sekundę, nie zauważysz narzutu.

W jednowątkowych zadaniach bez żadnego współdzielenia danych między rdzeniami też jest katastrofa wydajnościowa: https://www.phoronix.com/scan[...]tem=lvi-attack-perf&num=5 (FLAC audio encoding, ZTCP to jest jednowątkowy test) Noopem bym tego nie nazwał.

3

Wspaniała gimnastyka tylko po to, by ułatwić kompilatorowi optymalizacje

Ale jaka gimnastyka? Dodanie & przed typem w sygnaturze metody aby uniknąć kopiowania to gimnastyka?
Poza tym patrzysz z perspektywy C++. Z perspektywy Rusta nie jest to żadna gimnastyka, tylko normalny sposób pracy z obiektami każdego typu (Rust jest domyślnie pass-by-move, a nie pass-by-copy jak C++). Nie da się niechcący skopiować wskaźnika. Aby skopiować wskaźnik, musisz się własnie nagimnastykować, tj. użyć na nim .clone().

A rozjazd między borrow/move jest potrzebny, bo semantycznie jest olbrzymia różnica. Taki sam rozjazd masz w Javie (i właściwie każdym języku) tylko jedyny sposób na udokumentowanie go to komentarze w kodzie. Przykład: Masz w Javie funkcję biorącą obiekt typu InputStream. Kto zamyka strumień? I co jak w JavaDoc nie ma o tym ani słowa?

Card tables w generacyjnych GC powinny rozwiązywać ten problem do pewnego stopnia: https://stackoverflow.com/que[...]able-and-writer-barrier-works

Dla każdego GC można znaleźć takie zadanie, z którym poradzi sobie słabo:
https://ionutbalosin.com/2019[...]tors-benchmarks-report-19-12/

W jednowątkowych zadaniach bez żadnego współdzielenia danych między rdzeniami też jest katastrofa wydajnościowa: https://www.phoronix.com/scan[...]tem=lvi-attack-perf&num=5 (FLAC audio encoding, ZTCP to jest jednowątkowy test) Noopem bym tego nie nazwał.

Tylko że w tej mitygacji zdaje się że dodawany jest LFENCE po każdym przesłaniu danych z pamięci. To trochę częściej niż przy okazjonalnej aktualizacji licznika referencji.
Zauważ że nie we wszystkich benchmarkach zastosowanie LFENCE spowodowało tak drastyczny spadek wydajności - w wielu sytuacjach jest niezauważalne.

2

Ale jaka gimnastyka? Dodanie & przed typem w sygnaturze metody aby uniknąć kopiowania to gimnastyka?
Poza tym patrzysz z perspektywy C++. Z perspektywy Rusta nie jest to żadna gimnastyka, tylko normalny sposób pracy z obiektami każdego typu (Rust jest domyślnie pass-by-move, a nie pass-by-copy jak C++). Nie da się niechcący skopiować wskaźnika. Aby skopiować wskaźnik, musisz się własnie nagimnastykować, tj. użyć na nim .clone().

Gimnastyka polega na wyborze między przenoszeniem, pożyczaniem mut i nie mut (z zachowaniem zgodności lifetime'ów). Zmiana czegoś takiego w jednym miejscu może skutkować kaskadowymi zmianami w wielu innych miejscach. Inaczej rzecz biorąc: wybieranie między tymi trybami jest dodatkowym problemem podczas opracowywania architektury kodu. Ja bym jednak wolał się skupić na innych rzeczach. A równie dobrze można powiedzieć, że checked exceptions nie są problemem, bo co to jest jedno throws na metodę?

A rozjazd między borrow/move jest potrzebny, bo semantycznie jest olbrzymia różnica. Taki sam rozjazd masz w Javie (i właściwie każdym języku) tylko jedyny sposób na udokumentowanie go to komentarze w kodzie. Przykład: Masz w Javie funkcję biorącą obiekt typu InputStream. Kto zamyka strumień? I co jak w JavaDoc nie ma o tym ani słowa?

W typowym (statystycznie) kodzie zamyka się mniej więcej w tym samym miejscu co otwiera, np używając try-with-resources mamy otwieranie i zamykanie w jednej linijce. Rzadko kiedy widzę problemy (w sensie manifestujące się kiepską wydajnością czy błędami w runtime) z wyciekającymi zasobami.

Dla każdego GC można znaleźć takie zadanie, z którym poradzi sobie słabo:

Analogicznie: dla każdego alokatora można znaleźć zadanie, z którym poradzi sobie słabo. Już tu kiedyś robiłem testy alokatorów dla testu binarytrees z Benchmarks Game i jemalloc wypadał znacznie gorzej do tcmalloc. Alokatorów jest na pęczki i każdy pokazuje, że jest znacznie lepszy niż inne.

Tracing GC to mimo wszystko ciągle mocno zmieniający się temat. Java przełączyła się (w sensie domyślnego wyboru) na (dalej dynamicznie się rozwijający) G1 dopiero w 2017 roku: http://openjdk.java.net/jeps/248 Niskopauzowe GC przechodzą ze statusu experimental do production dopiero w nadchodzącej Javie 15: https://openjdk.java.net/jeps/377 https://openjdk.java.net/jeps/379 Sporo jeszcze testów przed nimi. Na razie koncentrują się na jakichś realnych benchmarkach typu SPECjbb, a nie mało realistycznych (w kontekście zastosowań biznesowych) Benchmarks Game.

Żeby przejście przez wszystkie destruktory i zwolnienie pamięci zajęło więcej niż przeciętne GC w Javie (nawet takie jak G1), które powiedzmy trwa ok 100 ms, to musiałbyś zwalniać hurtowo miliony obiektów. Poza tym takie zwolnienie i tak nie pauzuje innych wątków - pauzuje jeden wątek, ten zwalniający, natomiast pozostałe np. 47 rdzeni serwera dalej może wykonywać swoją pracę. A nawet w sytuacji gdyby to było problemem - jest banalne wyjście - zwalnianie w tle albo podzielenie zwalniania na paczki. Czyli jeden prosty do rozwiązania i niezbyt poważny problem (dealokacja) C++ został zastąpiony przez Javę innym, znacznie znacznie poważniejszym i znacznie trudniejszym do rozwiązania (pauzy GC).

Shenandoah GC ma mechanizm pacing: https://wiki.openjdk.java.net[...]andoah/Main#Main-FailureModes (szukaj: -XX:+ShenandoahPacing), który spowalnia wątek, który alokuje dużo, a reszta wątków (które alokują mało) może w tym czasie pracować z pełną prędkością.

Tylko że w tej mitygacji zdaje się że dodawany jest LFENCE po każdym przesłaniu danych z pamięci. To trochę częściej niż przy okazjonalnej aktualizacji licznika referencji.
Zauważ że nie we wszystkich benchmarkach zastosowanie LFENCE spowodowało tak drastyczny spadek wydajności - w wielu sytuacjach jest niezauważalne.

LFENCE after load ma największy wpływ na wydajność, prawie cały spadek jest przez to spowodowany:
lfence.png
Tam gdzie wpływ był niewielki (Redis + memcached) prawdopodobnie IPC było bardzo niskie ze względu na opóźnienia na odczycie z pamięci (bo losowy dostęp do pamięci to główna czynność w tych programach), więc dodatkowe synchronizacje w potokach wykonawczych niewiele zmieniły. Ty napisałeś, że LOCK (silniejszy niż LFENCE) może być wykonywany razem z innymi instrukcjami (tak jak się to typowo dzieje w out-of-order CPU), ale nie jest to prawda i dobitnie to widać na wykresach.

2

Gimnastyka polega na wyborze między przenoszeniem, pożyczaniem mut i nie mut (z zachowaniem zgodności lifetime'ów).

Przesadzasz. W większości przypadków już "na dzień dobry" wiesz co potrzebujesz. Ogólne zasady są:

  • referencja kiedy się da, o ile wiesz, że typ jest Copy
  • mutowalna referencja jest dość oczywista kiedy
  • przenoszenie jeśli ty chcesz być właścicielem (doh) lub jeśli jest to typ Copy

Nie jest to trudne i bardzo szybko "wchodzi w krew", zwłaszcza, że kompilator Ciebie prowadzi.

Zmiana czegoś takiego w jednym miejscu może skutkować kaskadowymi zmianami w wielu innych miejscach.

Ale raczej tylko w obrębie samej funkcji lub ewentualnie miejsc gdzie tę funkcję wywołujesz. Ale jak wyżej, po chwili przyzwyczajenia, raczej rzadko kiedy jest to problemem.

Jak dla mnie to rozdwojenie typu pożyczanie kontra przesuwanie jest podobne do rozdwojenia sync vs async w oryginalnym artykule "what color is your function?" Rust nie dość, że koloruje funkcje względem sync/async to jeszcze dokłada kolory borrow/move.

No właśnie nie, bo zarówno funkcje sync/async jak i borrow/move są właściwościami typów, a nie funkcji. W Ruście zapis:

async fn foo() -> Bar { … }

Jest praktycznie równoważny zapisowi:

fn foo() -> impl Future<Bar> { … }

Dodatkowo w miejscu gdzie wywołujesz funkcję ewidentnie widzisz czy będzie to borrow czy move:

  • foo(val) - move
  • foo(&val) - borrow
  • foo(&mut val) - mut borrow

Więc po prawdzie nic nie jest przed Tobą ukryte i jeśli chcesz, to możesz "ręcznie" kontrolować wywołanie wszystkiego.

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