W językach takich jak C programista powinien wstawiać połączenia za darmo. Dlaczego kompilator nie robi tego automatycznie? Ludzie robią to w rozsądnym czasie (ignorując błędy), więc nie jest to niemożliwe.

EDYCJA: Dla przyszłego odniesienia, oto kolejna dyskusja, która ma ciekawy przykład.

Ponieważ nie można rozstrzygnąć, czy program ponownie użyje pamięci. Oznacza to, że żaden algorytm nie może poprawnie określić, kiedy zadzwonić free()we wszystkich przypadkach, co oznacza, że ​​każdy kompilator, który spróbowałby to zrobić, koniecznie wytworzyłby niektóre programy z wyciekami pamięci i / lub niektóre programy, które nadal używały zwolnionej pamięci. Nawet jeśli upewniłeś się, że twój kompilator nigdy nie zrobił drugiego, i pozwoliłeś programiście wstawić wywołania, aby free()naprawić te błędy, wiedza o tym, kiedy zadzwonić free()do tego kompilatora, byłaby nawet trudniejsza niż wiedza, kiedy zadzwonić, free()gdy używasz kompilatora, który nie próbował pomóc.

Jak słusznie zauważył David Richerby, problem jest ogólnie nierozstrzygalny. Żywotność obiektu jest globalną własnością programu i ogólnie może zależeć od danych wejściowych do programu.

Nawet precyzyjne dynamiczne zbieranie śmieci jest nierozstrzygalnym problemem! Wszystkie rzeczywiste śmieciarki używają osiągalności jako konserwatywne przybliżenie, czy przydzielony obiekt będzie potrzebny w przyszłości. To dobre przybliżenie, ale mimo to przybliżenie.

Ale to tylko prawda w ogóle. Jednym z najbardziej znanych oszustów w branży informatycznej jest „w ogóle niemożliwe, dlatego nic nie możemy zrobić”. Przeciwnie, istnieje wiele przypadków, w których można poczynić postępy.

Implementacje oparte na zliczaniu referencji są bardzo zbliżone do „kompilatora wstawiającego dezalokacje”, tak że trudno odróżnić. LLVM jest automatyczne odliczanie odniesienia (stosowanej w celu C i Swift ) jest znany np.

Wnioskowanie o regionie i zbieranie śmieci w czasie kompilacji są obecnie aktywnymi obszarami badawczymi. O wiele łatwiej okazuje się w deklaratywnych językach, takich jak ML i Mercury , w których nie można modyfikować obiektu po jego utworzeniu.

Teraz, na temat ludzi, istnieją trzy główne sposoby ręcznego zarządzania czasem życia alokacji:

1. Zrozumienie programu i problemu. Ludzie mogą na przykład umieszczać obiekty o podobnym czasie życia w tym samym obiekcie alokacji. Kompilatorzy i śmieciarze muszą to wywnioskować, ale ludzie mają dokładniejsze informacje.
2. Selektywnie wykorzystując nielokalne prowadzenie ksiąg rachunkowych (np. Zliczanie referencji) lub inne specjalne techniki alokacji (np. Strefy) tylko w razie potrzeby. Znów człowiek może to wiedzieć, gdy kompilator musi to wywnioskować.
3. Źle. W końcu wszyscy wiedzą o wdrażanych programach, które mają powolne wycieki. A jeśli nie, czasem programy i wewnętrzne interfejsy API muszą zostać zrestrukturyzowane w okresie użytkowania pamięci, zmniejszając możliwość ponownego użycia i modułowość.

Jest to problem niekompletności, a nie problem nierozstrzygalności

Chociaż prawdą jest, że optymalne rozmieszczenie instrukcji dealokacji jest nierozstrzygalne, po prostu o to nie chodzi. Ponieważ jest to nierozstrzygalne zarówno dla ludzi, jak i kompilatorów, niemożliwe jest zawsze świadome wybranie optymalnego położenia dezalokacji, niezależnie od tego, czy jest to proces ręczny czy automatyczny. A ponieważ nikt nie jest doskonały, wystarczająco zaawansowany kompilator powinien być w stanie przewyższyć ludzi w zgadywaniu w przybliżeniu optymalnych miejsc. Zatem nierozstrzygalność nie jest powodem, dla którego potrzebujemy wyraźnych instrukcji zwolnienia .

Są przypadki, w których wiedza zewnętrzna informuje o umieszczeniu oświadczenia o zwolnieniu. Usunięcie tych instrukcji jest następnie równoznaczne z usunięciem części logiki operacyjnej, a poproszenie kompilatora o automatyczne wygenerowanie tej logiki jest równoznaczne z prośbą o zgadnięcie, co myślisz.

Załóżmy na przykład, że piszesz pętlę Read-Evaluate-Print-Loop (REPL) : użytkownik wpisuje polecenie, a program je wykonuje. Użytkownik może przydzielić / cofnąć przydział pamięci, wpisując polecenia w REPL. Twój kod źródłowy określa, co REPL powinien zrobić dla każdej możliwej komendy użytkownika, w tym dezalokację, gdy użytkownik wpisze komendę.

Ale jeśli kod źródłowy C nie zawiera jawnej komendy do dezalokacji, kompilator musiałby wywnioskować, że powinien wykonać alokację, gdy użytkownik wprowadzi odpowiednią komendę do REPL. Czy to polecenie „zwolnij”, „bezpłatnie” czy coś innego? Kompilator nie ma możliwości dowiedzenia się, jakie polecenie ma być. Nawet jeśli programujesz logicznie, aby szukać tego słowa polecenia, a REPL je znajdzie, kompilator nie ma możliwości wiedzieć, że powinien odpowiedzieć na nie z alokacją, chyba że wyraźnie powiesz to w kodzie źródłowym.

tl; dr Problem w tym, że kod źródłowy C nie zapewnia kompilatorowi wiedzy zewnętrznej. Nierozstrzygalność nie jest problemem, ponieważ występuje niezależnie od tego, czy proces jest ręczny czy automatyczny.

Obecnie żadna z opublikowanych odpowiedzi nie jest w pełni poprawna.

Dlaczego kompilatory nie wstawiają automatycznie zwolnień?

1. Niektórzy. (Wyjaśnię później.)

2. Trywialnie możesz dzwonić free()tuż przed wyjściem z programu. Ale w twoim pytaniu istnieje domniemana potrzeba free()jak najszybszego połączenia .

3. Problem, kiedy należy wywołać free()w dowolnym programie C, gdy tylko pamięć jest nieosiągalna, jest nierozstrzygalny, tzn. W przypadku dowolnego algorytmu dostarczającego odpowiedź w określonym czasie istnieje przypadek, którego nie obejmuje. To - i wiele innych nierozstrzygalności arbitralnych programów - można udowodnić na podstawie problemu zatrzymania .

4. Niezdecydowany problem nie zawsze może zostać rozwiązany w skończonym czasie przez dowolny algorytm, czy to przez kompilator, czy przez człowieka.

5. Ludzie (próbują) pisać w podzbiorze programów C, które można zweryfikować pod kątem poprawności pamięci za pomocą ich algorytmu (samych siebie).

6. Niektóre języki osiągają # 1 poprzez wbudowanie # 5 w kompilator. Nie zezwalają programom na dowolne użycie alokacji pamięci, ale raczej na ich decydujący podzbiór. Foth i Rust to dwa przykłady języków, które mają bardziej restrykcyjny przydział pamięci niż języki C malloc(), które mogą (1) wykryć, czy program jest napisany poza ich zestawem decyzyjnym (2) automatycznie wstawiać dezalokacje.

„Ludzie to robią, więc nie jest to niemożliwe” to dobrze znany błąd. Niekoniecznie rozumiemy (a tym bardziej kontrolujemy) rzeczy, które tworzymy - pieniądze są częstym przykładem. Mamy tendencję do przeceniania (czasami dramatycznie) naszych szans na sukces w kwestiach technologicznych, zwłaszcza gdy czynniki ludzkie wydają się nieobecne.

Wydajność ludzka w programowaniu komputerowym jest bardzo niska , a studia informatyczne (brakuje wielu profesjonalnych programów edukacyjnych) pomagają zrozumieć, dlaczego ten problem nie ma prostej poprawki. Możemy pewnego dnia, być może nie za daleko, zastąpić sztuczną inteligencję w pracy. Nawet wtedy nie będzie ogólnego algorytmu, który automatycznie usunie alokację przez cały czas.

Brak automatycznego zarządzania pamięcią jest cechą tego języka.

C nie powinien być narzędziem do łatwego pisania oprogramowania. Jest to narzędzie do zmuszania komputera do robienia tego, co mu każesz. Obejmuje to przydzielanie i zwalnianie pamięci w wybranym momencie. C to język niskiego poziomu, którego używasz, gdy chcesz precyzyjnie kontrolować komputer lub gdy chcesz robić rzeczy w inny sposób, niż oczekiwali projektanci języka / biblioteki standardowej.

Chodzi przede wszystkim o artefakt historyczny, a nie niemożność wdrożenia.

Większość kompilatorów C buduje kod w taki sposób, że kompilator widzi tylko każdy plik źródłowy na raz; nigdy nie widzi całego programu naraz. Kiedy jeden plik źródłowy wywołuje funkcję z innego pliku źródłowego lub biblioteki, wszystko, co kompilator widzi, to plik nagłówkowy z typem zwracanym przez funkcję, a nie faktyczny kod funkcji. Oznacza to, że gdy istnieje funkcja zwracająca wskaźnik, kompilator nie ma sposobu, aby stwierdzić, czy pamięć, na którą wskazuje wskaźnik, musi zostać zwolniona, czy nie. Informacje do podjęcia decyzji, które nie są pokazywane kompilatorowi w tym momencie. Z drugiej strony, ludzki programista może wyszukiwać kod źródłowy funkcji lub dokumentację, aby dowiedzieć się, co należy zrobić ze wskaźnikiem.

Jeśli spojrzysz na bardziej nowoczesne języki niskiego poziomu, takie jak C ++ 11 lub Rust, przekonasz się, że większość z nich rozwiązała problem, ujawniając własność pamięci w typie wskaźnika. W C ++ użyłbyś unique_ptr<T>zamiast zwykłego T*do przechowywania pamięci i unique_ptr<T>upewnia się, że pamięć zostanie zwolniona, gdy obiekt osiągnie koniec zakresu, w przeciwieństwie do zwykłego T*. Programiści mogą przekazywać pamięć między unique_ptr<T>sobą, ale tylko jedna może unique_ptr<T>wskazywać na pamięć. Dlatego zawsze jest jasne, kto jest właścicielem pamięci i kiedy należy ją uwolnić.

C ++, ze względu na kompatybilność wsteczną, nadal umożliwia ręczne zarządzanie pamięcią starego stylu, a tym samym tworzenie błędów lub sposobów obejścia ochrony unique_ptr<T>. Rdza jest jeszcze bardziej surowa, ponieważ wymusza reguły własności pamięci poprzez błędy kompilatora.

Jeśli chodzi o nierozstrzygalność, problem zatrzymania i tym podobne, tak, jeśli trzymasz się semantyki C, nie jest możliwe określenie dla wszystkich programów, kiedy pamięć powinna zostać zwolniona. Jednak w przypadku większości rzeczywistych programów, a nie ćwiczeń akademickich lub błędnego oprogramowania, absolutnie można zdecydować, kiedy uwolnić, a kiedy nie. To przecież jedyny powód, dla którego człowiek może w pierwszej chwili dowiedzieć się, kiedy się uwolnić.

Inne odpowiedzi koncentrowały się na tym, czy możliwe jest zbieranie śmieci, niektóre szczegóły, jak to zrobić i niektóre problemy.

Jedną z kwestii, która nie została jeszcze omówiona, jest nieuniknione opóźnienie w usuwaniu śmieci. W C, gdy programista wywołuje free (), pamięć ta jest natychmiast dostępna do ponownego użycia. (Teoretycznie przynajmniej!) Więc programista może zwolnić swoją strukturę 100 MB, przydzielić kolejną strukturę 100 MB milisekundę później i oczekiwać, że ogólne użycie pamięci pozostanie takie samo.

Nie dotyczy to śmiecia. Systemy odśmiecania mają pewne opóźnienie w zwróceniu nieużywanej pamięci do sterty, co może być znaczące. Jeśli Twoja struktura 100 MB wykracza poza zakres, a milisekunda później program konfiguruje kolejną strukturę 100 MB, możesz rozsądnie oczekiwać, że Twój system zużyje 200 MB na krótki okres. Ten „krótki okres” może wynosić milisekundy lub sekundy w zależności od systemu, ale nadal występuje opóźnienie.

Jeśli korzystasz z komputera z pamięcią RAM i pamięcią wirtualną, oczywiście nigdy tego nie zauważysz. Jeśli jednak korzystasz z systemu z bardziej ograniczonymi zasobami (np. System osadzony lub telefon), musisz wziąć to na poważnie. Jest to nie tylko teoretyczne - osobiście widziałem, że stwarza to problemy (jak w przypadku awarii urządzenia) podczas pracy na systemie WinCE przy użyciu .NET Compact Framework i rozwoju w C #.

Pytanie zakłada, że ​​dealokacja jest czymś, co programista powinien wywnioskować z innych części kodu źródłowego. To nie jest. „W tym momencie programu odwołanie do pamięci FOO nie jest już przydatne” to informacja znana tylko w umyśle programisty, dopóki nie zostanie zakodowana w (w językach proceduralnych) instrukcja dealokacji.

Teoretycznie nie różni się niczym od żadnej innej linii kodu. Dlaczego kompilatory nie wstawiają automatycznie „W tym momencie programu sprawdź rejestr BAR dla wejścia” lub „jeśli wywołanie funkcji zwraca wartość niezerową, wyjdź z bieżącego podprogramu” ? Z punktu widzenia kompilatora przyczyną jest „niekompletność”, jak pokazano w tej odpowiedzi . Ale każdy program cierpi z powodu niekompletności, gdy programista nie powiedział mu wszystkiego, co wie.

W prawdziwym życiu zwalnianie to chrząknięcie lub bojler; nasze mózgi wypełniają je automatycznie i narzekają na to, a sentencja „kompilator mógłby to zrobić równie dobrze lub lepiej” jest prawdą. Teoretycznie jednak tak nie jest, chociaż na szczęście inne języki dają nam większy wybór teorii.

Co jest zrobione: istnieje odśmiecanie i są kompilatory wykorzystujące liczenie referencji (Objective-C, Swift). Ci, którzy liczą odniesienia, potrzebują pomocy programisty, unikając silnych cykli odniesienia.

Prawdziwa odpowiedź „dlaczego” jest to, że twórcy kompilatora nie zorientowali się w sposób, który jest wystarczająco dobry i wystarczająco szybko, by działał w kompilator. Ponieważ autorzy kompilatorów są zazwyczaj dość inteligentni, można stwierdzić, że bardzo, bardzo trudno jest znaleźć sposób wystarczająco dobry i wystarczająco szybki.

Jednym z powodów, dla których jest to bardzo, bardzo trudne, jest oczywiście niezdecydowanie. W informatyce, gdy mówimy o „rozstrzygalności”, mamy na myśli „podjęcie właściwej decyzji”. Ludzcy programiści mogą oczywiście z łatwością zdecydować, gdzie należy zwolnić pamięć, ponieważ nie ograniczają się do właściwych decyzji. I często podejmują błędne decyzje.

W językach takich jak C programista powinien wstawiać połączenia za darmo. Dlaczego kompilator nie robi tego automatycznie?

Ponieważ czas życia bloku pamięci jest decyzją programisty, a nie kompilatora.

Otóż ​​to. Jest to konstrukcja C. Kompilator nie może wiedzieć, jaki był zamiar przydzielenia bloku pamięci. Ludzie mogą to zrobić, ponieważ znają cel każdego bloku pamięci i kiedy ten cel jest realizowany, aby można go było uwolnić. To część projektu pisanego programu.

C jest językiem niskiego poziomu, więc przypadki przekazywania bloku pamięci do innego procesu lub nawet do innego procesora są dość częste. W skrajnym przypadku programista może celowo przydzielić część pamięci i nigdy więcej jej nie używać, aby wywrzeć presję na pamięć na inne części systemu. Kompilator nie ma możliwości sprawdzenia, czy blok jest nadal potrzebny.

W językach takich jak C programista powinien wstawiać połączenia za darmo. Dlaczego kompilator nie robi tego automatycznie?

W C i wielu innych językach istnieje możliwość ułatwienia kompilatorowi wykonania tej czynności w tych przypadkach, w których w czasie kompilacji jest jasne, kiedy należy to zrobić: użycie zmiennych o automatycznym czasie trwania (tj. Zwykłe zmienne lokalne) . Kompilator odpowiada za zapewnienie wystarczającej ilości miejsca na takie zmienne oraz za zwolnienie tej przestrzeni po zakończeniu (dobrze zdefiniowanego) okresu życia.

Ponieważ tablice o zmiennej długości są cechą C od C99, obiekty o automatycznym czasie trwania służą zasadniczo wszystkim funkcjom w C, które pełnią dynamicznie przydzielane obiekty o obliczalnym czasie trwania. W praktyce oczywiście implementacje języka C mogą nakładać znaczne praktyczne ograniczenia na użycie VLA - tzn. Ich rozmiar może być ograniczony w wyniku przydzielenia na stosie - ale jest to kwestia implementacji, a nie kwestia projektu językowego.

Tymi obiektami, których zamierzone użycie wyklucza nadanie im automatycznego czasu trwania, są dokładnie te, których czasu życia nie można ustalić w czasie kompilacji.