Przydział sterty Java Szybszy niż C ++

Już opublikowałem to pytanie na SO i było w porządku. Niestety został on zamknięty (wystarczy jeden głos, aby ponownie otworzyć), ale ktoś zasugerował, że opublikuję go tutaj, ponieważ jest lepiej dopasowany, więc poniższy tekst jest dosłownie kopią pasty do pytania

Czytałem komentarze do tej odpowiedzi i widziałem ten cytat.

Tworzenie instancji obiektów i funkcje obiektowe są niezwykle szybkie w użyciu (w wielu przypadkach szybsze niż C ++), ponieważ zostały zaprojektowane od samego początku. i Kolekcje są szybkie. Standardowa Java wyprzedza standardowy C / C ++ w tym obszarze, nawet w przypadku najbardziej zoptymalizowanego kodu C.

Jeden użytkownik (z bardzo wysokim przedstawicielem, który mogę dodać) odważnie bronił tego twierdzenia, stwierdzając to

1. alokacja sterty w java jest lepsza niż w C ++

2. i dodał to oświadczenie, broniąc kolekcji w java

   Kolekcje Java są szybkie w porównaniu do kolekcji C ++, głównie ze względu na inny podsystem pamięci.

Więc moje pytanie brzmi: czy którekolwiek z tych stwierdzeń może być prawdziwe, a jeśli tak, to dlaczego alokacja sterty Java jest o wiele szybsza.

To interesujące pytanie, a odpowiedź jest złożona.

Ogólnie rzecz biorąc, uważam za słuszne powiedzieć, że moduł śmieciowy JVM jest bardzo dobrze zaprojektowany i niezwykle wydajny. Jest to prawdopodobnie najlepszy system zarządzania pamięcią ogólnego przeznaczenia .

C ++ może pokonać JVM GC dzięki specjalistycznym przydziałom pamięci zaprojektowanym do określonych celów. Przykładami mogą być:

• Dzielniki pamięci na ramkę, które okresowo czyszczą cały obszar pamięci. Są one często używane w grach C ++, na przykład, gdy tymczasowy obszar pamięci jest wykorzystywany raz na klatkę i natychmiast odrzucany.
• Niestandardowe alokatory zarządzające pulą obiektów o stałej wielkości
• Alokacja na podstawie stosu (choć należy pamiętać, że JVM robi to również w różnych okolicznościach, np. Poprzez analizę ucieczki )

Specjalistyczne alokatory pamięci są oczywiście z definicji ograniczone. Zwykle mają ograniczenia dotyczące cyklu życia obiektu i / lub ograniczenia dotyczące typu obiektu, którym można zarządzać. Odśmiecanie jest znacznie bardziej elastyczne.

Odśmiecanie daje również kilka znaczących korzyści z perspektywy wydajności:

• Tworzenie instancji obiektów jest rzeczywiście niezwykle szybkie. Ze względu na sposób, w jaki nowe obiekty są przydzielane sekwencyjnie w pamięci, często wymaga niewiele więcej niż jednego wskaźnika, co z pewnością jest szybsze niż typowe algorytmy alokacji sterty C ++.
• Pozwala to uniknąć kosztów zarządzania cyklem życia - np. Zliczanie referencji (czasem stosowane jako alternatywa dla GC) jest wyjątkowo słabe z punktu widzenia wydajności, ponieważ częste zwiększanie i zmniejszanie liczby referencji powoduje znaczne zwiększenie wydajności (zwykle znacznie więcej niż GC) .
• Jeśli używasz niezmiennych obiektów, możesz skorzystać z udostępniania strukturalnego, aby zaoszczędzić pamięć i poprawić wydajność pamięci podręcznej. Jest to często używane przez języki funkcjonalne JVM, takie jak Scala i Clojure. Bez GC jest to bardzo trudne, ponieważ bardzo trudno jest zarządzać czasem życia współdzielonych obiektów. Jeśli wierzysz (tak jak ja), że niezmienność i współdzielenie strukturalne są kluczem do budowania dużych współbieżnych aplikacji, to jest to prawdopodobnie największa zaleta wydajności GC.
• Można uniknąć kopiowania, jeśli wszystkie typy obiektów i odpowiadające im cykle życia są zarządzane przez ten sam system usuwania śmieci. Porównaj z C ++, w którym często trzeba wykonywać pełne kopie danych, ponieważ miejsce docelowe wymaga innego podejścia do zarządzania pamięcią lub ma inny cykl życia obiektu.

Java GC ma jedną poważną wadę: ponieważ praca polegająca na zbieraniu śmieci jest odraczana i wykonywana w okresach czasu, powoduje sporadyczne przerwy w zbieraniu śmieci, które mogą mieć wpływ na opóźnienia. Zwykle nie stanowi to problemu dla typowych aplikacji, ale może wykluczyć Javę w sytuacjach, w których wymagany jest trudny czas rzeczywisty (np. Sterowanie robotem). Miękki czas rzeczywisty (np. Gry, multimedia) jest zazwyczaj OK.

To nie jest naukowe twierdzenie. Po prostu daję trochę do myślenia na ten temat.

Jedna wizualna analogia jest następująca: otrzymujesz mieszkanie (lokal mieszkalny) z wykładziną dywanową. Dywan jest brudny. Jaki jest najszybszy sposób (pod względem godzin), aby podłoga w mieszkaniu lśniła czystością?

Odpowiedź: wystarczy zwinąć stary dywan; wyrzucić; i rozwinąć nowy dywan.

Czego tu zaniedbujemy?

• Koszt wyprowadzenia istniejących rzeczy osobistych, a następnie przeprowadzki.
  • Jest to znane jako „zatrzymanie świata” kosztu zbierania śmieci.
• Koszt nowego dywanu.
  • Który przypadkowo dla pamięci RAM jest bezpłatny.

Odśmiecanie jest ogromnym tematem i jest wiele pytań zarówno w Programmers.SE, jak i StackOverflow.

Jeśli chodzi o kwestię poboczną, menedżer alokacji C / C ++ znany jako TCMalloc wraz z zliczaniem referencji obiektów teoretycznie jest w stanie sprostać najlepszym wymaganiom wydajnościowym dowolnego systemu GC.

Głównym powodem jest to, że kiedy pytasz Javę o nową bryłę pamięci, idzie ona prosto na koniec stosu i daje ci blok. W ten sposób alokacja pamięci jest tak samo szybka jak alokacja na stosie (tak robisz przez większość czasu w C / C ++, ale poza tym ..)

Przydziały są więc szybkie, ale ... to nie liczy kosztów uwolnienia pamięci. Tylko dlatego, że niczego nie zwalniasz, dopóki dużo później nie oznacza, że ​​nie kosztuje to dużo, aw przypadku systemu GC koszt jest znacznie większy niż „normalne” przydziały sterty - nie tylko GC musi przebiegać przez wszystkie obiekty, aby sprawdzić, czy są one żywe, czy też nie, musi je również zwolnić, a (duży koszt) skopiować pamięć, aby zagęścić stertę - dzięki czemu możesz mieć szybki przydział na końcu mechanizm (lub zabraknie pamięci, na przykład C / C ++ przejdzie stertę po każdym przydziale, szukając następnego bloku wolnego miejsca, który może zmieścić się w obiekcie).

Jest to jeden z powodów, dla których testy porównawcze Java / .NET wykazują tak dobrą wydajność, a rzeczywiste aplikacje wykazują tak niską wydajność. Mam tylko spojrzeć na aplikacje na swoim telefonie - naprawdę szybko, te czułe są wszystkie napisane z wykorzystaniem NDK, tak, nawet byłem zaskoczony.

Obecnie kolekcje mogą być szybkie, jeśli wszystkie obiekty są przydzielane lokalnie, np. W jednym ciągłym bloku. Teraz w Javie po prostu nie otrzymujesz ciągłych bloków, ponieważ obiekty są przydzielane pojedynczo z wolnego końca stosu. Możesz skończyć z nimi szczęśliwie przylegle, ale tylko przez szczęście (tj. Do kaprysu procedur kompresji GC i tego, jak kopiuje obiekty). Z drugiej strony C / C ++ wyraźnie obsługuje przydziały ciągłe (oczywiście przez stos). Zasadniczo obiekty sterty w C / C ++ nie różnią się od BTW Java.

Teraz dzięki C / C ++ możesz być lepszy niż domyślne alokatory, które zostały zaprojektowane w celu oszczędzania pamięci i efektywnego jej wykorzystania. Możesz zastąpić alokator zestawem pul bloków stałych, dzięki czemu zawsze możesz znaleźć blok, który ma dokładnie odpowiedni rozmiar dla przydzielanego obiektu. Spacer po stosie staje się kwestią wyszukiwania bitmapy, aby zobaczyć, gdzie jest wolny blok, a cofnięcie alokacji polega po prostu na ponownym ustawieniu bitów w tej bitmapie. Kosztem jest to, że zużywasz więcej pamięci podczas przydzielania w blokach o stałym rozmiarze, więc masz stos 4 bloków bajtów, inny dla bloków 16 bajtów itp.

Eden Space

Więc moje pytanie brzmi: czy którekolwiek z tych stwierdzeń może być prawdziwe, a jeśli tak, to dlaczego alokacja sterty Java jest o wiele szybsza.

Studiowałem trochę o tym, jak działa Java GC, ponieważ jest to dla mnie bardzo interesujące. Zawsze staram się poszerzać swoją kolekcję strategii alokacji pamięci w C i C ++ (zainteresowany próbą zaimplementowania czegoś podobnego w C), i jest to bardzo, bardzo szybki sposób na alokację wielu obiektów w trybie serii praktyczna perspektywa, ale przede wszystkim ze względu na wielowątkowość.

Sposób alokacji Java GC polega na użyciu wyjątkowo taniej strategii alokacji, aby początkowo alokować obiekty do przestrzeni „Eden”. Z tego, co mogę powiedzieć, używa sekwencyjnego przydziału puli.

Jest to o wiele szybsze, jeśli chodzi o algorytm i ograniczenie obowiązkowych błędów strony niż ogólnego przeznaczenia mallocw C lub domyślnie, rzucając operator neww C ++.

Ale sekwencyjne alokatory mają rażącą słabość: mogą alokować porcje o zmiennej wielkości, ale nie mogą uwolnić żadnych pojedynczych porcji. Po prostu przydzielają w prosty sekwencyjny sposób z dopełnieniem do wyrównania i mogą wyczyścić tylko całą przydzieloną pamięć naraz. Przydają się zwykle w C i C ++ do konstruowania struktur danych, które wymagają jedynie wstawiania i usuwania elementów, takich jak drzewo wyszukiwania, które musi zostać zbudowane tylko raz, gdy program się uruchamia, a następnie jest wielokrotnie przeszukiwane lub dodawane są tylko nowe klucze ( brak kluczy usuniętych).

Mogą być również używane nawet w strukturach danych, które pozwalają na usuwanie elementów, ale te elementy nie zostaną w rzeczywistości zwolnione z pamięci, ponieważ nie możemy ich indywidualnie zwolnić. Taka struktura wykorzystująca sekwencyjny alokator zużywałaby po prostu coraz więcej pamięci, chyba że miałaby jakieś odroczone przejście, w którym dane zostały skopiowane do nowej, zwartej kopii przy użyciu osobnego sekwencyjnego alokatora (a czasami jest to bardzo skuteczna technika, jeśli wygrany ustalony alokator wygrał z jakiegoś powodu - po prostu od razu po kolei przydziel nową kopię struktury danych i zrzuć całą pamięć starej).

Kolekcja

Podobnie jak w powyższym przykładzie struktury danych / puli sekwencyjnej, ogromnym problemem byłoby, gdyby Java GC alokowała tylko w ten sposób, mimo że jest super szybka dla alokacji serii wielu pojedynczych porcji. Nie byłby w stanie niczego zwolnić, dopóki oprogramowanie nie zostanie zamknięte, w którym to momencie może uwolnić (oczyścić) wszystkie pule pamięci jednocześnie.

Zamiast tego po jednym cyklu GC przechodzi się przez istniejące obiekty w przestrzeni „Eden” (przydzielane sekwencyjnie), a te, do których nadal się odwołuje, są przydzielane za pomocą bardziej ogólnego przeznaczenia, który może uwolnić poszczególne porcje. Te, o których już nie ma mowy, zostaną po prostu zwolnione w procesie oczyszczania. Zasadniczo jest to więc „kopiowanie obiektów z przestrzeni Eden, jeśli nadal się do nich odwołuje, a następnie czyszczenie”.

Zwykle byłoby to dość drogie, więc odbywa się to w osobnym wątku w tle, aby uniknąć znacznego zablokowania wątku, który pierwotnie przydzielił całą pamięć.

Po skopiowaniu pamięci z miejsca Eden i przydzieleniu jej przy użyciu tego droższego schematu, który może uwolnić poszczególne porcje po początkowym cyklu GC, obiekty przenoszą się do bardziej trwałego regionu pamięci. Te pojedyncze fragmenty są następnie uwalniane w kolejnych cyklach GC, jeśli przestaną być przywoływane.

Prędkość

Mówiąc wprost, powodem, dla którego Java GC może znacznie przewyższyć C lub C ++ przy alokacji prostej stosu, jest to, że używa najtańszej, całkowicie zdegenerowanej strategii alokacji w wątku żądającym alokacji pamięci. Następnie oszczędza to droższą pracę, którą normalnie musielibyśmy wykonać, używając bardziej ogólnego alokatora, takiego jak wyprostowanie mallocdla innego wątku.

Tak więc koncepcyjnie GC musi wykonać ogólnie więcej pracy, ale rozkłada to na wątki, aby pełny koszt nie był opłacany z góry przez jeden wątek. Pozwala to wątkowi przydzielić pamięć, aby zrobić to bardzo tanio, a następnie odłożyć prawdziwy koszt wymagany do prawidłowego wykonania czynności, aby poszczególne obiekty mogły zostać faktycznie uwolnione do innego wątku. W C lub C ++, kiedy my malloclub call operator new, musimy zapłacić pełny koszt z góry w ramach tego samego wątku.

Jest to główna różnica i dlaczego Java może znacznie przewyższać C lub C ++, używając tylko naiwnych wywołań malloclub operator newprzydzielić indywidualnie kilka małych fragmentów. Oczywiście zwykle będą pewne operacje atomowe i pewne potencjalne blokowanie, gdy rozpocznie się cykl GC, ale prawdopodobnie jest to całkiem sporo zoptymalizowane.

Zasadniczo proste wyjaśnienie sprowadza się do zapłacenia wyższego kosztu w jednym wątku ( malloc) w porównaniu do zapłacenia tańszego kosztu w jednym wątku, a następnie zapłacenia wyższego kosztu w innym wątku, który może działać równolegle ( GC). Wadą robienia tego w ten sposób jest to, że potrzebujesz dwóch pośredników, aby uzyskać odniesienie od obiektu do obiektu, co jest wymagane, aby umożliwić alokatorowi kopiowanie / przenoszenie pamięci bez unieważniania istniejących odniesień do obiektu, a także możesz utracić lokalizację przestrzenną, gdy pamięć obiektu zostanie wyprowadził się z przestrzeni „Eden”.

I na koniec, porównanie jest nieco niesprawiedliwe, ponieważ kod C ++ zwykle nie przydziela dużej liczby obiektów indywidualnie na stercie. Przyzwoity kod C ++ ma tendencję do alokacji pamięci dla wielu elementów w sąsiadujących blokach lub na stosie. Jeśli przydziela ładunek małych obiektów pojedynczo w darmowym sklepie, kod jest gówniany.

Wszystko zależy od tego, kto mierzy prędkość, jaką prędkość implementacji mierzą i co chcą udowodnić. I co porównują.

Jeśli spojrzysz na przydzielanie / zwalnianie, w C ++ możesz mieć 1 000 000 połączeń do malloc i 1 000 000 połączeń za darmo (). W Javie miałbyś 1 000 000 wywołań new () i moduł wyrzucania elementów bezużytecznych działający w pętli, który znajdowałby 1 000 000 obiektów, które mógłby uwolnić. Pętla może być szybsza niż wywołanie free ().

Z drugiej strony malloc / free poprawił się w innym czasie i zazwyczaj malloc / free po prostu ustawia jeden bit w osobnej strukturze danych i jest zoptymalizowany pod kątem malloc / free w tym samym wątku, więc w środowisku wielowątkowym brak zmiennych pamięci wspólnej są używane w wielu przypadkach (a zmienne blokowania lub pamięci współdzielonej są bardzo drogie).

Z drugiej strony istnieją takie rzeczy, jak liczenie referencji, które mogą być potrzebne bez wyrzucania elementów bezużytecznych, a to nie jest bezpłatne.