Editing Garbage collection (computer science)

{{Short description|Form of automatic memory management}}
{{About|garbage collection in memory management|garbage collection in a solid-state drive|Garbage collection (SSD)}}
{{Use dmy dates|date=April 2019|cs1-dates=y}}
{{Use list-defined references|date=July 2022}}
[[File:Structure and Interpretation of Computer Programs p.764a.gif|thumb|400px|Stop-and-copy garbage collection in a [[Lisp (programming language)|Lisp architecture]]:<ref name="Abelson-Sussman_2016"/> Memory is divided into ''working'' and ''free'' memory; new objects are allocated in the former. When it is full (depicted), garbage collection is performed: All data structures still in use are located by pointer tracing and copied into consecutive locations in free memory.]]
[[File:Structure and Interpretation of Computer Programs p.764b.gif|thumb|400px|After that, the working memory contents is discarded in favor of the compressed copy, and the role of ''working'' and ''free'' memory are exchanged (depicted).]]

In [[computer science]], '''garbage collection''' ('''GC''') is a form of automatic [[memory management]].<ref name="techtarget">{{Cite web |title=What is garbage collection (GC) in programming? |url=https://www.techtarget.com/searchstorage/definition/garbage-collection |access-date=2024-06-21 |website=Storage |language=en}}</ref> The ''garbage collector'' attempts to reclaim memory that was allocated by the program, but is no longer referenced; such memory is called ''[[garbage (computer science)|garbage]]''. Garbage collection was invented by American computer scientist [[John McCarthy (computer scientist)|John McCarthy]] around 1959 to simplify manual memory management in [[Lisp (programming language)|Lisp]].<ref name="McCarthy_1960"/>

Garbage collection relieves the programmer from doing [[manual memory management]], where the programmer specifies what objects to de-allocate and return to the memory system and when to do so.<ref name="techtarget"/> Other, similar techniques include [[stack-based memory allocation|stack allocation]], [[region inference]], and memory ownership, and combinations thereof. Garbage collection may take a significant proportion of a program's total processing time, and affect [[computer performance|performance]] as a result.

Resources other than memory, such as [[network socket]]s, database [[Handle (computing)|handle]]s, [[Window (computing)|window]]s, [[File (computing)|file]] descriptors, and device descriptors, are not typically handled by garbage collection, but rather by other [[Method (computer programming)|method]]s (e.g. [[Destructor (computer programming)|destructor]]s). Some such methods de-allocate memory also.

== Overview ==
{{More citations needed section|date=July 2014}}
Many [[programming language]]s require garbage collection, either as part of the [[language specification]] (e.g., [[RPL (programming language)|RPL]], [[Java (programming language)|Java]], [[C Sharp (programming language)|C#]], [[D (programming language)|D]],<ref name="Mars"/> [[Go (programming language)|Go]], and most [[scripting language]]s) or effectively for practical implementation (e.g., formal languages like [[lambda calculus]]).<ref>{{Cite web |last=Heller |first=Martin |date=2023-02-03 |title=What is garbage collection? Automated memory management for your programs |url=https://www.infoworld.com/article/3685493/what-is-garbage-collection-automated-memory-management-for-your-programs.html |access-date=2024-06-21 |website=InfoWorld |language=en}}</ref> These are said to be ''garbage-collected languages''. Other languages, such as [[C (programming language)|C]] and [[C++]], were designed for use with manual memory management, but have garbage-collected implementations available. Some languages, like [[Ada (programming language)|Ada]], [[Modula-3]], and [[C++/CLI]], allow both garbage collection and [[manual memory management]] to co-exist in the same application by using separate [[Heap (data structure)|heap]]s for collected and manually managed objects. Still others, like [[D (programming language)|D]], are garbage-collected but allow the user to manually delete objects or even disable garbage collection entirely when speed is required.<ref>{{Cite web |date=2020-01-16 |title=A Guide to Garbage Collection in Programming |url=https://www.freecodecamp.org/news/a-guide-to-garbage-collection-in-programming/ |access-date=2024-06-21 |website=freeCodeCamp.org |language=en}}</ref>

Although many languages integrate GC into their [[compiler]] and [[runtime system]], ''post-hoc'' GC systems also exist, such as [[Automatic Reference Counting]] (ARC). Some of these ''post-hoc'' GC systems do not require recompilation.<ref>{{Cite web |title=Garbage Collection - D Programming Language |url=https://dlang.org/spec/garbage.html |access-date=2022-10-17 |website=dlang.org}}</ref> 

=== Advantages ===
{{Unreferenced section|date=April 2021}}
GC frees the programmer from manually de-allocating memory. This helps avoid some kinds of [[bug (software)|error]]s:<ref>{{Cite web |title=Garbage Collection |url=https://rebelsky.cs.grinnell.edu/Courses/CS302/99S/Presentations/GC/ |access-date=2024-01-13 |website=rebelsky.cs.grinnell.edu}}</ref>

* ''[[Dangling pointer]]s'', which occur when a piece of memory is freed while there are still [[pointer (computer programming)|pointer]]s to it, and one of those pointers is [[dereference operator|dereferenced]]. By then the memory may have been reassigned to another use, with unpredictable results.<ref>{{Cite web |last=Heller |first=Martin |date=2023-02-03 |title=What is garbage collection? Automated memory management for your programs |url=https://www.infoworld.com/article/3685493/what-is-garbage-collection-automated-memory-management-for-your-programs.html |access-date=2024-06-21 |website=InfoWorld |language=en}}</ref>
* ''Double free bugs'', which occur when the program tries to free a region of memory that has already been freed, and perhaps already been allocated again.
* Certain kinds of ''[[memory leak]]s'', in which a program fails to free memory occupied by objects that have become [[unreachable]], which can lead to memory exhaustion.<ref>{{Cite web|url=https://learn.microsoft.com/en-us/dotnet/standard/garbage-collection/fundamentals|title=Fundamentals of garbage collection {{!}} Microsoft Learn|author=[[Microsoft]]|date=28 February 2023 |access-date=2023-03-29}}</ref>

=== Disadvantages ===
GC uses computing resources to decide which memory to free. Therefore, the penalty for the convenience of not annotating object lifetime manually in the source code is [[overhead (computing)|overhead]], which can impair program performance.<ref name="Zorn_1993"/> A peer-reviewed paper from 2005 concluded that GC needs five times the memory to compensate for this overhead and to perform as fast as the same program using idealized explicit memory management. The comparison however is made to a program generated by inserting deallocation calls using an [[oracle machine|oracle]], implemented by collecting traces from programs run under a [[Profiling (computer programming)|profiler]], and the program is only correct for one particular execution of the program.<ref name="Hertz-Berger_2005"/> Interaction with [[memory hierarchy]] effects can make this overhead intolerable in circumstances that are hard to predict or to detect in routine testing. The impact on performance was given by Apple as a reason for not adopting garbage collection in [[iOS]], despite it being the most desired feature.<ref name="wwdc_2011"/>

The moment when the garbage is actually collected can be unpredictable, resulting in stalls (pauses to shift/free memory) scattered throughout a [[Session (computer science)|session]]. Unpredictable stalls can be unacceptable in [[real-time computing|real-time environment]]s, in [[transaction processing]], or in interactive programs. Incremental, concurrent, and real-time garbage collectors address these problems, with varying trade-offs.

== Strategies ==
=== Tracing ===
{{Main|Tracing garbage collection}}

[[Tracing garbage collection]] is the most common type of garbage collection, so much so that "garbage collection" often refers to tracing garbage collection, rather than other methods such as [[reference counting]]. The overall strategy consists of determining which objects should be garbage collected by tracing which objects are ''reachable'' by a chain of references from certain root objects, and considering the rest as garbage and collecting them. However, there are a large number of algorithms used in implementation, with widely varying complexity and performance characteristics.

=== Reference counting ===
{{Main|Reference counting}}
Reference counting garbage collection is where each object has a count of the number of references to it. Garbage is identified by having a reference count of zero. An object's reference count is incremented when a reference to it is created and decremented when a reference is destroyed. When the count reaches zero, the object's memory is reclaimed.<ref name="MS_2009"/>

As with manual memory management, and unlike tracing garbage collection, reference counting guarantees that objects are destroyed as soon as their last reference is destroyed, and usually only accesses memory which is either in [[CPU cache]]s, in objects to be freed, or directly pointed to by those, and thus tends to not have significant negative side effects on CPU cache and [[virtual memory]] operation.

There are a number of disadvantages to reference counting; this can generally be solved or mitigated by more sophisticated algorithms:

; Cycles: If two or more objects refer to each other, they can create a cycle whereby neither will be collected as their mutual references never let their reference counts become zero. Some garbage collection systems using reference counting (like the one in [[CPython]]) use specific cycle-detecting algorithms to deal with this issue.<ref name="Python_2008"/> Another strategy is to use [[weak reference]]s for the "backpointers" which create cycles. Under reference counting, a weak reference is similar to a weak reference under a tracing garbage collector. It is a special reference object whose existence does not increment the reference count of the referent object. Furthermore, a weak reference is safe in that when the referent object becomes garbage, any weak reference to it ''lapses'', rather than being permitted to remain dangling, meaning that it turns into a predictable value, such as a null reference.

; Space overhead (reference count): Reference counting requires space to be allocated for each object to store its reference count. The count may be stored adjacent to the object's memory or in a side table somewhere else, but in either case, every single reference-counted object requires additional storage for its reference count. Memory space with the size of an unsigned pointer is commonly used for this task, meaning that 32 or 64 bits of reference count storage must be allocated for each object. On some systems, it may be possible to mitigate this overhead by using a [[tagged pointer]] to store the reference count in unused areas of the object's memory. Often, an architecture does not actually allow programs to access the full range of memory addresses that could be stored in its native pointer size; a certain number of high bits in the address is either ignored or required to be zero. If an object reliably has a pointer at a certain location, the reference count can be stored in the unused bits of the pointer. For example, each object in [[Objective-C]] has a pointer to its [[class (computer programming)|class]] at the beginning of its memory; on the [[ARM64]] architecture using [[iOS 7]], 19 unused bits of this class pointer are used to store the object's reference count.<ref name="Ash_2013"/><ref name="Sealie_2013"/>

; Speed overhead (increment/decrement): In naive implementations, each assignment of a reference and each reference falling out of scope often require modifications of one or more reference counters. However, in a common case when a reference is copied from an outer scope variable into an inner scope variable, such that the lifetime of the inner variable is bounded by the lifetime of the outer one, the reference incrementing can be eliminated. The outer variable "owns" the reference. In the programming language C++, this technique is readily implemented and demonstrated with the use of <code>const</code> references. Reference counting in C++ is usually implemented using "[[smart pointer]]s"<ref name="Pibinger_2005"/> whose constructors, destructors, and assignment operators manage the references. A smart pointer can be passed by reference to a function, which avoids the need to copy-construct a new smart pointer (which would increase the reference count on entry into the function and decrease it on exit). Instead, the function receives a reference to the smart pointer which is produced inexpensively. The Deutsch-Bobrow method of reference counting capitalizes on the fact that most reference count updates are in fact generated by references stored in local variables. It ignores these references, only counting references in the heap, but before an object with reference count zero can be deleted, the system must verify with a scan of the stack and register that no other reference to it still exists. A further substantial decrease in the overhead on counter updates can be obtained by update coalescing introduced by Levanoni and [[Erez Petrank|Petrank]].<ref name="Levanoni-Petrank_2001"/><ref name="Levanoni-Petrank_2006"/> Consider a pointer that in a given interval of the execution is updated several times. It first points to an object <code>O1</code>, then to an object <code>O2</code>, and so forth until at the end of the interval it points to some object <code>On</code>. A reference counting algorithm would typically execute <code>rc(O1)--</code>, <code>rc(O2)++</code>, <code>rc(O2)--</code>, <code>rc(O3)++</code>, <code>rc(O3)--</code>, ..., <code>rc(On)++</code>. But most of these updates are redundant. In order to have the reference count properly evaluated at the end of the interval it is enough to perform <code>rc(O1)--</code> and <code>rc(On)++</code>. Levanoni and Petrank measured an elimination of more than 99% of the counter updates in typical Java benchmarks.

; Requires atomicity: When used in a [[thread (computing)|multithreaded]] environment, these modifications (increment and decrement) may need to be [[atomic operation]]s such as [[compare-and-swap]], at least for any objects which are shared, or potentially shared among multiple threads. Atomic operations are expensive on a multiprocessor, and even more expensive if they have to be emulated with software algorithms. It is possible to avoid this issue by adding per-thread or per-CPU reference counts and only accessing the global reference count when the local reference counts become or are no longer zero (or, alternatively, using a binary tree of reference counts, or even giving up deterministic destruction in exchange for not having a global reference count at all), but this adds significant memory overhead and thus tends to be only useful in special cases (it is used, for example, in the reference counting of Linux kernel modules). Update coalescing by Levanoni and Petrank<ref name="Levanoni-Petrank_2001"/><ref name="Levanoni-Petrank_2006"/> can be used to eliminate all atomic operations from the write-barrier. Counters are never updated by the program threads in the course of program execution. They are only modified by the collector which executes as a single additional thread with no synchronization. This method can be used as a stop-the-world mechanism for parallel programs, and also with a concurrent reference counting collector.

; Not real-time: Naive implementations of reference counting do not generally provide real-time behavior, because any pointer assignment can potentially cause a number of objects bounded only by total allocated memory size to be recursively freed while the thread is unable to perform other work. It is possible to avoid this issue by delegating the freeing of unreferenced objects to other threads, at the cost of extra overhead.

=== Escape analysis ===
{{Main|Escape analysis}}
[[Escape analysis]] is a compile-time technique that can convert [[heap allocation]]s to [[stack allocation]]s, thereby reducing the amount of garbage collection to be done. This analysis determines whether an object allocated inside a function is accessible outside of it. If a function-local allocation is found to be accessible to another function or thread, the allocation is said to "escape" and cannot be done on the stack. Otherwise, the object may be allocated directly on the stack and released when the function returns, bypassing the heap and associated memory management costs.<ref name="Salagnac-Yovine-Garbervetsky_2005"/>

== Availability ==
Generally speaking, [[high-level programming language|higher-level programming language]]s are more likely to have garbage collection as a standard feature. In some languages lacking built-in garbage collection, it can be added through a library, as with the [[Boehm garbage collector]] for C and C++.

Most [[functional programming language]]s, such as [[ML (programming language)|ML]], [[Haskell]], and [[APL (programming language)|APL]], have garbage collection built in. [[Lisp (programming language)|Lisp]] is especially notable as both the first [[functional programming language]] and the first language to introduce garbage collection.<ref name="Chisnall_2011"/>

Other dynamic languages, such as [[Ruby (programming language)|Ruby]] and [[Julia (programming language)|Julia]] (but not [[Perl]]&nbsp;5 or [[PHP]] before version 5.3,<ref name="PHP"/> which both use reference counting), [[JavaScript]] and [[ECMAScript]] also tend to use GC. [[Object-oriented programming]] languages such as [[Smalltalk]], [[Object REXX|ooRexx]], [[RPL (programming language)|RPL]] and [[Java (programming language)|Java]] usually provide integrated garbage collection. Notable exceptions are [[C++]] and [[Delphi (programming language)|Delphi]], which have [[Destructor (computer programming)|destructor]]s.

=== BASIC ===
[[BASIC]] and [[Logo (programming language)|Logo]] have often used garbage collection for variable-length data types, such as strings and lists, so as not to burden programmers with memory management details. On the [[Altair 8800]], programs with many string variables and little string space could cause long pauses due to garbage collection.<ref name="MITS_1977"/> Similarly the [[Applesoft BASIC]] interpreter's garbage collection algorithm repeatedly scans the string descriptors for the string having the highest address in order to compact it toward high memory, resulting in [[Big O notation|<math>O(n^2)</math>]] performance<ref name="Hacker"/> and pauses anywhere from a few seconds to a few minutes.<ref name="Little_1985"/> A replacement garbage collector for Applesoft BASIC by [[Randy Wigginton]] identifies a group of strings in every pass over the heap, reducing collection time dramatically.<ref name="Fast_1981"/> BASIC.SYSTEM, released with [[ProDOS]] in 1983, provides a windowing garbage collector for BASIC that is many times faster.<ref name="Worth_1984"/>

=== Objective-C ===
While the [[Objective-C]] traditionally had no garbage collection, with the release of [[OS&nbsp;X 10.5]] in 2007 [[Apple Inc.|Apple]] introduced garbage collection for [[Objective-C]]&nbsp;2.0, using an in-house developed runtime collector.<ref name="Leopard"/>
However, with the 2012 release of [[OS&nbsp;X 10.8]], garbage collection was deprecated in favor of [[LLVM]]'s [[Automatic Reference Counting|automatic reference counter]] (ARC) that was introduced with [[OS&nbsp;X 10.7]].<ref name="Siracusa_2011"/> Furthermore, since May 2015 Apple even forbade the usage of garbage collection for new OS&nbsp;X applications in the [[App Store (iOS)|App Store]].<ref name="Appleinsider_2015"/><ref name="Cichon_2015"/> For [[iOS]], garbage collection has never been introduced due to problems in application responsivity and performance;<ref name="wwdc_2011"/><ref name="Silva_2014"/> instead, iOS uses ARC.<ref name="Napier-Kumar_2012"/><ref name="Cruz_2012"/>

=== Limited environments ===
Garbage collection is rarely used on [[embedded computing|embedded]] or real-time systems because of the usual need for very tight control over the use of limited resources. However, garbage collectors compatible with many limited environments have been developed.<ref name="Fu-Hauser_2005"/> The Microsoft [[.NET Micro Framework]], .NET nanoFramework<ref name="nanoframework"/> and [[Java Platform, Micro Edition]] are embedded software platforms that, like their larger cousins, include garbage collection.

=== Java ===
{{main|Java virtual machine#Garbage collectors}}
Garbage collectors available in [[Java (software platform)|Java]] [[OpenJDK]]s virtual machine (JVM) include:
* Serial
* Parallel
* [[Concurrent mark sweep collector|CMS]] (Concurrent Mark Sweep)
* [[Garbage-first collector|G1]] (Garbage-First)
* ZGC (Z Garbage Collector)
* Epsilon
* Shenandoah
* GenZGC (Generational ZGC)
* GenShen (Generational Shenandoah)
* IBM Metronome (only in [[IBM]] OpenJDK)
* SAP (only in [[SAP]] OpenJDK)
* Azul C4 (Continuously Concurrent Compacting Collector)<ref name="Tene-Iyengar-Wolf_2011"/> (only in [[Azul Systems]] OpenJDK)

=== Compile-time use ===
Compile-time garbage collection is a form of [[static program analysis|static analysis]] allowing memory to be reused and reclaimed based on invariants known during compilation.

This form of garbage collection has been studied in the [[Mercury (programming language)|Mercury programming language]],<ref name="Mazur_2004"/> and it saw greater usage with the introduction of [[LLVM]]'s [[Automatic Reference Counting|automatic reference counter]] (ARC) into Apple's ecosystem (iOS and OS&nbsp;X) in 2011.<ref name="Napier-Kumar_2012"/><ref name="Cruz_2012"/><ref name="Appleinsider_2015"/>

=== Real-time systems ===
Incremental, concurrent, and real-time garbage collectors have been developed, for example by [[Henry Baker (computer scientist)|Henry Baker]] and by [[Henry Lieberman]].<ref name="Huelsbergen-Winterbottom_1998"/><ref name="IECC-GC"/><ref name="Lieberman-Hewitt_1983"/>

In Baker's algorithm, the allocation is done in either half of a single region of memory. When it becomes half full, a garbage collection is performed which moves the live objects into the other half and the remaining objects are implicitly deallocated. The running program (the 'mutator') has to check that any object it references is in the correct half, and if not move it across, while a background task is finding all of the objects.<ref name="Baker_1978"/>

[[Tracing garbage collection#Generational GC (ephemeral GC)|Generational garbage collection]] schemes are based on the empirical observation that most objects die young. In generational garbage collection, two or more allocation regions (generations) are kept, which are kept separate based on the object's age. New objects are created in the "young" generation that is regularly collected, and when a generation is full, the objects that are still referenced from older regions are copied into the next oldest generation. Occasionally a full scan is performed.

Some [[high-level language computer architecture]]s include hardware support for real-time garbage collection.

Most implementations of real-time garbage collectors use [[tracing garbage collection#Real-time garbage collection|tracing]].{{Citation needed|date=September 2019}} Such real-time garbage collectors meet [[hard real-time]] constraints when used with a real-time operating system.<ref name="McCloskey_2008"/>

== See also ==
{{Portal|Computer programming}}
* [[Destructor (computer programming)]]
* [[Dynamic dead-code elimination]]
* [[Smart pointer]]
* [[Virtual memory compression]]

== References ==
{{Reflist|refs=
<ref name="Abelson-Sussman_2016">{{cite book |title=Structure and Interpretation of Computer Programs |url=https://commons.wikimedia.org/wiki/File:Structure_and_Interpretation_of_Computer_Programs_(Second_Edition).pdf |author-first1=Harold |author-last1=Abelson |author-first2=Gerald Jay |author-last2=Sussman |author-first3=Julie |author-last3=Sussman |location=Cambridge, Massachusetts, US |publisher=[[MIT Press]] |edition=2nd |date=2016 |pages=734–736}}</ref>
<ref name="McCarthy_1960">{{cite journal |title=Recursive functions of symbolic expressions and their computation by machine, Part I |journal=Communications of the ACM |volume=3 |issue=4 |doi=10.1145/367177.367199 |date=1960 |author-last=McCarthy |author-first=John |s2cid=1489409 |pages=184–195 |url=http://www-formal.stanford.edu/jmc/recursive.html |access-date=2009-05-29|doi-access=free }}</ref>
<ref name="Mars">{{cite web |url=http://dlang.org/overview.html |title=Overview – D Programming Language |website=dlang.org |publisher=Digital Mars |access-date=2014-07-29}}</ref> 
<ref name="Zorn_1993">{{cite journal |citeseerx=10.1.1.14.1816 |author-first=Benjamin |author-last=Zorn |title=The Measured Cost of Conservative Garbage Collection |journal=Software: Practice and Experience |volume=23 |issue=7 |pages=733–756 |publisher=Department of Computer Science, [[University of Colorado Boulder]] |date=1993-01-22 |doi=10.1002/spe.4380230704 |s2cid=16182444}}</ref>
<ref name="Hertz-Berger_2005">{{cite book |chapter-url=https://people.cs.umass.edu/~emery/pubs/gcvsmalloc.pdf |archive-url=https://web.archive.org/web/20120402024350/http://people.cs.umass.edu/~emery/pubs/gcvsmalloc.pdf |archive-date=2012-04-02 |url-status=live |chapter=Quantifying the Performance of Garbage Collection vs. Explicit Memory Management |title=Proceedings of the 20th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications - OOPSLA '05 |pages=313–326 |author-first1=Matthew |author-last1=Hertz |author-first2=Emery D. |author-last2=Berger |date=2005 |access-date=2015-03-15 |doi=10.1145/1094811.1094836 |isbn=1-59593031-0 |s2cid=6570650}}</ref>
<ref name="wwdc_2011">{{cite web |url=https://developer.apple.com/devcenter/download.action?path=/wwdc_2011/adc_on_itunes__wwdc11_sessions__pdf/300developer_tools_kickoff.pdf |work=[[WWDC]] 2011 |title=Developer Tools Kickoff – session 300 |publisher=[[Apple, Inc.]] |date=2011-06-24 |access-date=2015-03-27 |archive-url=https://web.archive.org/web/20230904235123/https://docs.huihoo.com/apple/wwdc/2011/session_300__developer_tools_kickoff.pdf |archive-date=2023-09-04 |url-status=dead}}</ref>
<ref name="MS_2009">{{cite web |url=https://blogs.msdn.microsoft.com/abhinaba/2009/01/27/back-to-basics-reference-counting-garbage-collection/ |author=[[Microsoft]]|title=Reference Counting Garbage Collection|date=27 January 2009 |access-date=2023-03-29}}</ref><ref name="Python_2008">{{cite web |url=https://docs.python.org/release/2.5.2/ext/refcounts.html |access-date=2014-05-22 |date=2008-02-21 |title=Reference Counts |work=Extending and Embedding the Python Interpreter}}</ref> 
<ref name="Ash_2013">{{cite web |author-first=Mike |author-last=Ash |url=https://www.mikeash.com/pyblog/friday-qa-2013-09-27-arm64-and-you.html |title=Friday Q&A 2013-09-27: ARM64 and You |publisher=mikeash.com |access-date=2014-04-27}}</ref>
<ref name="Sealie_2013">{{cite web |url=http://www.sealiesoftware.com/blog/archive/2013/09/24/objc_explain_Non-pointer_isa.html |title=Hamster Emporium: [objc explain&#93;: Non-pointer isa |publisher=Sealiesoftware.com |date=2013-09-24 |access-date=2014-04-27}}</ref>
<ref name="Pibinger_2005">{{cite web |url=http://www.codeproject.com/Articles/10141/RAII-Dynamic-Objects-and-Factories-in-C#1 |title=RAII, Dynamic Objects, and Factories in C++ |author-first=Roland |author-last=Pibinger |date=2005-05-03 |orig-date=2005-04-17}}</ref>
<ref name="Levanoni-Petrank_2001">{{cite conference |author-first1=Yossi |author-last1=Levanoni |author-first2=Erez |author-last2=Petrank |author-link2=Erez Petrank |date=2001 |title=An on-the-fly reference-counting garbage collector for java |url=https://www.cs.technion.ac.il/~erez/Papers/refcount.ps |conference=[[OOPSLA]] 2001 |book-title=Proceedings of the 16th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications |pages=367–380 |doi=10.1145/504282.504309|url-access=subscription }}</ref>
<ref name="Levanoni-Petrank_2006">{{cite journal |author-first1=Yossi |author-last1=Levanoni |author-first2=Erez |author-last2=Petrank |author-link2=Erez Petrank |date=2006 |title=An on-the-fly reference-counting garbage collector for java |url=https://www.cs.technion.ac.il/~erez/Papers/refcount.ps |journal=ACM Trans. Program. Lang. Syst. |pages=31–69 |doi=10.1145/1111596.1111597 |volume=28 |citeseerx=10.1.1.15.9106 |s2cid=14777709}}</ref>
<ref name="Salagnac-Yovine-Garbervetsky_2005">{{Cite journal |author-first1=Guillaume |author-last1=Salagnac |author-first2=Sergio |author-last2=Yovine |author-first3=Diego |author-last3=Garbervetsky |date=2005-05-24 |title=Fast Escape Analysis for Region-based Memory Management |journal=[[Electronic Notes in Theoretical Computer Science]] |volume=131 |pages=99–110 |doi=10.1016/j.entcs.2005.01.026 |doi-access=free}}</ref>
<ref name="Chisnall_2011">{{Cite book |url=http://www.informit.com/articles/article.aspx?p=1671639 |title=Influential Programming Languages, Part 4: Lisp |author-last=Chisnall |author-first=David |date=2011-01-12}}</ref>
<ref name="PHP">{{cite web |url=http://php.net/manual/en/features.gc.performance-considerations.php |title=PHP: Performance Considerations |website=php.net |access-date=2015-01-14}}</ref>
<ref name="MITS_1977">{{cite web |title=Altair 8800 Basic 4.1 Reference Manual |url=http://vtda.org/docs/computing/MITS/MITS_Altair8800Basic4.1Reference_April1977.pdf |archive-url=https://web.archive.org/web/20210629013809/http://vtda.org/docs/computing/MITS/MITS_Altair8800Basic4.1Reference_April1977.pdf |archive-date=2021-06-29 |url-status=live |website=The Vintage Technology Digital Archive |access-date=2021-06-29 |page=108 |date=April 1977}}</ref>
<ref name="Hacker">{{cite web |title=I did some work to speed up string garbage collection under Applesoft... |url=https://news.ycombinator.com/item?id=26655648 |website=Hacker News |access-date=2021-06-29}}</ref>
<ref name="Little_1985">{{cite book |author-last=Little |author-first=Gary B. |title=Inside the Apple IIc |date=1985 |publisher=Brady Communications Co |location=Bowie, Md. |isbn=0-89303-564-5 |page=82 |url=http://hackzapple.org/scripts_php/index.php?menu=14&mod=8517283d55e912b0b5ac842147e28904a4a751d3&page=4 |access-date=2021-06-29}}</ref>
<ref name="Fast_1981">{{cite journal |title=Fast Garbage Collection |journal=[[Call-A.P.P.L.E.]] |date=January 1981 |pages=40–45}}</ref>
<ref name="Worth_1984">{{cite book |author-last=Worth |author-first=Don |title=Beneath Apple Pro DOS |date=1984 |publisher=Quality Software |location=Chatsworth, California, US |isbn=0-912985-05-4 |pages=2–6 |url=http://www.apple-iigs.info/doc/fichiers/beneathprodos.pdf |archive-url=https://web.archive.org/web/20081203160743/http://www.apple-iigs.info/doc/fichiers/beneathprodos.pdf |archive-date=2008-12-03 |url-status=live |access-date=2021-06-29 |edition=March 1985 printing}}</ref>
<ref name="Leopard">{{cite web |url=http://developer.apple.com/leopard/overview/objectivec2.html |title=Objective-C 2.0 Overview |archive-url=https://web.archive.org/web/20100724195423/http://developer.apple.com/leopard/overview/objectivec2.html |archive-date=2010-07-24 |url-status=dead}}</ref>
<ref name="Siracusa_2011">{{cite web |url=https://arstechnica.com/apple/2011/07/mac-os-x-10-7/11/ |title=Mac OS X 10.7 Lion: the Ars Technica review |author-first=John |author-last=Siracusa |date=2011-07-20}}</ref>
<ref name="Cichon_2015">{{cite web |url=http://www.heise.de/developer/meldung/App-Store-Apple-entfernt-Programme-mit-Garbage-Collection-2557111.html |title=App Store: Apple entfernt Programme mit Garbage Collection |date=2015-02-21 |access-date=2015-03-30 |publisher=[[Heise.de]] |author-first=Waldemar |author-last=Cichon}}</ref>
<ref name="Silva_2014">{{cite web |url=http://au.ibtimes.com/ios-8-vs-android-50-lollipop-apple-kills-google-memory-efficiency-1389704/ |title=iOS 8 vs Android 5.0 Lollipop: Apple Kills Google with Memory Efficiency |author-first=Precious |author-last=Silva |website=[[International Business Times]] |access-date=2015-04-07 |date=2014-11-18 |archive-date=2015-04-03  |archive-url=https://web.archive.org/web/20150403234107/http://au.ibtimes.com/ios-8-vs-android-50-lollipop-apple-kills-google-memory-efficiency-1389704 |url-status=dead }}</ref>
<ref name="Napier-Kumar_2012">{{cite book |url=https://books.google.com/books?id=-vg0Xe80W4oC&q=arc+runtime+garbage+collection&pg=PT83 |title=iOS 6 Programming Pushing the Limit |author-first1=Rob |author-last1=Napier |author-first2=Mugunth |author-last2=Kumar |access-date=2015-03-30 |date=2012-11-20 |publisher=[[John Wiley & Sons]] |isbn=978-1-11844997-4}}</ref>
<ref name="Cruz_2012">{{cite web|url=http://www.drdobbs.com/mobile/automatic-reference-counting-on-ios/240000820 |title=Automatic Reference Counting on iOS |first=José R. C. |last=Cruz |date=2012-05-22 |publisher=[[Dr. Dobbs]] |access-date=2015-03-30
|archive-url=https://web.archive.org/web/20200516185324/https://www.drdobbs.com/mobile/automatic-reference-counting-on-ios/240000820
|archive-date=2020-05-16
}}</ref>
<ref name="Fu-Hauser_2005">{{cite book |doi=10.1145/1140389.1140392 |chapter=A real-time garbage collection framework for embedded systems |title=Proceedings of the 2005 Workshop on Software and Compilers for Embedded Systems - SCOPES '05 |pages=20–26 |date=2005 |author-last1=Fu |author-first1=Wei |author-last2=Hauser |author-first2=Carl |isbn=1-59593207-0 |s2cid=8635481}}</ref>
<ref name="Tene-Iyengar-Wolf_2011">{{cite book |doi=10.1145/1993478 |chapter-url=https://www.azul.com/files/c4_paper_acm1.pdf |archive-url=https://web.archive.org/web/20170809024656/http://www.azul.com/files/c4_paper_acm1.pdf |archive-date=2017-08-09 |url-status=live |chapter=C4: the continuously concurrent compacting collector |title=ISMM '11: Proceedings of the international symposium on Memory management |date=2011 |author-last1=Tene |author-first1=Gil |author-last2=Iyengar |author-first2=Balaji |author-last3=Wolf |author-first3=Michael |isbn=978-1-45030263-0}}</ref>
<ref name="Mazur_2004">{{cite thesis |url=https://mercurylang.org/documentation/papers/CW2004_03_mazur.pdf |archive-url=https://web.archive.org/web/20140427161526/http://www.mercurylang.org/documentation/papers/CW2004_03_mazur.pdf |archive-date=2014-04-27 |url-status=live |title=Compile-time garbage collection for the declarative language Mercury |author-first=Nancy |author-last=Mazur |date=May 2004 |publisher=[[Katholieke Universiteit Leuven]]}}</ref>
<ref name="Appleinsider_2015">{{cite web |url=http://appleinsider.com/articles/15/02/20/apple-says-mac-app-makers-must-transition-to-arc-memory-management-by-may |title=Apple says Mac app makers must transition to ARC memory management by May |work=AppleInsider |date=2015-02-20}}</ref>
<ref name="Huelsbergen-Winterbottom_1998">{{cite book |doi=10.1145/286860.286878 |chapter-url=http://doc.cat-v.org/inferno/concurrent_gc/concurrent_gc.pdf |archive-url=https://web.archive.org/web/20080513153921/http://doc.cat-v.org/inferno/concurrent_gc/concurrent_gc.pdf |archive-date=2008-05-13 |url-status=live |chapter=Very concurrent mark-&-sweep garbage collection without fine-grain synchronization |title=Proceedings of the First International Symposium on Memory Management - ISMM '98 |pages=166–175 |date=1998 |author-last1=Huelsbergen |author-first1=Lorenz |author-last2=Winterbottom |author-first2=Phil |isbn=1-58113114-3 |s2cid=14399427}}</ref>
<ref name="IECC-GC">{{cite web |url=http://www.iecc.com/gclist/GC-faq.html |title=GC FAQ}}</ref>
<ref name="Lieberman-Hewitt_1983">{{cite journal |doi=10.1145/358141.358147 |url=https://web.media.mit.edu/~lieber/Lieberary/GC/Realtime/Realtime.html |title=A real-time garbage collector based on the lifetimes of objects |journal=[[Communications of the ACM]] |volume=26 |issue=6 |pages=419–429 |date=1983 |author-last1=Lieberman |author-first1=Henry |author-last2=Hewitt |author-first2=Carl |hdl=1721.1/6335 |s2cid=14161480 |hdl-access=free}}</ref>
<ref name="Baker_1978">{{cite journal |doi=10.1145/359460.359470 |title=List processing in real time on a serial computer |journal=[[Communications of the ACM]] |volume=21 |issue=4 |pages=280–294 |date=1978 |author-last=Baker |author-first=Henry G. |hdl=1721.1/41976 |s2cid=17661259 |hdl-access=free}} see also [http://web.media.mit.edu/~lieber/Lieberary/GC/Realtime/Realtime.html description]</ref>
<ref name="McCloskey_2008">{{citation |author-last=McCloskey |author-last2=Bacon |author-last3=Cheng |author-last4=Grove |url=http://researcher.watson.ibm.com/researcher/files/us-groved/rc24504.pdf |archive-url=https://web.archive.org/web/20140311134329/http://researcher.watson.ibm.com/researcher/files/us-groved/rc24504.pdf |archive-date=2014-03-11 |url-status=live |title=Staccato: A Parallel and Concurrent Real-time Compacting Garbage Collector for Multiprocessors |date=2008}}</ref>
<ref name="nanoframework">{{cite web |url=https://nanoframework.net/ |title=.NET nanoFramework}}</ref>
}}

== Further reading ==
* {{cite book |title=The Garbage Collection Handbook: The Art of Automatic Memory Management |date=2011-08-16 |author-first1=Richard |author-last1=Jones |author-first2=Antony |author-last2=Hosking |author-first3=J. Eliot B. |author-last3=Moss |publisher=[[Chapman and Hall]] / [[CRC Press]] / [[Taylor & Francis Ltd]] |series=CRC Applied Algorithms and Data Structures Series |isbn=978-1-4200-8279-1}} (511 pages)
* {{cite book |title=Garbage Collection: Algorithms for Automatic Dynamic Memory Management |date=1996-07-12 |edition=1 |author-first1=Richard |author-last1=Jones |author-first2=Rafael |author-last2=Lins |publisher=[[Wiley (publisher)|Wiley]] |isbn=978-0-47194148-4}} (404 pages)
* {{cite journal |author-first1=Herbert |author-last1=Schorr |author-first2= William M. |author-last2=Waite |title=An Efficient Machine-Independent Procedure for Garbage Collection in Various List Structures |journal=[[Communications of the ACM]] |volume=10 |number=8 |pages=501–506 |date=August 1967 |doi=10.1145/363534.363554 |s2cid=5684388 |url=https://www.cs.purdue.edu/homes/hosking/690M/p501-schorr.pdf |archive-url=https://web.archive.org/web/20210122003137/https://www.cs.purdue.edu/homes/hosking/690M/p501-schorr.pdf |archive-date=2021-01-22 |url-status=live}} 
* {{cite book |chapter=Uniprocessor Garbage Collection Techniques |author-first=Paul R. |author-last=Wilson |title=Memory Management |citeseerx=10.1.1.47.2438 |date=1992 |journal=Proceedings of the International Workshop on Memory Management (IWMM 92) |volume=637 |pages=1–42 |publisher=[[Springer-Verlag]] |doi=10.1007/bfb0017182|series=Lecture Notes in Computer Science |isbn=3-540-55940-X}}
* {{cite book |chapter=Dynamic Storage Allocation: A Survey and Critical Review |author-first1=Paul R. |author-last1=Wilson |author-first2=Mark S. |author-last2=Johnstone |author-first3=Michael |author-last3=Neely |author-first4=David |author-last4=Boles |title=Memory Management |date=1995 |edition=1 |journal=Proceedings of the International Workshop on Memory Management (IWMM 95) |volume=986 |pages=1–116 |citeseerx=10.1.1.47.275 |doi=10.1007/3-540-60368-9_19|series=Lecture Notes in Computer Science |isbn=978-3-540-60368-9}}

== External links ==
{{Wikibooks |Memory Management |Garbage Collection}}
* [http://www.memorymanagement.org/ The Memory Management Reference]
* [http://basen.oru.se/kurser/koi/2008-2009-p1/texter/gc/ The Very Basics of Garbage Collection]
* [http://www.oracle.com/technetwork/java/javase/gc-tuning-6-140523.html Java SE 6 HotSpot Virtual Machine Garbage Collection Tuning]
* [http://tinygc.sourceforge.net/ TinyGC - an independent implementation of the BoehmGC API]
* [http://www.codeproject.com/KB/cpp/conservative_gc.aspx Conservative Garbage Collection Implementation for C Language]
* [http://sourceforge.net/projects/meixnergc/ MeixnerGC - an incremental mark and sweep garbage collector for C++ using smart pointers]

{{Memory management}}
{{John McCarthy}}
{{Authority control}}

[[Category:Memory management]]
[[Category:Automatic memory management|*]]
[[Category:Solid-state computer storage]]