Jak działa wyrzucanie elementów bezużytecznych w językach, które są kompilowane natywnie?

Po przejrzeniu kilku odpowiedzi na temat przepełnienia stosu jest jasne, że niektóre natywnie skompilowane języki mają funkcję usuwania śmieci . Ale nie jest dla mnie jasne, jak dokładnie by to działało.

Rozumiem, jak wyrzucanie elementów bezużytecznych może działać z interpretowanym językiem. Śmieciarka po prostu działałaby obok interpretera i usuwała nieużywane i nieosiągalne obiekty z pamięci programu. Oboje biegną razem.

Jak by to działało z skompilowanymi językami? Rozumiem, że kiedy kompilator skompiluje kod źródłowy do kodu docelowego - w szczególności macierzystego kodu maszynowego - jest to gotowe. Jego praca jest skończona. Jak więc skompilowany program może być również usuwany?

Czy kompilator działa w jakiś sposób z procesorem, gdy program jest wykonywany w celu usuwania obiektów „śmieciowych”? Czy też kompilator zawiera minimalny moduł wyrzucania elementów bezużytecznych w pliku wykonywalnym skompilowanego programu.

Uważam, że moje drugie stwierdzenie miałoby większą ważność niż poprzednie z powodu tego fragmentu tej odpowiedzi na temat przepełnienia stosu :

Jednym z takich języków programowania jest Eiffel. Większość kompilatorów Eiffla generuje kod C ze względu na przenośność. Ten kod C służy do tworzenia kodu maszynowego przez standardowy kompilator C. Implementacje Eiffla zapewniają GC (a czasem nawet dokładne GC) dla tego skompilowanego kodu i nie ma potrzeby używania VM. W szczególności kompilator VisualEiffel generował natywny kod maszynowy x86 bezpośrednio z pełną obsługą GC .

Ostatnia instrukcja wydaje się sugerować, że kompilator zawiera jakiś program w końcowym pliku wykonywalnym, który działa jako śmieciarz podczas działania programu.

Strona na stronie D języka na temat wyrzucania elementów bezużytecznych - która jest natywnie skompilowana i ma opcjonalny moduł wyrzucania elementów bezużytecznych - również wydaje się sugerować, że jakiś program działający w tle działa obok oryginalnego programu wykonywalnego w celu wdrożenia wyrzucania elementów bezużytecznych.

D jest językiem programowania systemowego z obsługą odśmiecania. Zwykle nie jest konieczne jawne zwalnianie pamięci. Po prostu przydziel w razie potrzeby, a moduł odśmiecania będzie okresowo zwracał całą nieużywaną pamięć do puli dostępnej pamięci.

Jeśli metoda wspomniano powyżej jest używany, jak dokładnie to działa? Czy kompilator przechowuje kopię jakiegoś programu do czyszczenia pamięci i wkleja go do każdego generowanego przez siebie pliku wykonywalnego?

Czy też mam błędne myślenie? Jeśli tak, to jakie metody są używane do implementacji czyszczenia pamięci dla skompilowanych języków i jak dokładnie by one działały?

Odśmiecanie w skompilowanym języku działa w taki sam sposób, jak w języku interpretowanym. Języki takie jak Go używają śledzenia zbieraczy śmieci, mimo że ich kod jest zwykle kompilowany z wyprzedzeniem do kodu maszynowego.

(Śledzenie) wyrzucanie elementów bezużytecznych zwykle rozpoczyna się od przejścia stosów wywołań wszystkich aktualnie działających wątków. Obiekty na tych stosach są zawsze żywe. Następnie moduł wyrzucania elementów bezużytecznych przemierza wszystkie obiekty wskazane przez obiekty aktywne, dopóki nie zostanie wykryty cały wykres obiektów aktywnych.

Oczywiste jest, że wykonanie tego wymaga dodatkowych informacji, których nie dostarczają języki takie jak C. W szczególności wymaga mapy ramki stosu każdej funkcji, która zawiera przesunięcia wszystkich wskaźników (i prawdopodobnie ich typów danych), a także mapy wszystkich układów obiektów zawierających te same informacje.

Łatwo jednak zauważyć, że języki, które mają silne gwarancje typu (np. Jeśli rzutowanie wskaźnika na różne typy danych jest niedozwolone) mogą rzeczywiście obliczyć te mapy w czasie kompilacji. Po prostu przechowują powiązanie między adresami instrukcji i mapami ramek stosu oraz powiązanie między typami danych i mapami układu obiektów w pliku binarnym. Informacje te umożliwiają im następnie przejście przez wykres obiektowy.

Sam garbage collector jest niczym więcej niż biblioteką połączoną z programem, podobną do biblioteki standardowej C. Na przykład ta biblioteka może zapewnić funkcję podobną do malloc()tej, która uruchamia algorytm gromadzenia danych, jeśli ciśnienie pamięci jest wysokie.

Czy kompilator przechowuje kopię jakiegoś programu do czyszczenia pamięci i wkleja go do każdego generowanego przez siebie pliku wykonywalnego?

Brzmi nieelegancko i dziwnie, ale tak. Kompilator ma całą bibliotekę narzędzi, zawierającą znacznie więcej niż tylko kod czyszczenia pamięci, a wywołania tej biblioteki będą wstawiane do każdego tworzonego pliku wykonywalnego. Nazywa się to biblioteką wykonawczą i zdziwiłbyś się, ile różnych zadań zazwyczaj wykonuje.

Czy też kompilator zawiera minimalny moduł wyrzucania elementów bezużytecznych w kodzie skompilowanego programu.

To dziwny sposób powiedzenia „kompilator łączy program z biblioteką, która wykonuje odśmiecanie”. Ale tak właśnie się dzieje.

Nie jest to nic specjalnego: kompilatory zwykle łączą tony bibliotek z programami, które kompilują; w przeciwnym razie skompilowane programy nie mogłyby wiele zrobić bez ponownego wdrożenia wielu rzeczy od zera: nawet pisanie tekstu na ekranie / pliku /… wymaga biblioteki.

Ale może GC różni się od tych innych bibliotek, które zapewniają jawne interfejsy API, które wywołuje użytkownik?

Nie: w większości języków biblioteki wykonawcze wykonują wiele zakulisowych prac bez publicznego interfejsu API, poza GC. Rozważ te trzy przykłady:

1. Propagacja wyjątków i wywoływanie rozwijania / niszczenia stosu.
2. Dynamiczny przydział pamięci (który zwykle nie polega tylko na wywołaniu funkcji, jak w C, nawet gdy nie ma funkcji wyrzucania elementów bezużytecznych).
3. Śledzenie informacji o typie dynamicznym (dla rzutów itp.).

Dlatego biblioteka śmieciarek wcale nie jest wyjątkowa, a a priori nie ma nic wspólnego z tym, czy program został skompilowany z wyprzedzeniem.

Jak by to działało z kompilowanymi językami?

Twoje sformułowanie jest nieprawidłowe. Język programowania jest specyfikacja napisany w jakimś raportu technicznego (za dobry przykład, patrz R5RS ). Mówisz o implementacji określonego języka (jakim jest oprogramowanie).

^{(niektóre języki programowania mają złe specyfikacje lub nawet brakujące te, lub po prostu jako zgodny z jakiegoś realizacji próbki, jednak jeden język programowania definiuje zachowanie - np ma składnię i semantykę -, to nie produkt, oprogramowanie, ale może być implementowane przez niektóre oprogramowanie; wiele języków programowania ma kilka implementacji; w szczególności „skompilowany” jest przymiotnikiem stosowanym do implementacji - nawet jeśli niektóre języki programowania są łatwiejsze do implementacji przez tłumaczy niż przez kompilatory.)}

Rozumiem, że kiedy kompilator skompiluje kod źródłowy do kodu docelowego - w szczególności macierzystego kodu maszynowego - jest to gotowe. Jego praca jest skończona.

Zauważ, że tłumacze i kompilatory mają luźne znaczenie, a niektóre implementacje językowe można uznać za oba. Innymi słowy, istnieje między nimi kontinuum. Przeczytaj najnowszą książkę Dragon Book i pomyśl o kodzie bajtowym , kompilacji JIT , dynamicznie emitującym kodzie C, który jest kompilowany w jakąś „wtyczkę”, a następnie dlopen (3) -ed tym samym procesem (i na obecnych maszynach jest to wystarczająco szybki, aby być kompatybilnym z interaktywna REPL , zobacz to )

Zdecydowanie polecam przeczytanie podręcznika GC . Aby odpowiedzieć, potrzebna jest cała książka . Wcześniej przeczytaj stronę Wikipedii Garbage Collection (którą zakładam przeczytałeś przed przeczytaniem poniżej).

System wykonawczy implementacji skompilowanego języka zawiera moduł czyszczenia pamięci, a kompilator generuje kod, który jest odpowiedni dla tego konkretnego systemu wykonawczego. W szczególności operacje podstawowe alokacji (są kompilowane do kodu maszynowego, który) wywoła (lub może) wywołać system wykonawczy.

Jak więc skompilowany program może być również usuwany?

Po prostu emitując kod maszynowy, który używa (i jest „przyjazny” i „zgodny z”) systemem wykonawczym.

Zauważ, że możesz znaleźć kilka bibliotek śmieci, w szczególności Boehm GC , MPS Ravenbrook , a nawet moje ( nieobsługiwane ) Qish . A kodowanie prostego GC nie jest bardzo trudne (jednak debugowanie jest trudniejsze, a kodowanie konkurencyjnego GC jest trudne ).

W niektórych przypadkach kompilator używałby konserwatywnego GC (takiego jak Boehm GC ). Wtedy nie ma wiele do kodowania. Konserwatywny GC (gdy kompilator wywoła procedurę alokacji lub całą procedurę GC) czasami skanuje cały stos wywołań i zakłada, że ​​dowolna strefa pamięci (pośrednio) dostępna ze stosu wywołań jest aktywna. Nazywa się to konserwatywnym GC, ponieważ informacje o pisaniu są tracone: jeśli liczba całkowita na stosie wywołań będzie wyglądać jak jakiś adres, zostanie zastosowana itd.

W innych (trudniejszych) przypadkach środowisko wykonawcze zapewnia generowanie śmieci w trybie kopiowania (typowym przykładem jest kompilator Ocaml, który kompiluje kod Ocaml do kodu maszynowego przy użyciu takiego GC). Problem polega na znalezieniu dokładnie na stosach połączeń wszystkich wskaźników, a niektóre z nich są przenoszone przez GC. Następnie kompilator generuje metadane opisujące ramki stosu wywołań, których używa środowisko wykonawcze. Więc konwencje telefoniczne i ABI stają specyficzny dla tej realizacji (tj kompilatora) i układu wykonawczego.

W niektórych przypadkach kod maszynowy generowany przez kompilator (w rzeczywistości nawet zamknięcia do niego wskazujące) jest sam śmieciami . Dotyczy to zwłaszcza SBCL (dobrej implementacji Common Lisp), która generuje kod maszynowy dla każdej interakcji REPL . Wymaga to również pewnych metadanych opisujących kod i ramek wywołania używanych w nim.

Czy kompilator przechowuje kopię jakiegoś programu do czyszczenia pamięci i wkleja go do każdego generowanego przez siebie pliku wykonywalnego?

Sortuj Jednak system wykonawczy może być biblioteką współdzieloną itp. Czasami (w Linuksie i kilku innych systemach POSIX) może to być nawet interpreter skryptów, np. Przekazywany do execve (2) z shebangiem . Lub tłumacz ELF , patrz elf (5) i PT_INTERPitp.

BTW, większość kompilatorów dla języka z odśmiecaniem pamięci (i ich systemem uruchomieniowym ) jest dziś wolnym oprogramowaniem . Pobierz kod źródłowy i przestudiuj go.

Istnieją już dobre odpowiedzi, ale chciałbym wyjaśnić niektóre nieporozumienia związane z tym pytaniem.

Nie ma czegoś takiego jak „natywnie skompilowany język” jako taki. Na przykład ten sam kod Java został zinterpretowany (a następnie częściowo skompilowany w czasie wykonywania) na moim starym telefonie (Java Dalvik) i jest (z wyprzedzeniem) skompilowany na moim nowym telefonie (ART).

Różnica między uruchomieniem kodu natywnego i interpretowanego jest o wiele mniej rygorystyczna, niż się wydaje. Obie potrzebują do działania bibliotek wykonawczych i systemu operacyjnego (*). Interpretowany kod wymaga interpretera, ale interpreter jest tylko częścią środowiska wykonawczego. Ale nawet to nie jest ścisłe, ponieważ można zastąpić interpreter kompilatorem (just-in-time). Aby uzyskać maksymalną wydajność, możesz mieć jedno i drugie (środowisko wykonawcze Java na pulpicie zawiera interpreter i dwa kompilatory).

Bez względu na to, jak uruchomić kod, powinien on zachowywać się tak samo. Przydzielanie i zwalnianie pamięci jest zadaniem środowiska wykonawczego (podobnie jak otwieranie plików, uruchamianie wątków itp.). W swoim języku piszesz new X()lub piszesz podobnie. Specyfikacja języka mówi, co powinno się zdarzyć, a środowisko wykonawcze to robi.

Część wolnej pamięci zostaje przydzielona, ​​wywoływany jest konstruktor itp. Gdy nie ma wystarczającej ilości pamięci, wywoływany jest moduł czyszczenia pamięci. Ponieważ jesteś już w środowisku wykonawczym, które jest rodzimym fragmentem kodu, istnienie interpretera nie ma żadnego znaczenia.

Naprawdę nie ma bezpośredniego związku między interpretacją kodu a odśmiecaniem. Po prostu języki niskiego poziomu, takie jak C, zostały zaprojektowane z myślą o szybkości i szczegółowej kontroli wszystkiego, co nie pasuje do idei nienatywnego kodu lub śmietnika. Więc jest tylko korelacja.

Było to bardzo prawdziwe w dawnych czasach, gdy np. Interpreter Java był bardzo wolny, a moduł wyrzucania elementów bezużytecznych. W dzisiejszych czasach sprawy wyglądają zupełnie inaczej i mówienie o tłumaczonym języku straciło sens.

(*) Przynajmniej mówiąc o kodzie ogólnego przeznaczenia, pomijając programy ładujące rozruch i podobne.

Szczegóły różnią się między implementacjami, ale ogólnie jest to kombinacja następujących elementów:

• Biblioteka środowiska wykonawczego, która zawiera GC. Będzie to obsługiwać przydział pamięci i mieć inne punkty wejścia, w tym funkcję „GC_now”.
• Kompilator utworzy tabele dla GC, aby wiedział, które pola w których typach danych są odwołaniami. Zostanie to również wykonane dla ramek stosu dla każdej funkcji, aby GC mógł śledzić ze stosu.
• Jeśli GC jest przyrostowy (aktywność GC jest przeplatana z programem) lub współbieżny (działa w osobnym wątku), wówczas kompilator będzie również zawierał specjalny kod obiektowy do aktualizacji struktur danych GC po aktualizacji odniesień. Oba mają podobne problemy dotyczące spójności danych.

W przyrostowym i współbieżnym GC skompilowany kod i GC muszą współpracować, aby zachować niektóre niezmienniki. Na przykład w kolektorze kopiującym GC działa, kopiując dane na żywo z przestrzeni A do przestrzeni B, pozostawiając śmieci. W następnym cyklu zmienia A i B i powtarza. Tak więc jedną zasadą może być zapewnienie, że za każdym razem, gdy program użytkownika spróbuje odwołać się do obiektu w przestrzeni A, zostanie to wykryte, a obiekt zostanie natychmiast skopiowany do przestrzeni B, gdzie program może nadal uzyskać do niego dostęp. Adres przekazujący zostaje pozostawiony w przestrzeni A, aby wskazać GC, że tak się stało, aby wszelkie inne odniesienia do obiektu były aktualizowane w miarę ich śledzenia. Jest to znane jako „bariera odczytu”.

Algorytmy GC były badane od lat 60. XX wieku i istnieje obszerna literatura na ten temat. Google, jeśli chcesz uzyskać więcej informacji.