Demonstracja usuwania śmieci jest szybsza niż ręczne zarządzanie pamięcią

23

Czytałem w wielu miejscach (cholera, nawet sam tak napisałem), że zbieranie śmieci może (teoretycznie) być szybsze niż ręczne zarządzanie pamięcią.

Jednak pokazywanie jest znacznie trudniejsze niż opowiadanie.
Tak naprawdę nigdy nie widziałem żadnego kodu, który demonstruje ten efekt w działaniu.

Czy ktoś ma (lub wie, gdzie mogę znaleźć) kod, który demonstruje tę przewagę wydajności?

memory garbage-collection

— Mehrdad
źródło

5

problem z GC polega na tym, że większość implementacji nie jest deterministyczna, więc 2 przebiegi mogą mieć bardzo różne wyniki, nie wspominając już o tym, że trudno jest wyodrębnić odpowiednie zmienne do porównania

— maniak zapadkowy

@ratchetfreak: Jeśli znasz jakieś przykłady, które są tylko szybsze (powiedzmy) w 70% przypadków, to też mi nie przeszkadza. Musi być jakiś sposób na porównanie tych dwóch, przynajmniej pod względem przepustowości (prawdopodobnie opóźnienie nie zadziałałoby).

— Mehrdad

1

Jest to trochę trudne, ponieważ zawsze możesz ręcznie zrobić wszystko, co daje GC przewagę nad tym, co zrobiłeś ręcznie. Może lepiej ograniczyć to do „standardowych” ręcznych narzędzi do zarządzania pamięcią (malloc () / free (), posiadanych wskaźników, wskaźników wspólnych z przeliczeniem, słabych wskaźników, żadnych niestandardowych alokatorów)? Lub, jeśli zezwolisz na niestandardowe alokatory (które mogą być bardziej realistyczne lub mniej realistyczne, w zależności od tego, jakiego programisty zakładasz), nałóż ograniczenia na wysiłek włożony w te alokatory. W przeciwnym razie ręczna strategia „kopiuj to, co robi GC w tym przypadku” jest zawsze co najmniej tak szybka jak GC.

1

Przez „skopiuj to, co robi GC” nie miałem na myśli „zbuduj własnego GC” (choć zauważ, że jest to teoretycznie możliwe w C ++ 11 i późniejszych wersjach, które wprowadza opcjonalną obsługę GC). Miałem na myśli, jak to sformułowałem wcześniej w tym samym komentarzu, „zrób to, co daje GC przewagę nad tym, co zrobiłeś ręcznie”. Na przykład, jeśli zagęszczenie podobne do Cheneya bardzo pomaga tej aplikacji, możesz ręcznie wdrożyć podobny schemat przydziału i zagęszczenia, korzystając z niestandardowych inteligentnych wskaźników do obsługi naprawy wskaźnika. Ponadto za pomocą technik takich jak stos cieni można wyszukiwać root w C lub C ++ kosztem dodatkowej pracy.

1

@Ike: W porządku. Widzisz, dlaczego zadałem pytanie? To był cały punkt mojego pytania - ludzie wymyślają wszelkiego rodzaju wyjaśnienia, które powinny mieć sens, ale wszyscy potykają się, gdy poprosisz ich o przedstawienie demonstracji, która udowodni, że to, co mówią, jest poprawne w praktyce. Chodziło o to, aby raz na zawsze pokazać, że tak naprawdę może się zdarzyć w praktyce.

— Mehrdad

26

Zobacz http://blogs.msdn.com/b/ricom/archive/2005/05/10/416151.aspx i skorzystaj ze wszystkich linków, aby zobaczyć, jak Rico Mariani kontra Raymond Chen (obaj bardzo kompetentni programiści w Microsoft) pojedynkują się . Raymond poprawiłby ten niezarządzany, Rico zareagowałby optymalizując to samo w zarządzanych.

Przy praktycznie zerowym nakładzie pracy na optymalizację, zarządzane wersje zaczęły działać wiele razy szybciej niż podręcznik. Ostatecznie instrukcja pokonała zarządzany, ale tylko poprzez optymalizację do poziomu, do którego większość programistów nie chciałaby pójść. We wszystkich wersjach użycie pamięci podręcznika było znacznie lepsze niż zarządzane.

— btilly
źródło

+1 za cytowanie rzeczywistego przykładu z kodem :) chociaż prawidłowe użycie konstrukcji C ++ (takich jak swap) nie jest takie trudne i prawdopodobnie doprowadziłoby cię tam dość łatwo pod względem wydajności ...

— Mehrdad

5

Możesz być w stanie prześcignąć Raymonda Chena pod względem wydajności. Jestem przekonany, że nie dam rady, chyba że się na to nie zgodzi z powodu choroby, pracuję wiele razy ciężej i mam szczęście. Nie wiem, dlaczego nie wybrał rozwiązania, które wybrałbyś. Jestem pewien, że miał ku temu powody

— btilly,

I skopiowane kod Raymonda tutaj , i porównać, napisałem własną wersję tutaj . Plik ZIP zawierający plik tekstowy znajduje się tutaj . Na moim komputerze mój działa w 14 ms, a Raymond w 21 ms. O ile nie zrobiłem czegoś złego (co jest możliwe), jego 215-liniowy kod jest o 50% wolniejszy niż moja 48-liniowa implementacja, nawet bez użycia plików mapowanych w pamięci lub niestandardowych pul pamięci (których używał). Mój jest o połowę dłuższy niż wersja C #. Czy zrobiłem to źle, czy obserwujesz to samo?

— Mehrdad

1

@ Mehrdad Wyciągając starą kopię gcc na tym laptopie, mogę zgłosić, że ani twój kod, ani jego kod nie skompilują się, nie mówiąc już o tym, aby cokolwiek z tym zrobić. Fakt, że nie jestem w systemie Windows, prawdopodobnie to tłumaczy. Załóżmy jednak, że twoje liczby i kod są poprawne. Czy działają tak samo na dekadzie starego kompilatora i komputera? (Zobacz, kiedy powstał blog.) Może, a może nie. Załóżmy, że tak jest, że on (będąc programistą C) nie wiedział, jak prawidłowo używać C ++, itd. Z czym mamy?

— btilly,

1

Pozostaje nam rozsądny program C ++, który można przetłumaczyć na pamięć zarządzaną i przyspieszyć. Ale gdzie wersję C ++ można zoptymalizować i przyspieszyć dalej. To, co wszyscy jesteśmy zgodni, to ogólny wzorzec, który zawsze ma miejsce, gdy zarządzany kod jest szybszy niż niezarządzany. Jednak wciąż mamy konkretny przykład rozsądnego kodu od dobrego programisty, który był szybszy w wersji zarządzanej.

— btilly,

5

Ogólna zasada jest taka, że nie ma bezpłatnych obiadów.

GC eliminuje problemy związane z ręcznym zarządzaniem pamięcią i zmniejsza prawdopodobieństwo popełnienia błędów. Są sytuacje, w których określona strategia GC jest optymalnym rozwiązaniem problemu, w którym to przypadku nie zapłacisz kary za korzystanie z niej. Ale są też inne, w których inne rozwiązania będą szybsze. Ponieważ zawsze możesz symulować wyższe abstrakcje z niższego poziomu, ale nie na odwrót, możesz skutecznie udowodnić, że w żaden sposób wyższe abstrakcje nie mogą być szybsze niż niższe w ogólnym przypadku.

GC to szczególny przypadek ręcznego zarządzania pamięcią

Ręczne uzyskanie lepszej wydajności może wymagać dużo pracy lub więcej błędów, ale to inna historia.

— Guy Sirton
źródło

1

To nie ma dla mnie sensu. Aby podać kilka konkretnych przykładów: 1) alokatory i bariery zapisu w GC produkcyjnym są ręcznie napisanym asemblerem, ponieważ C jest zbyt nieefektywny, więc w jaki sposób pokonasz to z C, i 2) eliminacja ogona jest przykładem optymalizacji wykonywane w językach wysokiego poziomu (funkcjonalnych), które nie są wykonywane przez kompilator C, a zatem nie można tego zrobić w C. Spacerowanie po stosach to kolejny przykład czegoś, co zostało wykonane poniżej poziomu C przez języki wysokiego poziomu.

— Jon Harrop

2

1) Muszę zobaczyć konkretny kod, aby skomentować, ale jeśli ręcznie napisane alokatory / bariery w asemblerze są szybsze, użyj asemblera napisanego ręcznie. Nie jestem pewien, co to ma wspólnego z GC. 2) Spójrz tutaj: stackoverflow.com/a/9814654/441099 nie chodzi o to, czy jakiś język inny niż GC może dla ciebie wyeliminować rekurencję. Chodzi o to, że możesz przekształcić swój kod tak szybko lub szybciej. To, czy kompilator określonego języka może to zrobić automatycznie, jest kwestią wygody. W wystarczająco niskiej abstrakcji zawsze możesz to zrobić sam, jeśli chcesz.

— Guy Sirton

1

Ten przykład wywołania ogona w C działa tylko w specjalnym przypadku wywołania funkcji. C nie może poradzić sobie z ogólnym przypadkiem funkcji wywoływania ogona. Opadanie na asemblera i zakładanie nieskończonego czasu na rozwój jest tarapetą Turinga.

— Jon Harrop

3

Łatwo jest skonstruować sztuczną sytuację, w której GC jest nieskończenie wydajniejszy niż metody ręczne - po prostu ustal, że istnieje tylko jeden „root” dla śmietnika, i że wszystko jest śmieci, więc krok GC jest natychmiast ukończony.

Jeśli się nad tym zastanowić, jest to model używany podczas wyrzucania elementów bezużytecznych do pamięci przydzielonej procesom. Proces umiera, cała pamięć to śmieci, gotowe. Nawet w praktyce proces, który się uruchamia, uruchamia i umiera, nie pozostawiając śladu, może być bardziej wydajny niż proces, który uruchamia się i działa na zawsze.

W przypadku praktycznych programów napisanych w językach z funkcją odśmiecania zaletą nie jest szybkość, lecz poprawność i prostota.

— ddyer
źródło

Jeśli łatwo jest skonstruować sztuczny przykład, czy mógłbyś pokazać prosty?

— Mehrdad

1

@ Mehrdad Wyjaśnił prosty. Napisz program, w którym wersja GC nie wykonuje czyszczenia pamięci przed zamknięciem. Wersja ręcznie zarządzanej pamięci będzie wolniejsza, ponieważ wyraźnie śledziła i zwalniała rzeczy.

— btilly,

3

@btilly: „Napisz program, w którym wersja GC nie wykonuje czyszczenia pamięci przed wyjściem.” ... niepowodzenie w wyrzucaniu elementów bezużytecznych to przede wszystkim wyciek pamięci z powodu braku działającego GC, a nie poprawa wydajności z powodu obecności GC! To jak wywoływanie abort()w C ++ przed zamknięciem programu. To bezsensowne porównanie; nawet nie zbierasz śmieci, po prostu pozwalasz na wyciek pamięci. Nie można powiedzieć, że zbieranie śmieci jest szybsze (lub wolniejsze), jeśli nie zbieracie śmieci na początek ...

— Mehrdad

Aby zrobić skrajny przykład, musisz zdefiniować kompletny system z własnym stertą i zarządzaniem stertami, co byłoby świetnym projektem studenckim, ale zbyt dużym, aby zmieścić się na tym marginesie. Radziłbyś sobie całkiem nieźle, pisząc program, który przydziela i zwalnia tablice o losowych rozmiarach, w sposób zaprojektowany tak, aby stresować metody zarządzania pamięcią inną niż gc.

— ddyer

3

@Mehrdad Nie tak. Scenariusz jest taki, że wersja GC nigdy nie osiągnęła progu, przy którym wykonałaby bieg, nie zaś, że nie działałaby poprawnie na innym zestawie danych. To trywialnie będzie bardzo dobre dla wersji GC, choć nie jest dobrym prognostykiem ostatecznej wydajności.

— btilly,

2

Należy wziąć pod uwagę, że GC to nie tylko strategia zarządzania pamięcią; nakłada także wymagania na cały projekt języka i środowiska wykonawczego, co wiąże się z kosztami (i korzyściami). Na przykład język, który obsługuje GC, musi zostać skompilowany do postaci, w której wskaźników nie można ukryć przed śmieciarzem, i ogólnie tam, gdzie nie można ich zbudować, chyba że przez starannie zarządzane operacje podstawowe systemu. Inną kwestią jest trudność z utrzymaniem gwarancji czasu reakcji, ponieważ GC nakłada pewne kroki, które należy wykonać, aby zakończyć.

W związku z tym, jeśli masz język, w którym zbierane są śmieci, i porównujesz szybkość z ręcznie zarządzaną pamięcią w tym samym systemie, nadal musisz zapłacić koszty ogólne, aby wesprzeć zbieranie śmieci, nawet jeśli go nie używasz.

— ddyer
źródło

2

Szybsze jest wątpliwe. Może być jednak bardzo szybki, niezauważalny lub szybszy, jeśli jest obsługiwany sprzętowo. Podobne konstrukcje dla maszyn LISP już dawno temu. Jeden wbudował GC w podsystem pamięci urządzenia jako taki, że główny procesor nie wiedział, że tam jest. Podobnie jak wiele późniejszych projektów, GC działało równolegle z głównym procesorem z niewielkimi lub żadnymi przerwami. Bardziej nowoczesnym designem są maszyny Azul Systems Vega 3, które uruchamiają kod Java znacznie szybciej niż JVM z wykorzystaniem specjalnie zaprojektowanych procesorów i bez przerwy GC. Google, jeśli chcesz wiedzieć, jak szybka może być GC (lub Java).

— Nick P.
źródło

2

Zrobiłem w tym sporo pracy i opisałem niektóre z nich tutaj . Testowałem Boehm GC w C ++, alokując za pomocą, mallocale nie uwalniając, alokując i zwalniając za pomocą freei GC napisany w C ++ wszystko w porównaniu do podstawowego GC OCaml działającego na liście Solver n-queens. GC OCaml był szybszy we wszystkich przypadkach. Programy C ++ i OCaml zostały celowo napisane, aby wykonać te same alokacje w tej samej kolejności.

Można oczywiście przepisać programy w celu rozwiązania problemu, używając tylko 64-bitowych liczb całkowitych i bez przydziałów. Chociaż szybsze, to pokonałoby punkt ćwiczenia (który polegał na przewidywaniu wydajności nowego algorytmu GC, nad którym pracowałem przy użyciu prototypu zbudowanego w C ++).

Wiele lat spędziłem w branży, przenosząc prawdziwy kod C ++ na języki zarządzane. W prawie każdym przypadku zaobserwowałem znaczną poprawę wydajności, z których wiele prawdopodobnie wynikało z ręcznego zarządzania pamięcią przez GC. Praktyczne ograniczenie nie polega na tym, co można osiągnąć za pomocą znaku mikrodruku, ale na tym, co można osiągnąć przed upływem terminu, a języki oparte na GC oferują tak ogromne zwiększenie wydajności, że nigdy nie spojrzałem wstecz. Nadal używam C i C ++ na urządzeniach wbudowanych (mikrokontrolerach), ale nawet to się teraz zmienia.

— Jon Harrop
źródło

+1 dzięki. Gdzie możemy zobaczyć i uruchomić kod testu?

— Mehrdad

Kod jest rozrzucony po miejscu. Tutaj opublikowałem wersję mark-region: groups.google.com/d/msg/…

— Jon Harrop

1

Istnieją wyniki dla wątku zarówno bezpiecznego, jak i niebezpiecznego.

— Jon Harrop

1

@ Mehrdad: „Czy wyeliminowałeś takie potencjalne źródła błędów?”. Tak. OCaml ma bardzo prosty model kompilacji bez optymalizacji, takich jak analiza ucieczki. Reprezentacja zamknięcia przez OCaml jest w rzeczywistości znacznie wolniejsza niż rozwiązanie C ++, więc naprawdę powinna używać niestandardowego, List.filterpodobnie jak C ++. Ale tak, z pewnością masz rację, że niektóre operacje RC można uniknąć. Jednak największym problemem, jaki widzę na wolności, jest to, że ludzie nie mają czasu na ręczne przeprowadzanie takich optymalizacji na dużych bazach kodu przemysłowego.

— Jon Harrop

2

Tak, absolutnie. Bez dodatkowego wysiłku pisania, ale pisanie kodu nie jest wąskim gardłem w C ++. Utrzymanie kodu to. Utrzymywanie kodu przy tego rodzaju przypadkowej złożoności jest koszmarem. Większość baz kodu przemysłowego to miliony linii kodu. Po prostu nie chcesz sobie z tym poradzić. Widziałem, jak ludzie przekształcają wszystko, shared_ptraby naprawić błędy współbieżności. Kod jest dużo wolniejszy, ale hej, teraz działa.

— Jon Harrop

-1

Taki przykład niekoniecznie ma zły schemat ręcznej alokacji pamięci.

Załóż najlepszy zbieracz śmieci GC. Ma wewnętrznie metody alokacji pamięci, określania, którą pamięć można zwolnić oraz metody jej ostatecznego uwolnienia. Razem zajmują mniej czasu niż wszystkie GC; trochę czasu spędza się na innych metodach GC.

Rozważmy teraz ręczny alokator, który korzysta z tego samego mechanizmu alokacji co GCi którego free()wywołanie tylko odsuwa pamięć na tę samą metodę, co GC. Nie ma fazy skanowania ani żadnej innej metody. To z konieczności zajmuje mniej czasu.

— MSalters
źródło

2

Garbage-collector często uwalnia wiele obiektów, bez konieczności umieszczania pamięci w przydatnym stanie po każdym z nich. Rozważ zadanie usunięcia z listy tablic wszystkich elementów spełniających określone kryterium. Usuwanie pojedynczego elementu z listy N-elementów to O (N); usuwając M elementów z listy N, pojedynczo oznacza O (M * N). Jednak usunięcie wszystkich elementów spełniających kryterium w jednym przejściu przez listę to O (1).

— supercat

@ superupat: freemoże również zbierać partie. (I oczywiście usunięcie wszystkich pozycji spełniających kryterium jest wciąż O (N), choćby z powodu samej przejścia listy)

— MSalters

Usunięcie wszystkich elementów spełniających kryterium wynosi co najmniej O (N). Masz rację, że freemoże działać w trybie zbierania wsadowego, jeśli każdy element pamięci ma powiązaną z nim flagę, chociaż GC wciąż może wyjść na przód w niektórych sytuacjach. Jeśli ktoś ma M referencji, które identyfikują L odrębnych pozycji z zestawu N rzeczy, czas na usunięcie każdego odwołania, do którego nie ma żadnego odniesienia, i utrwalenie reszty to O (M) zamiast O (N). Jeśli jest dostępne M dodatkowej przestrzeni, stała skalowania może być dość mała. Ponadto, kompaktowanie w

— nieskanującym

@ superupat: Cóż, na pewno nie jest to O (1), jak stwierdza twoje ostatnie zdanie w pierwszym komentarzu.

— MSalters

1

@MSalters: „A co zapobiegnie deterministycznemu planowi posiadania pokoju dziecinnego?”. Nic. Wykrywanie śmieci przez OCaml jest deterministyczne i wykorzystuje pokój dziecinny. Ale to nie jest „ręczne” i myślę, że niewłaściwie używasz słowa „deterministyczny”.

— Jon Harrop