Garbage collection

Garbage collection stop-and-copy într-o arhitectură Lisp: Memoria este împărțită în memorie liberă și memorie de lucru; obiectele noi se alocă în cea de a doua. Când ea este plină (ilustrat), se face garbage collection: Toate structurile de date încă folosite sunt localizate prin trasarea pointerilor și se copiază în locații consecutive din memoria liberă.

După aceea, conținutul memoriei de lucru este golit în favoarea copiei compactate, iar cele două zone își schimbă rolurile între ele (ilustrat).

În ingineria software, garbage collection (GC; literalmente din engleză, strângerea gunoiului) este o formă de gestiune automată a memoriei^⁠(d). Garbage collectorul încearcă să reelibereze memoria care fusese alocată de program, dar care nu mai este referențiată; asemenea memorie este numită garbage^⁠(d) (lit. gunoi). Garbage collection a fost inventat de informaticianul american John McCarthy prin 1959 pentru a simplifica gestiunea manuală a memoriei din Lisp.

Garbage collection degrevează programatorul de munca de gestiune manuală a memoriei^⁠(d), anume de obligația de a specifica ce obiecte și când să fie dealocate pentru a elibera memoria sistemului. Există și alte tehnici similare, ca alocarea stivei^⁠(d), inferența pe regiuni^⁠(d), și proprietatea memoriei, care pot fi folosite singure sau în combinație. Garbage collection poate ocupa o durată semnificativă de timp de procesare, și poate afecta performanța^⁠(d).

Alte resurse decât memoria, cum ar fi sockeții de rețea^⁠(d), handle-urile^⁠(d) de baze de date, ferestrele^⁠(d), descriptorii de fișier și de dispozitive, nu sunt de regulă gestionați prin garbage collection, ci prin alte metode (cum ar fi destructorii^⁠(d)). Unele astfel de metode fac și dealocări de memorie

Generalități

Multe limbaje de programare necesită garbage collection, fie ca parte a specificației limbajului^⁠(d) (ca RPL^⁠(d), Java, C#, D, Go, și cele mai multe limbaje de scripting^⁠(d)) sau efectiv pentru implementarea practică (ca limbajele formale în genul calculului lambda^⁠(d)). Ele se numesc limbaje garbage-collected. Alte limbaje, cum ar fi C și C++, au fost proiectate pentru a fi folosite cu gestiune manuală a memoriei, dar au disponibile implementări garbage-collected. Alte limbaje, ca Ada, Modula-3^⁠(d), și C++/CLI^⁠(d), permit coexistența gestiunii manuale a memoriei cu garbage collection în aceeași aplicație, folosind heapuri^⁠(d) separate pentru obiectele gestionate manual și cele colectate automat. Altele, ca D, sunt garbage-collected, dar permit utilizatorului să șteargă manual obiecte sau chiar să dezactiveze complet garbage collection dacă există constrângeri de viteză.

Deși multe limbaje integrează GC în compilator și în sistemul de runtime^⁠(d), există și sisteme GC post-hoc, cum ar fi Automatic Reference Counting^⁠(d) (ARC). Unele din aceste sisteme de GC post-hoc nu necesită recompilare.

Avantaje

GC degrevează programatorul de sarcina de a dealoca manual memorie. Aceasta ajută la evitarea unor tipuri de erori:

• Pointeri liberi, care apar atunci când o bucată de memorie este eliberată, dar mai există pointeri^⁠(d) la ea, și unul din acești pointeri este dereferențiat. În acel moment, memoria ar putea să fi fost reatribuită altor scopuri, ceea ce duce la rezultate imprevizibile.
• Buguri de dublă eliberare, care apar când programul încearcă să elibereze o regiune de memorie deja eliberată, și care potențial fusese deja realocată.
• Anumite feluri de memory leak^⁠(d), în care un program nu eliberează memoria ocuptă cu obiecte nereferențiabile, ceea ce duce la epuizarea memoriei.

Dezavantaje

GC folosește resurse de calcul pentru a decide ce memorie să elibereze. Ca urmare, conveniența neadnotării manuale a ciclului de viață al obiectelor vine cu prețul unui overhead^⁠(d), care poate afecta performanța programului. Un articol științific publicat în 2005 trăgea concluzia că GC necesită de cinci ori mai multă memorie pentru a-și compensa propriul overhead și pentru a funcționa la fel de rapid ca programul ce folosește gestiune explicită a memoriei. Comparația se face însă cu un program generat prin inserarea de apeluri de dealocare cu un oracol^⁠(d), implementat prin strângerea de urme lăsate de programele rulate într-un profiler^⁠(d), și ca urmare programul este corect numai pentru o anumită rulare a lui. Interacțiunea cu efectele ierarhiei de memorie^⁠(d) poate face ca acest overhead să fie intolerabil în circumstanțe greu de prevăzut sau detectat prin testarea de rutină. Impactul asupra performanței a fost invocat de Apple ca motiv pentru neadoptarea garbage collectionului în iOS, deși era cea mai dorită funcționalitate.

Momentul când se face garbage collection efectiv poate fi și el imprevizibil, și se poate solda cu încetiniri (pauze pentru eliberarea/realocarea memoriei) răspândite printr-o sesiune. Încetinirile imprevizibile pot fi inacceptabile în mediile de timp real^⁠(d), în prelucrarea tranzacțiilor^⁠(d), sau în programe interactive. Garbage collectorii incrementali, concurenți și de timp real adresează aceste probleme, cu diferite alte penalități.

Strategii

Trasare

Garbage collection prin trasare este cel mai comun tip de garbage collection, în așa măsură încât, în lipsa specificării unei strategii, trasarea este cea considerată implicită. Strategia de ansamblu constă în a determina care obiecte trebuie colectate prin trasarea obiectelor la care se poate ajunge printr-un lanț de referințe de la anumite obiecte-rădăcină. Restul se consideră gunoi și se colectează. Există însă numeroși algoritmi folosiți în implementări, cu complexitate și caracteristici de performanță foarte variate.

Numărarea referințelor

Garbage collection prin numărarea referințelor constă în ținerea unei evidențe a referințelor către fiecare obiect. Gunoiul se identifică prin obiectele cu zero referințe. Numărul referințelor la un obiect se incrementează la crearea unei referințe și se decrementează la distrugerea ei. Când numărătoarea ajunge la zero, memoria obiectului este recuperată.

Ca în cazul gestiunii manuale a memoriei, și spre deosebire de strategia de trasare, numărărea referințelor garantează că obiectele sunt distruse imediat ce se distruge ultima referință la ele, și de regulă accesează memorie care este ori în cache-ul prcesorului^⁠(d), ori în obiecte de eliberat, ori direct referențiată de acestea, și ca urmare tinde să nu aibă efecte laterale negative asupra cache-ului procesorului și operațiunilor de memorie virtuală^⁠(d).

Numărarea referințelor are mai multe dezavantaje; ele pot fi în general rezolvate sau ameliorate de algoritmi mai sofisticați:

Ciclurile

Dacă două sau mai multe obiecte se referă unul la altul, atunci ele creează un ciclu în graful de referințe, cu rezultatul că niciunul nu va fi colectat întrucât referințele ciclice între ele nu lasă numărul referințelor să ajungă niciodată la zero. Unele sisteme de garbage collection care folosesc numărarea referințelor (ca cel din CPython^⁠(d)) folosesc anumiți algoritmi specifici de detecție a ciclurilor pentru a trata problema. O altă strategie este folosirea referințelor slabe^⁠(d) pentru „backpointerii” care creează cicluri. În numărarea referințelor, o referință slabă este similară unei referințe slabe în strategia de trasare. Este un tip special de referențiere a cărui existență nu incrementează numărătoarea de referințe. Mai mult, o referință slabă se transformă în null dacă obiectul-destinație devine gunoi, și nu este lăsată astfel să trimită în spațiu de memorie nealocat.

Overheadul de spațiu

Numărarea referințelor necesită alocarea de spațiu sumplimentar de memorie pentru stocarea numărului de referințe. Numărătoarea poate fi stocată adiacent memoriei obiectului sau într-un tabel lateral în altă parte, dar în orice caz, fiecare obiect numărat impune folosirea de spațiu adițional pentru numărul de referințe. Pentru aceasta, de obicei se folosește un spațiu de memorie cu dimensiunea unui pointer fără semn, adică fiecărui obiect trebuie să i se aloce un spațiu de 32 sau 64 de biți pentru numărarea referințelor. Pe unele sisteme, acest overhead poate fi ameliorat prin folosirea unui pointer etichetat^⁠(d) pentru a stoca numărul de referințe în zonele neutilizate de memoria obiectului. Adesea, o arhitectură nu permite de obicei programelor să acceseze întregul spațiu de adrese de memorie care ar putea fi stocat și adresat cu pointeri de dimensiunea nativă a arhitecturii; un anumit număr de biți mai semnificativi din spațiul de adresă fie se ignoră, fie trebuie să fie zero. Dacă un obiect are un pointer către o locație, numărătoarea referințelor se poate stoca în părțile neutilizate din pointer. De exemplu, fiecare obiect din Objective-C^⁠(d) are un pointer către clasa lui la începutul memoriei sale; pe arhitectura ARM64^⁠(d) în iOS 7, 19 biți neutilizați din acest pointer la clasă sunt folosiți pentru stocarea numărului de referințe al obiectului.

Overheadul operațional (incrementarea și decrementarea)

În implementările naive, fiecare atribuire a unei referințe și fiecare referință care iese din sfera de referențiere necesită adesea modificări ale unui numărător de referințe sau mai multora. Într-un caz comun însă, când o referință se copiază dintr-o variabilă din sfera exterioară într-una din sfera interioară, în așa fel încât durata de viață a celei interioare este mărginită de durata de viață a celei exterioare, atunci incrementarea referinței se poate elimina. Variabila exterioară „deține” referința. În limbajul de programare C++, această technică este implementată și este demonstrată prin folosirea referințelor const. Numărarea referințelor în C++ se implementează de obicei folosind „pointeri smart^⁠(d)” ai căror constructori, destructori, și operatori de atribuire gestionează referințele. Un pointer smart poate fi dat ca referință unei funcții, ceea ce evită nevoia de a construi prin copiere un nou pointer smart (care ar crește numărătoarea referințelor la intrarea în funcție și ar decrementa-o la ieșire). În schimb, funcția primește o referință la pointerul smart, care este produsă cu costuri mici. Metoda Deutsch-Bobrow de numărare a referințelor profită de faptul că cele mai multe actualizări ale numărătorii referințelor sunt generate de fapt de referințe stocate în variabile locale. Acestea sunt ingorate, și se numără doar cele din heap, dar înainte ca un obiect cu zero referințe să poată fi șters, sistemul trebuie să verifice că nu mai există și altă referință. Se poate obține și o scădere suplimentară a overheadului actualizărilor numărătorii prin coalescența actualizărilor, introdusă de Levanoni și Petrank^⁠(d). În cazul unui pointer care este actualizat de mai multe ori într-un interval dat de execuție. Trimite întâi la un obiect O1, apoi la O2, și tot așa până la finalul intervalului când trimite la obiectul On. Un algoritm de numărarea referințelor ar executa în mod tipic rc(O1)--, rc(O2)++, rc(O2)--, rc(O3)++, rc(O3)--, ..., rc(On)++. Dar cele mai multe din aceste actualizări sunt redundante. Pentru ca numărătoarea referințelor să fie corect evaluată la finalul intervalului, trebuie să se efectueze de fapt doar rc(O1)-- și rc(On)++. Levanoni și Petrank au măsurat o eliminare a peste 99% din actualizările numărătorilor în teste de rulare tipice ale unor aplicații Java.

Necesitatea atomicității

Când se folosesc într-un mediu multithread, aceste modificări (incrementarea și decrementare) trebuie să fie operațiuni atomice^⁠(d) cum este compare-and-swap^⁠(d), cel puțin pentru orice obiecte care nu sunt partajate, sau potențial partajate între mai multe fire de execuție. Operațiunile atomice sunt costisitoare pe un multiprocesor, și devin și mai costisitoare dacă trebuie emulate de algoritmi software. Această problemă se poate evita prin adăugarea de numărări de referințe pe fir de execuție, sau pe CPU, accesând numărătoarea globală doar când cele locale devin zero sau se schimbă de la zero (sau, alternativ, folosind un arbore binar de numărări ale referințelor, sau chiar renunțând la distrugerea deterministă în schimbul absenței totale a unei numărători globale a referințelor), dar aceasta adaugă un overhead de memorie important și tinde să fie utilă doar în cazuri speciale (se folosește, de exemplu, la numărarea referințelor în modulele de kernel Linux). Coalescența actualizărilor realizată de Levanoni și Petrank se poate folosi și pentru a elimina toate operațiunile atomice din bariera de scriere. Numărătoarele nu se actualizează niciodată de către firele de execuție în cursul rulării programului. Ele sunt modificate doar de firul colector care se execută ca un singur fir adițional fără sincronizare. Această metodă poate fi folosită ca mecanism stop-the-world pentru programe paralele, dar și cu un colector concurent de numărare a referințelor.

Rularea în timp real

Implementările naive ale numărării referințelor nu furnizează de obicei comportament de timp real, deoarece orice atribuire de pointer poate determina eliberarea recursivă a unui număr de obiecte mărginit doar de cantitatea totală de memorie alocată în timp ce firul de execuție nu poat efectua alte operațiuni. Această problemă poate fi evitată prin delegarea eliberării obiectelor nereferențiate către alte fire de execuție, cu costul overheadului suplimentar.

Analiza de escape

Analiza de escape^⁠(d) este o tehnică aplicabilă la momentul compilării, și care poate converti alocările pe heap^⁠(d) în alocări pe stivă^⁠(d), reducând astfel cantitatea de garbage collection care trebuie făcută. Această analiză determină dacă un obiect alocat în interiorul unei funcții este accesibil în afara ei. Dacă se găsește că o alocare funcție-locală este accesibilă altei funcții sau altui fir de execuție, se spune că alocarea reușește să „scape” (escape) și deci nu poate fi făcută pe stivă. Altfel, obiectul poate fi alocat direct pe stivă și eliberat când funcția returnează, scurtcircuitând heapul și costurile asociate gestiunii memoriei în acest caz.

Disponibilitate

În general, limbajele de programare de nivel mai înalt^⁠(d) sunt mai probabil să aibă garbage collection drept caracteristică standard. În unele limbaje cărora le lipsește garbage collection built-in, el poate fi adăugat printr-o bibliotecă, cum este cazul cu garbage collectorul Boehm^⁠(d) pentru C și C++.

Cele mai multe limbaje funcționale, ca ML, Haskell, și APL, au garbage collection built in. Lisp se remarcă drept primul limbaj funcțional și primul limbaj care a adăugat RPL (programming language).

Alte limbaje dinamice, ca Ruby și Julia^⁠(d) (dar nu și Perl 5 sau PHP înainte de versiunea 5.3, ambele care folosesc numărarea referințelor), JavaScript și ECMAScript tind să folosească GC. Limbajele de programare orientată obiect ca Smalltalk^⁠(d), ooRexx^⁠(d), RPL^⁠(d) și Java furnizează de obicei garbage collection integrat. Excepții notabile sunt C++ și Delphi, care au destructori^⁠(d).

BASIC

BASIC și Logo^⁠(d) au folosit adesea garbage collection pentru tipurile de date variabile, cum ar fi șirurile de caractere și listele, pentru a nu complica viața programatorilor cu detaliile de gestiunea memoriei. Pe Altair 8800, programele cu multe variabile de tip șir de caractere și cu spațiu redus de memorie aveau pauze lungi pentru garbage collection. La fel, garbage collectionul interpretorului Applesoft BASIC^⁠(d) scanează repetat descriptorii de șiruri căutând șirul cu adresa cea mai mare pentru a-l compacta spre memoria superioară, cu performanțe de $O(n^{2})$ și pauze ce durau de la câteva secunde la câteva minute. Un înlocuitor de garbage collector pentru Applesoft BASIC realizat de Randy Wigginton^⁠(d) identifica un grup de șiruri la fiecare trecere prin heap, reducând dramatic durata colectării. BASIC.SYSTEM, lansat cu ProDOS^⁠(d) în 1983, oferă un garbage collector mult mai rapid.

C și C++

C nu a oferit niciodată oficial suport pentru garbage collection. C++ a adăugat garbage collection în C++11 la biblioteca standard, dar în C++23 acesta a fost eliminat deoarece niciun compilator nu implementa suport pentru această facilitate. Caracteristicile care făceau parte din aceasta erau legate de siguranța pointerilor.

Deși suportul pentru garbage collection din biblioteca standard a fost eliminat, se pot folosi totuși unele garbage collectors cum ar fi Boehm garbage collector^⁠(d) (pentru C și C++). Boehm GC folosește garbage collection prin trasare. Se poate folosi și în modul leak detection, în care gestiunea memoriei este tot manuală, dar pot fi detectate și raportate erorile ce duc la scurgeri în memorie și la duble dealocări. Se poate folosi prin headerul <gc.h>.

Distrugerile manuale de obiecte pot fi abstractizate în C++ folosind idiomul „resource acquisition is initialization” (RAII) și pointerii smart^⁠(d). std::unique_ptr leagă durata de viață de ownership, în vreme ce std::shared_ptr folosește numărarea referințelor pentru a determina durata de viață. std::weak_ptr poate fi folosit pentru obține un pointer fără a crește numărarea referințelor. Spre deosebire de garbage collection, RAII este determinist.

Objective-C

Objective-C^⁠(d) nu avea, prin tradiție, garbage collection, dar după lansarea lui OS X 10.5 în 2007, Apple a introdus garbage collection pentru Objective-C 2.0, folosind un colector de runtime dezvoltat în cadrul proiectului. Cu lansarea în 2012 a lui OS X 10.8, garbage collection a fost înlocuit cu numărătorul automat de referințe^⁠(d) (ARC) that din LLVM^⁠(d), introdus în OS X 10.7. Din May 2015 însă, Apple a interzis utilizarea de garbage collection pentru noile aplicații OS X din App Store. Pentru iOS, garbage collection nu a fost introdus niciodată din cauza problemelor de performanță și timp de răspuns al aplicațiilor; iOS folosește, în schimb, ARC.

Medii limitate

Garbage collection se folosește rar în sistemele embedded sau de timp real din cauza nevoii lor de control foarte strict asupra utilizării unor resurse limitate. S-au dezboltat însă și garbage collectors compatibile cu multe sisteme limitate. Microsoft .NET Micro Framework^⁠(d), .NET nanoFramework și Java Platform, Micro Edition^⁠(d) sunt platforme de software embedded care, ca și rudele lor mai mari, includ garbage collection.

Java

Printre multiplele garbage collectors disponibile în mașinile virtuale Java^⁠(d) OpenJDK^⁠(d) (JVM) se numără:

• Serial
• Paralel
• CMS (Concurrent Mark Sweep)
• G1 (Garbage-First)
• ZGC (Z Garbage Collector)
• Epsilon
• Shenandoah
• GenZGC (Generational ZGC)
• GenShen (Generational Shenandoah)
• IBM Metronome (doar în IBM OpenJDK)
• SAP (doar în SAP OpenJDK)
• Azul C4 (Continuously Concurrent Compacting Collector) (doar în OpenJDK de la Azul Systems^⁠(d))

Utilizarea la compilare

Garbage collection la compilare este o formă de analiză statică^⁠(d) ce permite reutilizarea și recuperarea memoriei pe baza unor invarianți cunoscuți la compilare.

Această formă de garbage collection a fost studiată în limbajul de programare Mercury^⁠(d), și a fost foarte folosit după introducerea automatic reference counterului^⁠(d) (ARC) din LLVM^⁠(d) în ecosistemul Apple (iOS și OS X) în 2011.

Sisteme de timp real

S-au dezvoltat și garbage collectors Incrementale, concurente, și de timp real, de exemplu de către Henry Baker^⁠(d) și Henry Lieberman^⁠(d).

În algoritmul lui Baker, alocarea se face în câte o jumătate a unei anumite regiuni de memorie. Când ea se umple pe jumătate, se efectuează un garbage collection prin care obiectele vii se mută în cealaltă jumătate, iar celelalte se dealocă implicit. Programul care rulează („mutatorul”) trebuie să verifice dacă orice obiect referențiat este în jumătatea corectă, și dacă nu, să-l mute, în timp ce un task de fundal caută toate obiectele.

Schemele de garbage collection generațional se bazează pe observația empirică că cele mai multe obiecte mor tinere. În garbage collection generațional, memoria este împărțită în două sau mai multe regiuni de alocare (generații), care rămân separate pe baza vârstei obiectelor. Obiectele noi se creează în generația „tânără”, care este colectată regulat, iar când o generație este plină, obiectele care sunt încă referențiate din regiunile mai vechi se copiază în următoarea generație mai veche. Ocazional, se efectuează și scanări complete.

Unele arhitecturi de calculatoare cu limbaje de nivel înalt cuprind suport hardware pentru garbage collection în timp real.

Lectură suplimentară

• Jones, Richard; Hosking, Antony; Moss, J. Eliot B. (16 august 2011). The Garbage Collection Handbook: The Art of Automatic Memory Management. CRC Applied Algorithms and Data Structures Series. Chapman and Hall^⁠(d) / CRC Press / Taylor & Francis Ltd^⁠(d). ISBN 978-1-4200-8279-1.  (511 pages)
• Jones, Richard; Lins, Rafael (12 iulie 1996). Garbage Collection: Algorithms for Automatic Dynamic Memory Management (ed. 1). Wiley. ISBN 978-0-47194148-4.  (404 pages)
• Communications of the ACM^⁠(d). 10 (8): 501–506. Arhivat din original la 22 ianuarie 2021. 
• Wilson, Paul R. (1992). „Uniprocessor Garbage Collection Techniques”. Memory Management. Proceedings of the International Workshop on Memory Management (IWMM 92). Lecture Notes in Computer Science. 637. Springer-Verlag. pp. 1–42. doi:10.1007/bfb0017182. ISBN 3-540-55940-X. 
• Wilson, Paul R.; Johnstone, Mark S.; Neely, Michael; Boles, David (1995). „Dynamic Storage Allocation: A Survey and Critical Review”. Memory Management. Proceedings of the International Workshop on Memory Management (IWMM 95). Lecture Notes in Computer Science. 986 (ed. 1). pp. 1–116. doi:10.1007/3-540-60368-9_19. ISBN 978-3-540-60368-9.