Czy można zaniedbać koszt GC, analizując czas działania najgorszych struktur danych określonych w zbędnym języku programowania?

22

Właśnie zdałem sobie sprawę, że zakładam, że odpowiedź na moje pytanie brzmi „tak”, ale nie mam dobrego powodu. Wyobrażam sobie, że może istnieje śmieciarz, który prawdopodobnie wprowadza tylko spowolnienie w najgorszym przypadku. Czy istnieje ostateczne odniesienie, które mogę zacytować? W moim przypadku pracuję nad czysto funkcjonalną strukturą danych i używam standardowego ML, jeśli te szczegóły mają znaczenie. $O(1)$

A może to pytanie byłoby jeszcze bardziej odpowiednie, gdy zastosuje się je do struktur danych określonych np. W Javie? Może są jakieś istotne dyskusje w podręcznikach algorytmów / struktury danych, które używają Java? (Wiem, że Sedgewick ma wersję Java, ale mam dostęp tylko do wersji C.)

— Maverick Woo
źródło

17

Tak, gc jest amortyzowane przez stały czas. Załóżmy, że masz algorytm działający przez czas ze szczytowym zestawem roboczym o rozmiarze . Teraz zauważ, że możesz przydzielić co najwyżej słowa podczas wykonywania programu, a koszt czasu uruchomienia kopiującego śmietnika wynosi (tj. Koszt gc jest proporcjonalny do sumy ilość danych na żywo). Jeśli więc uruchomisz gc co najwyżej razy, wówczas całkowity koszt środowiska wykonawczego jest ograniczony przez $n$ $k$ $O(n)$ $O(k)$ $O(n/k)$ $O(n)$ , co oznacza, że zamortyzowany koszt gc jest stały. Jeśli więc masz kolektor w stylu Cheneya, a każdy półprzestrzeń ma rozmiar , łatwo zauważyć, że nie można wywołać pełnej kolekcji więcej niż raz na kroków, ponieważ przydzielenie słów zajmuje czas, a zestaw roboczy nigdy nie przekracza rozmiaru , co daje ci pożądaną granicę. Uzasadnia to ignorowanie problemów z GC. $2k$ $n/k$ $k$ $O(k)$ $k$

Jednak jednym z przypadków, w których obecność lub nieobecność gc nie można pominąć, jest pisanie struktur danych bez blokady. Wiele nowoczesnych, pozbawionych blokad struktur danych celowo wycieka pamięć i polega na gc w zakresie poprawności. Wynika to z faktu, że na wysokim poziomie działają one w taki sposób, że kopiują niektóre dane, wprowadzają w nich zmiany i próbują atomowo aktualizować je za pomocą instrukcji CAS i uruchamiać to w pętli, aż CAS się powiedzie. Dodanie deterministycznego dezalokacji do tych algorytmów sprawia, że są one znacznie bardziej złożone, dlatego ludzie często nie przejmują się tym (zwłaszcza, że często są one ukierunkowane na środowiska podobne do Java).

EDYCJA: Jeśli chcesz granice bez amortyzacji, kolekcjoner Cheney tego nie zrobi - skanuje cały zestaw na żywo za każdym razem, gdy jest wywoływany. Słowo kluczowe dla wyszukiwarki Google to „odśmiecanie w czasie rzeczywistym”, a Djikstra i in. a Steele dała pierwsze kolekcjonerskie markery w czasie rzeczywistym, a Baker pierwszy gc.

@article {dijkstra1978fly,
  title = {{Odrzucanie śmieci w locie: ćwiczenie we współpracy}},
  autor = {Dijkstra, EW i Lamport, L. i Martin, AJ i Scholten, CS i Steffens, EFM},
  journal = {Komunikacja ACM},
  wielkość = {21},
  liczba = {11},
  strony = {966--975},
  issn = {0001-0782},
  rok = {1978},
  wydawca = {ACM}
}

@article {steele1975multiprocessing,
  title = {{Multiprocessing compactifying garbage collection}},
  autor = {Steele Jr, GL},
  journal = {Komunikacja ACM},
  wolumin = {18},
  liczba = {9},
  strony = {495--508},
  issn = {0001-0782},
  rok = {1975},
  wydawca = {ACM}
}

@article {baker1978list,
  title = {{Przetwarzanie listy w czasie rzeczywistym na komputerze szeregowym}},
  autor = {Baker Jr, HG},
  journal = {Komunikacja ACM},
  wielkość = {21},
  liczba = {4},
  strony = {280--294},
  issn = {0001-0782},
  rok = {1978},
  wydawca = {ACM}
}

— Neel Krishnaswami
źródło

a

$a$

b

$b$

a

$a$

b

$b$

1

„Tak, gc jest amortyzowane przez stały czas”. Zasadniczo nie jest to prawdą. Możesz argumentować, że GC może być, ale niekoniecznie i prawdziwe nie są. Na przykład, naiwność List.mapw OCaml jest w rzeczywistości kwadratową złożonością, ponieważ głębokość stosu jest liniowa, a stos przechodzi się za każdym razem, gdy ewakuuje się pokój dziecinny. To samo dotyczy głównych wycinków napotykających duże tablice wskaźników.

— Jon Harrop

12

$O(n)$

$O(1)$

Ostateczne odwołanie do śmiecia to:

Garbage Collection autorstwa Richarda Jonesa i Rafaela Lin

Ben Zorn pracował przy pomiarze rzeczywistych kosztów różnych algorytmów zbierania śmieci, chociaż w najnowszym artykule przedstawiono znacznie bardziej wszechstronne porównanie:

Mity i realia: Wpływ wydajności wywozu śmieci , SM Blackburn, P. Cheng i KS McKinley, ACM SIGMETRICS Conference on Measurement & Modeling Computer Systems, str. 25--36, Nowy Jork, NY, czerwiec 2004.

Więcej informacji:

Ujednolicona teoria wywozu śmieci , Bacon, Cheng i Rajan, ACM Conference on Object-Oriented Programming, Systems, Languages and Applications, Vancouver, BC, Canada, str. 50-68, 2004.

— Dave Clarke
źródło