class=skin-invert-image|miniatura|400x400px|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ă. class=skin-invert-image|miniatura|400x400px|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, (GC; literalmente din engleză, strângerea gunoiului) este o formă de . ul încearcă să reelibereze memoria care fusese alocată de program, dar care nu mai este referențiată; asemenea memorie este numită ( gunoi). a fost inventat de informaticianul american John McCarthy prin 1959 pentru a simplifica gestiunea manuală a memoriei din Lisp.

degrevează programatorul de munca de , 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 , , și proprietatea memoriei, care pot fi folosite singure sau în combinație. poate ocupa o durată semnificativă de timp de procesare, și poate afecta .

Alte resurse decât memoria, cum ar fi , de baze de date, , descriptorii de fișier și de dispozitive, nu sunt de regulă gestionați prin , ci prin alte metode (cum ar fi ). Unele astfel de metode fac și dealocări de memorie

Generalități Multe limbaje de programare necesită , fie ca parte a (ca , Java, C#, D, Go, și cele mai multe ) sau efectiv pentru implementarea practică (ca limbajele formale în genul ). Ele se numesc limbaje . 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 . Alte limbaje, ca Ada, , și , permit coexistența gestiunii manuale a memoriei cu în aceeași aplicație, folosind separate pentru obiectele gestionate manual și cele colectate automat. Altele, ca D, sunt , dar permit utilizatorului să șteargă manual obiecte sau chiar să dezactiveze complet dacă există constrângeri de viteză.

Deși multe limbaje integrează GC în compilator și în , există și sisteme GC post-hoc, cum ar fi (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ă 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 , î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 , 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 , implementat prin strângerea de urme lăsate de programele rulate într-un , și ca urmare programul este corect numai pentru o anumită rulare a lui. Interacțiunea cu efectele 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 ului în iOS, deși era cea mai dorită funcționalitate.

Momentul când se face 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 , în , sau în programe interactive. ii incrementali, concurenți și de timp real adresează aceste probleme, cu diferite alte penalități.

Strategii

Trasare prin trasare este cel mai comun tip de , î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 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 , 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 .

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 care folosesc numărarea referințelor (ca cel din ) folosesc anumiți algoritmi specifici de detecție a ciclurilor pentru a trata problema. O altă strategie este folosirea 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 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 are un pointer către clasa lui la începutul memoriei sale; pe arhitectura î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 „” 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 . Î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 cum este , 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