863:'s classic generation scavenger has two generations. It divides the youngest generation, called "new space", into a large "eden" in which new objects are created and two smaller "survivor spaces", past survivor space and future survivor space. The objects in the older generation that may reference objects in new space are kept in a "remembered set". On each scavenge, the objects in new space are traced from the roots in the remembered set and copied to future survivor space. If future survivor space fills up, the objects that do not fit are promoted to old space, a process called "tenuring". At the end of the scavenge, some objects reside in future survivor space, and eden and past survivor space are empty. Then future survivor space and past survivor space are exchanged and the program continues, allocating objects in eden. In Ungar's original system, eden is 5 times larger than each survivor space.
830:"mark and don't sweep" collector, all reachable objects are always black. An object is marked black at the time it is allocated, and it will stay black even if it becomes unreachable. A white object is unused memory and may be allocated. Second, the interpretation of the black/white bit can change. Initially, the black/white bit may have the sense of (0=white, 1=black). If an allocation operation ever fails to find any available (white) memory, that means all objects are marked used (black). The sense of the black/white bit is then inverted (for example, 0=black, 1=white). Everything becomes white. This momentarily breaks the invariant that reachable objects are black, but a full marking phase follows immediately, to mark them black again. Once this is done, all unreachable memory is white. No "sweep" phase is necessary.
803:, which dates to 1969. In this moving collector, memory is partitioned into an equally sized "from space" and "to space". Initially, objects are allocated in "to space" until it becomes full and a collection cycle is triggered. At the start of the cycle, the "to space" becomes the "from space", and vice versa. The objects reachable from the root set are copied from the "from space" to the "to space". These objects are scanned in turn, and all objects that they point to are copied into "to space", until all reachable objects have been copied into "to space". Once the program continues execution, new objects are once again allocated in the "to space" until it is once again full and the process is repeated.
853:). A generational GC (also known as ephemeral GC) divides objects into generations and, on most cycles, will place only the objects of a subset of generations into the initial white (condemned) set. Furthermore, the runtime system maintains knowledge of when references cross generations by observing the creation and overwriting of references. When the garbage collector runs, it may be able to use this knowledge to prove that some objects in the initial white set are unreachable without having to traverse the entire reference tree. If the generational hypothesis holds, this results in much faster collection cycles while still reclaiming most unreachable objects.
1000:, notably embedded systems, and a poor fit for interactive use, or any other situation where low latency is a priority. However, incremental garbage collectors can provide hard real-time guarantees, and on systems with frequent idle time and sufficient free memory, such as personal computers, garbage collection can be scheduled for idle times and have minimal impact on interactive performance. Manual memory management (as in C++) and reference counting have a similar issue of arbitrarily long pauses in case of deallocating a large data structure and all its children, though these only occur at fixed times, not depending on garbage collection.
818:"sweep" of the memory areas then frees white objects. The mark and sweep strategy has the advantage that, once the condemned set is determined, either a moving or non-moving collection strategy can be pursued. This choice of strategy can be made at runtime, as available memory permits. It has the disadvantage of "bloating" objects by a small amount, as in, every object has a small hidden memory cost because of the list/extra bit. This can be somewhat mitigated if the collector also handles allocation, since then it could potentially use unused bits in the allocation data structures. Or, this "hidden memory" can be eliminated by using a
857:
generation being collected (by the hypothesis), leaving it to be used to allocate new objects. When a collection doesn't collect many objects (the hypothesis doesn't hold, for example because the program has computed a large collection of new objects it does want to retain), some or all of the surviving objects that are referenced from older memory regions are promoted to the next highest region, and the entire region can then be overwritten with fresh objects. This technique permits very fast incremental garbage collection, since the garbage collection of only one region at a time is all that is typically required.
1040:
allocation only requires following a pointer. However, this size segregation usually cause a large degree of external fragmentation, which can have an adverse impact on cache behaviour. Memory allocation in a garbage collected language may be implemented using heap allocation behind the scenes (rather than simply incrementing a pointer), so the performance advantages listed above don't necessarily apply in this case. In some situations, most notably
524:, and regular weak references. A softly referenced object is only eligible for reclamation if the garbage collector decides that the program is low on memory. Unlike a soft reference or a regular weak reference, a phantom reference does not provide access to the object that it references. Instead, a phantom reference is a mechanism that allows the garbage collector to notify the program when the referenced object has become
2062:
2052:
2042:
2032:
2022:
879:) usually use some hybrid of the various strategies that have been described thus far; for example, most collection cycles might look only at a few generations, while occasionally a mark-and-sweep is performed, and even more rarely a full copying is performed to combat fragmentation. The terms "minor cycle" and "major cycle" are sometimes used to describe these different levels of collector aggression.
993:, though in some cases the amortized cost can be extremely low, in some cases even lower than one instruction per allocation or collection, outperforming stack allocation. Manual memory management requires overhead due to explicit freeing of memory, and reference counting has overhead from incrementing and decrementing reference counts, and checking if the count has overflowed or dropped to zero.
581:
66:
477:, the garbage collector needs to somehow be able to distinguish which variables on the stack or fields in an object are regular values and which are references: in memory, an integer and a reference might look alike. The garbage collector then needs to know whether to treat the element as a reference and follow it, or whether it is a primitive value. One common solution is the use of
25:
168:
636:
1081:
and at other times trigger a lengthy garbage collection cycle. Under reference counting, whereas allocation of objects is usually fast, decrementing a reference is nondeterministic, since a reference may reach zero, triggering recursion to decrement the reference counts of other objects which that object holds.
1133:
One major challenge for real-time garbage collection on modern multi-core architectures is in designing a non-blocking concurrent garbage collection, not letting the concurrent threads block each other and create unpredictable pauses. A study of algorithms that allow non-blocking real-time concurrent
895:
This has the disadvantage that the program can perform no useful work while a collection cycle is running (sometimes called the "embarrassing pause"). Stop-the-world garbage collection is therefore mainly suitable for non-interactive programs. Its advantage is that it is both simpler to implement and
829:
garbage collector, like the mark-and-sweep, keeps a bit with each object to record if it is white or black; the grey set is kept as a separate list or using another bit. There are two key differences here. First, black and white mean different things than they do in the mark and sweep collector. In a
817:
A mark and sweep garbage collector keeps a bit or two with each object to record if it is white or black. The grey set is kept as a separate list or using another bit. As the reference tree is traversed during a collection cycle (the "mark" phase), these bits are manipulated by the collector. A final
622:
This method has several disadvantages, the most notable being that the entire system must be suspended during collection; no mutation of the working set can be allowed. This can cause programs to 'freeze' periodically (and generally unpredictably), making some real-time and time-critical applications
1039:
It is difficult to compare the two cases directly, as their behavior depends on the situation. For example, in the best case for a garbage collecting system, allocation just increments a pointer, but in the best case for manual heap allocation, the allocator maintains freelists of specific sizes and
947:
collector. Conservative collectors assume that any bit pattern in memory could be a pointer if, interpreted as a pointer, it would point into an allocated object. Conservative collectors may produce false positives, where unused memory is not released because of improper pointer identification. This
551:
are useful. Like a regular hash table, a weak hash table maintains an association between pairs of objects, where each pair is understood to be a key and value. However, the hash table does not actually maintain a strong reference on these objects. Special behavior takes place when either the key or
1080:
Garbage collection can have a nondeterministic impact on execution time, by potentially introducing pauses into the execution of a program which are not correlated with the algorithm being processed. Under tracing garbage collection, the request to allocate a new object can sometimes return quickly
1072:
in the timing of object finalization. An object which becomes eligible for garbage collection will usually be cleaned up eventually, but there is no guarantee when (or even if) that will happen. This is an issue for program correctness when objects are tied to non-memory resources, whose release is
567:
Tracing collectors are so called because they trace through the working set of memory. These garbage collectors perform collection in cycles. It is common for cycles to be triggered when there is not enough free memory for the memory manager to satisfy an allocation request. But cycles can often be
735:
and leave everything else as it is, or it may copy some or all of the reachable objects into a new area of memory, updating all references to those objects as needed. These are called "non-moving" and "moving" (or, alternatively, "non-compacting" and "compacting") garbage collectors, respectively.
717:
The tri-color method has an important advantage – it can be performed "on-the-fly", without halting the system for significant periods of time. This is accomplished by marking objects as they are allocated and during mutation, maintaining the various sets. By monitoring the size of
709:
Since all objects not immediately reachable from the roots are added to the white set, and objects can only move from white to grey and from grey to black, the algorithm preserves an important invariant – no black objects reference white objects. This ensures that the white objects
1094:
systems. A real-time garbage collector should guarantee that even in the worst case it will dedicate a certain number of computational resources to mutator threads. Constraints imposed on a real-time garbage collector are usually either work based or time based. A time based constraint would look
1058:
Some advances in garbage collection can be understood as reactions to performance issues. Early collectors were stop-the-world collectors, but the performance of this approach was distracting in interactive applications. Incremental collection avoided this disruption, but at the cost of decreased
985:
Performance of tracing garbage collectors – both latency and throughput – depends significantly on the implementation, workload, and environment. Naive implementations or use in very memory-constrained environments, notably embedded systems, can result in very poor performance compared with other
918:
Careful design is necessary with these techniques to ensure that the main program does not interfere with the garbage collector and vice versa; for example, when the program needs to allocate a new object, the runtime system may either need to suspend it until the collection cycle is complete, or
914:
garbage collectors do not stop program execution at all, except perhaps briefly when the program's execution stack is scanned. However, the sum of the incremental phases takes longer to complete than one batch garbage collection pass, so these garbage collectors may yield lower total throughput.
833:
The mark and don't sweep strategy requires cooperation between the allocator and collector, but is incredibly space efficient since it only requires one bit per allocated pointer (which most allocation algorithms require anyway). However, this upside is somewhat mitigated, since most of the time
856:
In order to implement this concept, many generational garbage collectors use separate memory regions for different ages of objects. When a region becomes full, the objects in it are traced, using the references from the older generation(s) as roots. This usually results in most objects in the
688:
In many algorithms, initially the black set starts as empty, the grey set is the set of objects which are directly referenced from roots and the white set includes all other objects. Every object in memory is at all times in exactly one of the three sets. The algorithm proceeds as following:
739:
At first, a moving algorithm may seem inefficient compared to a non-moving one, since much more work would appear to be required on each cycle. But the moving algorithm leads to several performance advantages, both during the garbage collection cycle itself and during program execution:
870:
approach, and some unreachable objects may not be reclaimed on each cycle. It may therefore occasionally be necessary to perform a full mark and sweep or copying garbage collection to reclaim all available space. In fact, runtime systems for modern programming languages (such as
972:, or pointers to fields within an object. If the semantics of a language allow internal pointers, then there may be many different addresses that can refer to parts of the same object, which complicates determining whether an object is garbage or not. An example for this is the
744:
No additional work is required to reclaim the space freed by dead objects; the entire region of memory from which reachable objects were moved can be considered free space. In contrast, a non-moving GC must visit each unreachable object and record that the memory it occupied is
748:
Similarly, new objects can be allocated very quickly. Since large contiguous regions of memory are usually made available by a moving GC, new objects can be allocated by simply incrementing a 'free memory' pointer. A non-moving strategy may, after some time, lead to a heavily
976:
language, in which multiple inheritance can cause pointers to base objects to have different addresses. In a tightly optimized program, the corresponding pointer to the object itself may have been overwritten in its register, so such internal pointers need to be scanned.
619:, all memory is scanned from start to finish, examining all free or used blocks; those not marked as being 'in-use' are not reachable by any roots, and their memory is freed. For objects which were marked in-use, the in-use flag is cleared, preparing for the next cycle.
596:. Circles represent the objects themselves. Objects #1, #2, #3, #4, and #6 are strongly referenced from the root set. On the other hand, objects #5, #7, and #8 are not strongly referenced either directly or indirectly from the root set; therefore, they are garbage.
500:
A weak reference is not merely just any pointer to the object that a garbage collector does not care about. The term is usually reserved for a properly managed category of special reference objects which are safe to use even after the object disappears because they
956:
systems because the range of valid memory addresses tends to be a tiny fraction of the range of 64-bit values. Thus, an arbitrary 64-bit pattern is unlikely to mimic a valid pointer. A false negative can also happen if pointers are "hidden", for example using an
611:
which does a tree traversal of the entire 'root set' and marks each object that is pointed to by a root as being 'in-use'. All objects that those objects point to, and so on, are marked as well, so that every object that is reachable via the root set is marked.
552:
value or both become garbage: the hash table entry is spontaneously deleted. There exist further refinements such as hash tables which have only weak keys (value references are ordinary, strong references) or only weak values (key references are strong).
683:
The grey set contains all objects reachable from the roots but yet to be scanned for references to "white" objects. Since they are known to be reachable from the roots, they cannot be garbage-collected and will end up in the black set after being
1059:
efficiency due to the need for barriers. Generational collection techniques are used with both stop-the-world and incremental collectors to increase performance; the trade-off is that some garbage is not detected as such for longer than normal.
555:
Weak hash tables are important for maintaining associations between objects, such that the objects engaged in the association can still become garbage if nothing in the program refers to them any longer (other than the associating hash table).
259:
Informally, an object is reachable if it is referenced by at least one variable in the program, either directly or through references from other reachable objects. More precisely, objects can be reachable in only two ways:
891:
garbage collectors completely halt execution of the program to run a collection cycle, thus guaranteeing that new objects are not allocated and objects do not suddenly become unreachable while the collector is running.
291:
The reachability definition of "garbage" is not optimal, insofar as the last time a program uses an object could be long before that object falls out of the environment scope. A distinction is sometimes drawn between
680:
The black set is the set of objects that can be shown to have no outgoing references to objects in the white set, and to be reachable from the roots. Objects in the black set are not candidates for collection.
961:. Whether a precise collector is practical usually depends on the type safety properties of the programming language in question. An example for which a conservative garbage collector would be needed is the
509:). An unsafe reference that is not known to the garbage collector will simply remain dangling by continuing to refer to the address where the object previously resided. This is not a weak reference.
996:
In terms of latency, simple stop-the-world garbage collectors pause program execution for garbage collection, which can happen at arbitrary times and take arbitrarily long, making them unusable for
1130:, which also provides scalability to large multiprocessor architectures, while bringing various advantages over Metronome and other algorithms which, on the contrary, require specialized hardware.
834:
large portions of memory are wrongfully marked black (used), making it hard to give resources back to the system (for use by other allocators, threads, or processes) in times of low memory usage.
1073:
an externally visible program behavior, such as closing a network connection, releasing a device or closing a file. One garbage collection technique which provides determinism in this regard is
806:
This approach is very simple, but since only one semi space is used for allocating objects, the memory usage is twice as high compared to other algorithms. The technique is also known as
796:
Not only do collectors differ in whether they are moving or non-moving, they can also be categorized by how they treat the white, grey and black object sets during a collection cycle.
788:
the object in memory, preventing the garbage collector from moving it and allowing the memory to be directly shared with native pointers (and possibly allowing pointer arithmetic).
1044:, it is possible to avoid both garbage collection and heap management overhead by preallocating pools of memory and using a custom, lightweight scheme for allocation/deallocation.
466:. Although conservative heuristic methods for semantic garbage detection remain an active research area, essentially all practical garbage collectors focus on syntactic garbage.
948:
is not always a problem in practice unless the program handles a lot of data that could easily be misidentified as a pointer. False positives are generally less problematic on
559:
The use of a regular hash table for such a purpose could lead to a "logical memory leak": the accumulation of reachable data which the program does not need and will not use.
493:, which should be usable for as long as the object exists but should not prolong its lifetime. In discussions about weak references, ordinary references are sometimes called
772:
One disadvantage of a moving garbage collector is that it only allows access through references that are managed by the garbage collected environment, and does not allow
489:
The garbage collector can reclaim only objects that have no references pointing to them either directly or indirectly from the root set. However, some programs require
784:
with native code, the garbage collector must copy the object contents to a location outside of the garbage collected region of memory. An alternative approach is to
497:. An object is eligible for garbage collection if there are no strong (i.e. ordinary) references to it, even though there still might be some weak references to it.
910:
garbage collectors perform the garbage collection cycle in discrete phases, with program execution permitted between each phase (and sometimes during some phases).
837:
The mark and don't sweep strategy can therefore be seen as a compromise between the upsides and downsides of the mark and sweep and the stop and copy strategies.
718:
the sets, the system can perform garbage collection periodically, rather than as needed. Also, the need to touch the entire working set on each cycle is avoided.
706:
When the grey set is empty, the scan is complete; the black objects are reachable from the roots, while the white objects are not and can be garbage-collected.
822:, trading the memory cost for CPU time. However, the mark and sweep is the only strategy that readily cooperates with external allocators in the first place.
2002:
845:
It has been empirically observed that in many programs, the most recently created objects are also those most likely to become unreachable quickly (known as
600:
In the naive mark-and-sweep method, each object in memory has a flag (typically a single bit) reserved for garbage collection use only. This flag is always
1663:
83:
38:
639:
An example of tri-color marking on a heap with 8 objects. White, grey, and black objects are represented by light-grey, yellow, and blue, respectively.
696:
Move each white object that o references to the grey set. This ensures that neither this object nor any object it references can be garbage-collected.
243:
by a chain of references from certain "root" objects, and considering the rest as "garbage" and collecting them. Tracing is the most common type of
1711:
1464:
1103:
time. For work based analysis, MMU (minimal mutator utilization) is usually used as a real-time constraint for the garbage collection algorithm.
264:
A distinguished set of roots: objects that are assumed to be reachable. Typically, these include all the objects referenced from anywhere in the
1403:
580:
189:
176:
1545:
2055:
1859:
1683:
244:
2086:
2045:
130:
2065:
760:), objects can be moved very close to the objects they refer to in memory, increasing the chance that they will be located in the same
714:. Some variations on the algorithm do not preserve this invariant but use a modified form for which all the important properties hold.
102:
1630:
1505:
1479:
214:
149:
52:
109:
1882:
1656:
44:
2007:
986:
methods, while sophisticated implementations and use in environments with ample memory can result in excellent performance.
647:
87:
753:
heap, requiring expensive consultation of "free lists" of small available blocks of memory in order to allocate new objects.
536:
provides two subcategories of weak references, namely long weak references (tracks resurrection) and short weak references.
116:
906:
garbage collectors are designed to reduce this disruption by interleaving their work with activity from the main program.
1867:
1705:
867:
776:. This is because any pointers to objects will be invalidated if the garbage collector moves those objects (they become
593:
273:
623:
impossible. In addition, the entire working memory must be examined, much of it twice, potentially causing problems in
98:
1844:
872:
236:
1902:
1148:
528:. An object is phantom reachable, if it still resides in memory and it is referenced by a phantom reference, but its
239:
that consists of determining which objects should be deallocated ("garbage collected") by tracing which objects are
2025:
1892:
1745:
1649:
1971:
589:
585:
1271:
635:
1831:
1193:
962:
750:
2035:
1897:
1872:
1778:
1219:
1167:
1119:
1069:
643:
Because of these performance problems, most modern tracing garbage collectors implement some variant of the
181:
76:
1849:
1801:
1699:
1608:
1483:
1360:
1052:
1048:
990:
1115:
1143:
123:
1877:
1527:
965:, which allows typed (non-void) pointers to be type cast into untyped (void) pointers, and vice versa.
811:
247:– so much so that "garbage collection" often refers to the tracing method, rather than others such as
1415:
654:
collector) often do not make this abstraction explicit. Tri-color marking works as described below.
513:
228:
1755:
1553:
1365:
1091:
997:
1613:
1488:
568:
requested by the mutator directly or run on a time schedule. The original method involves a naïve
283:
Anything referenced from a reachable object is itself reachable; more formally, reachability is a
1997:
1981:
1907:
1519:
1411:
1378:
1323:
1074:
773:
732:
284:
248:
1601:
Proceedings of the 29th ACM SIGPLAN Conference on
Programming Language Design and Implementation
927:
Some collectors can correctly identify all pointers (references) in an object; these are called
1599:
1773:
1672:
1626:
1570:
Staccato: A Parallel and
Concurrent Real-time Compacting Garbage Collector for Multiprocessors
1511:
1501:
1297:
521:
293:
1950:
1945:
1788:
1618:
1493:
1445:
1370:
1313:
949:
781:
777:
494:
443:
297:
731:
Once the unreachable set has been determined, the garbage collector may simply release the
1940:
1839:
1568:
1430:
1041:
958:
512:
In some implementations, weak references are divided into subcategories. For example, the
463:
277:
1090:
While garbage collection is generally nondeterministic, it is possible to use it in hard
1245:
1051:-style program which frequently writes pointers into existing data structures than in a
1955:
1922:
1917:
1763:
1722:
1276:
1107:
876:
819:
768:
page. This can significantly speed up access to these objects through these references.
765:
544:
533:
517:
490:
478:
470:
269:
2080:
1932:
1735:
1730:
1374:
1523:
1345:
1327:
1122:. Another hard real-time garbage collection algorithm is Staccato, available in the
1595:
1382:
1341:
1035:
search for best/first-fit block and free list maintenance for non-moving collectors
624:
1567:
McCloskey, Bill; Bacon, David F.; Cheng, Perry; Grove, David (February 22, 2008).
1497:
1976:
919:
somehow notify the garbage collector that there exists a new, reachable object.
860:
442:
The problem of precisely identifying semantic garbage can easily be shown to be
65:
1740:
1465:"The Metronome: A Simpler Approach to Garbage Collection in Real-Time Systems"
761:
548:
474:
265:
1515:
1134:
garbage collection appears in a paper by Pizlo et al. in
Microsoft Research.
989:
In terms of throughput, tracing by its nature requires some implicit runtime
677:, is the set of objects that are candidates for having their memory recycled.
1887:
1768:
1622:
529:
167:
1449:
1318:
1301:
547:
can also be devised which have weak tracking features. For instance, weak
1821:
1816:
1806:
1796:
469:
Another complication with this approach is that, in languages with both
1811:
1055:-style program which constructs data only once and never changes them.
300:, those objects the program will in fact never again use. For example:
756:
If an appropriate traversal order is used (such as cdr-first for list
1127:
1047:
The overhead of write barriers is more likely to be noticeable in an
953:
251:– and there are a large number of algorithms used in implementation.
1641:
973:
634:
579:
462:
finishes would require a semantic garbage collector to solve the
1472:
Workshop on Java
Technologies for Real-Time and Embedded Systems
757:
1645:
1123:
1118:, whose commercial implementation is available as part of the
1111:
161:
59:
18:
1463:
Bacon, David F.; Cheng, Perry; Rajan, V. T. (November 2003).
1470:. In Corsaro, Angelo; Cytron, Ron; Santoro, Corrado (eds.).
572:
in which the entire memory set is touched several times.
371:* but we won't know until x.check_something() returns
368:/* In the following block, y *could* be semantic garbage;
1346:"Garbage collection can be faster than stack allocation"
1099:, mutator threads should be allowed to run at least for
710:
can be freed once the grey set is empty. This is called
702:
Repeat the last three steps until the grey set is empty.
296:, those objects the program cannot possibly reach, and
1684:
Memory management as a function of an operating system
1546:"Real-time Java, Part 4: Real-time garbage collection"
1990:
1964:
1931:
1858:
1830:
1787:
1754:
1721:
1692:
792:
Copying vs. mark-and-sweep vs. mark-and-don't-sweep
276:in the functions currently being invoked), and any
90:. Unsourced material may be challenged and removed.
1576:(Technical report). IBM Research Division. RC24504
1544:Biron, Benjamin; Sciampacone, Ryan (May 2, 2007).
1302:"Multiprocessing Compactifying Garbage Collection"
1011:search for best/first-fit block of sufficient size
1429:Cheng, Perry; Blelloch, Guy E. (June 22, 2001).
516:provides three forms of weak references, namely
1476:On The Move to Meaningful Internet Systems 2003
814:is an improvement on the semi-space collector.
1032:read/write barriers for incremental collectors
923:Precise vs. conservative and internal pointers
356:/* At this point, we know that the Foo object
1657:
883:Stop-the-world vs. incremental vs. concurrent
8:
2003:International Symposium on Memory Management
1029:copy reachable objects for moving collectors
896:faster than incremental garbage collection.
53:Learn how and when to remove these messages
1664:
1650:
1642:
1095:like: within each time window of duration
1612:
1607:. PLDI 2008 Conferenece. pp. 33–44.
1487:
1431:"A Parallel, Real-Time Garbage Collector"
1364:
1317:
799:The most straightforward approach is the
657:Three sets are created –
215:Learn how and when to remove this message
150:Learn how and when to remove this message
359:* originally assigned to x will never be
192:of all important aspects of the article.
1404:"Memory allocation in embedded systems"
1159:
604:, except during the collection cycle.
188:Please consider expanding the lead to
866:Generational garbage collection is a
650:, but simple collectors (such as the
446:: a program that allocates an object
374:* some value -- if it returns at all.
7:
1482:. Vol. 2889. pp. 466–478.
1106:One of the first implementations of
584:Naive mark-and-sweep in action on a
362:* accessed: it is syntactic garbage.
88:adding citations to reliable sources
1712:Input–output memory management unit
1598:; Steensgaard, Bjarne (June 2008).
939:) collectors, the opposite being a
1402:Hopwood, David (January 1, 2007).
1224:Java™ Platform Standard Ed. 7
1198:Java™ Platform Standard Ed. 7
1172:Java™ Platform Standard Ed. 7
1068:Tracing garbage collection is not
693:Pick an object o from the grey set
450:, runs an arbitrary input program
16:Form of computer memory management
14:
1194:"Class PhantomReference<T>"
532:has already executed. Similarly,
34:This article has multiple issues.
2061:
2060:
2051:
2050:
2041:
2040:
2031:
2030:
2021:
2020:
1474:. JTRES'03. OTM 2003 Workshops.
166:
64:
23:
1883:Concurrent mark sweep collector
180:may be too short to adequately
75:needs additional citations for
42:or discuss these issues on the
2008:Region-based memory management
1353:Information Processing Letters
1220:"Class WeakReference<T>"
1168:"Class SoftReference<T>"
841:Generational GC (ephemeral GC)
190:provide an accessible overview
1:
2056:Memory management algorithms
1868:Automatic Reference Counting
1706:Translation lookaside buffer
1498:10.1007/978-3-540-39962-9_52
1375:10.1016/0020-0190(87)90175-X
1086:Real-time garbage collection
99:"Tracing garbage collection"
2087:Automatic memory management
2046:Automatic memory management
1845:C dynamic memory allocation
1110:garbage collection for the
237:automatic memory management
2103:
2066:Memory management software
1913:Tracing garbage collection
1746:Virtual memory compression
485:Strong and weak references
233:tracing garbage collection
2016:
1679:
1306:Communications of the ACM
968:A related issue concerns
722:Implementation strategies
615:In the second stage, the
505:to a safe value (usually
255:Reachability of an object
1840:Static memory allocation
1832:Manual memory management
1026:locate reachable objects
302:
1898:Garbage-first collector
1873:Boehm garbage collector
1779:x86 memory segmentation
1623:10.1145/1375581.1375587
1250:.NET Framework 4.5
1120:IBM WebSphere Real Time
851:generational hypothesis
712:the tri-color invariant
699:Move o to the black set
607:The first stage is the
1903:Mark–compact algorithm
1700:Memory management unit
1149:Mark–compact algorithm
1004:Manual heap allocation
640:
597:
1450:10.1145/381694.378823
1319:10.1145/361002.361005
1272:"Copying and Pinning"
1144:Dead-code elimination
1014:free list maintenance
791:
727:Moving vs. non-moving
638:
583:
1850:new and delete (C++)
827:mark and don't sweep
801:semi-space collector
592:. Arrows represent
576:Naïve mark-and-sweep
514:Java Virtual Machine
229:computer programming
84:improve this article
1756:Memory segmentation
1438:ACM SIGPLAN Notices
1116:Metronome algorithm
998:real-time computing
945:partly conservative
733:unreachable objects
444:partially decidable
1998:Automatic variable
1982:Unreachable memory
1908:Reference counting
1878:Cheney's algorithm
1860:Garbage collection
1550:IBM DeveloperWorks
1300:(September 1975).
1075:reference counting
1019:Garbage collection
812:Cheney's algorithm
774:pointer arithmetic
673:The white set, or
641:
598:
522:phantom references
285:transitive closure
249:reference counting
245:garbage collection
2074:
2073:
2026:Memory management
1774:Virtual 8086 mode
1673:Memory management
1344:(June 17, 1987).
1246:"Weak References"
1114:was based on the
970:internal pointers
778:dangling pointers
645:tri-color marking
631:Tri-color marking
594:object references
588:containing eight
526:phantom reachable
495:strong references
294:syntactic garbage
225:
224:
217:
207:
206:
160:
159:
152:
134:
57:
2094:
2064:
2063:
2054:
2053:
2044:
2043:
2034:
2033:
2024:
2023:
1951:Dangling pointer
1946:Buffer over-read
1918:Strong reference
1789:Memory allocator
1666:
1659:
1652:
1643:
1637:
1636:
1616:
1606:
1591:
1585:
1584:
1582:
1581:
1575:
1564:
1558:
1557:
1552:. Archived from
1541:
1535:
1534:
1532:
1526:. Archived from
1491:
1469:
1460:
1454:
1453:
1435:
1426:
1420:
1419:
1414:. Archived from
1410:(Mailing list).
1399:
1393:
1392:
1390:
1389:
1368:
1350:
1342:Appel, Andrew W.
1338:
1332:
1331:
1321:
1294:
1288:
1287:
1285:
1284:
1268:
1262:
1261:
1259:
1257:
1242:
1236:
1235:
1233:
1231:
1216:
1210:
1209:
1207:
1205:
1190:
1184:
1183:
1181:
1179:
1164:
1042:embedded systems
952:systems than on
847:infant mortality
782:interoperability
540:Weak collections
508:
438:
435:
432:
429:
426:
423:
420:
417:
414:
411:
408:
405:
402:
399:
396:
393:
390:
387:
384:
381:
378:
375:
372:
369:
366:
363:
360:
357:
354:
351:
348:
345:
342:
339:
336:
333:
330:
327:
324:
321:
318:
315:
312:
309:
306:
298:semantic garbage
278:global variables
220:
213:
202:
199:
193:
170:
162:
155:
148:
144:
141:
135:
133:
92:
68:
60:
49:
27:
26:
19:
2102:
2101:
2097:
2096:
2095:
2093:
2092:
2091:
2077:
2076:
2075:
2070:
2012:
1986:
1960:
1941:Buffer overflow
1927:
1854:
1826:
1783:
1750:
1717:
1688:
1675:
1670:
1640:
1633:
1604:
1593:
1592:
1588:
1579:
1577:
1573:
1566:
1565:
1561:
1543:
1542:
1538:
1530:
1508:
1467:
1462:
1461:
1457:
1433:
1428:
1427:
1423:
1401:
1400:
1396:
1387:
1385:
1348:
1340:
1339:
1335:
1296:
1295:
1291:
1282:
1280:
1270:
1269:
1265:
1255:
1253:
1244:
1243:
1239:
1229:
1227:
1218:
1217:
1213:
1203:
1201:
1192:
1191:
1187:
1177:
1175:
1166:
1165:
1161:
1157:
1140:
1088:
1065:
983:
959:XOR linked list
925:
885:
843:
794:
729:
724:
633:
578:
565:
563:Basic algorithm
545:Data structures
542:
518:soft references
506:
491:weak references
487:
479:tagged pointers
471:reference types
464:halting problem
458:if and only if
440:
439:
436:
433:
430:
427:
424:
421:
418:
415:
412:
409:
406:
403:
400:
397:
394:
392:check_something
391:
388:
385:
382:
379:
376:
373:
370:
367:
364:
361:
358:
355:
352:
349:
346:
343:
340:
337:
334:
331:
328:
325:
322:
319:
316:
313:
310:
307:
304:
270:local variables
257:
221:
210:
209:
208:
203:
197:
194:
187:
175:This article's
171:
156:
145:
139:
136:
93:
91:
81:
69:
28:
24:
17:
12:
11:
5:
2100:
2098:
2090:
2089:
2079:
2078:
2072:
2071:
2069:
2068:
2058:
2048:
2038:
2036:Virtual memory
2028:
2017:
2014:
2013:
2011:
2010:
2005:
2000:
1994:
1992:
1988:
1987:
1985:
1984:
1979:
1974:
1968:
1966:
1962:
1961:
1959:
1958:
1956:Stack overflow
1953:
1948:
1943:
1937:
1935:
1929:
1928:
1926:
1925:
1923:Weak reference
1920:
1915:
1910:
1905:
1900:
1895:
1890:
1885:
1880:
1875:
1870:
1864:
1862:
1856:
1855:
1853:
1852:
1847:
1842:
1836:
1834:
1828:
1827:
1825:
1824:
1819:
1814:
1809:
1804:
1799:
1793:
1791:
1785:
1784:
1782:
1781:
1776:
1771:
1766:
1764:Protected mode
1760:
1758:
1752:
1751:
1749:
1748:
1743:
1738:
1733:
1727:
1725:
1723:Virtual memory
1719:
1718:
1716:
1715:
1709:
1703:
1696:
1694:
1690:
1689:
1687:
1686:
1680:
1677:
1676:
1671:
1669:
1668:
1661:
1654:
1646:
1639:
1638:
1631:
1586:
1559:
1556:on 2020-11-09.
1536:
1533:on 2006-10-26.
1506:
1455:
1444:(5): 125–136.
1421:
1418:on 2015-09-24.
1394:
1366:10.1.1.49.2537
1359:(4): 275–279.
1333:
1312:(9): 495–508.
1298:Steele, Guy L.
1289:
1277:Microsoft Docs
1263:
1237:
1211:
1185:
1158:
1156:
1153:
1152:
1151:
1146:
1139:
1136:
1108:hard real-time
1087:
1084:
1083:
1082:
1078:
1064:
1061:
1037:
1036:
1033:
1030:
1027:
1023:
1022:
1020:
1016:
1015:
1012:
1008:
1007:
1005:
982:
979:
924:
921:
889:stop-the-world
884:
881:
877:.NET Framework
842:
839:
820:Tagged pointer
793:
790:
770:
769:
766:virtual memory
754:
746:
728:
725:
723:
720:
704:
703:
700:
697:
694:
686:
685:
681:
678:
652:mark-and-sweep
632:
629:
577:
574:
570:mark-and-sweep
564:
561:
541:
538:
486:
483:
303:
289:
288:
281:
268:(that is, all
256:
253:
223:
222:
205:
204:
184:the key points
174:
172:
165:
158:
157:
72:
70:
63:
58:
32:
31:
29:
22:
15:
13:
10:
9:
6:
4:
3:
2:
2099:
2088:
2085:
2084:
2082:
2067:
2059:
2057:
2049:
2047:
2039:
2037:
2029:
2027:
2019:
2018:
2015:
2009:
2006:
2004:
2001:
1999:
1996:
1995:
1993:
1989:
1983:
1980:
1978:
1975:
1973:
1972:Fragmentation
1970:
1969:
1967:
1963:
1957:
1954:
1952:
1949:
1947:
1944:
1942:
1939:
1938:
1936:
1934:
1933:Memory safety
1930:
1924:
1921:
1919:
1916:
1914:
1911:
1909:
1906:
1904:
1901:
1899:
1896:
1894:
1891:
1889:
1886:
1884:
1881:
1879:
1876:
1874:
1871:
1869:
1866:
1865:
1863:
1861:
1857:
1851:
1848:
1846:
1843:
1841:
1838:
1837:
1835:
1833:
1829:
1823:
1820:
1818:
1815:
1813:
1810:
1808:
1805:
1803:
1800:
1798:
1795:
1794:
1792:
1790:
1786:
1780:
1777:
1775:
1772:
1770:
1767:
1765:
1762:
1761:
1759:
1757:
1753:
1747:
1744:
1742:
1739:
1737:
1736:Memory paging
1734:
1732:
1731:Demand paging
1729:
1728:
1726:
1724:
1720:
1713:
1710:
1707:
1704:
1701:
1698:
1697:
1695:
1691:
1685:
1682:
1681:
1678:
1674:
1667:
1662:
1660:
1655:
1653:
1648:
1647:
1644:
1634:
1632:9781595938602
1628:
1624:
1620:
1615:
1614:10.1.1.3.8544
1610:
1603:
1602:
1597:
1596:Petrank, Erez
1594:Pizlo, Phil;
1590:
1587:
1572:
1571:
1563:
1560:
1555:
1551:
1547:
1540:
1537:
1529:
1525:
1521:
1517:
1513:
1509:
1507:3-540-20494-6
1503:
1499:
1495:
1490:
1489:10.1.1.3.8544
1485:
1481:
1477:
1473:
1466:
1459:
1456:
1451:
1447:
1443:
1439:
1432:
1425:
1422:
1417:
1413:
1409:
1405:
1398:
1395:
1384:
1380:
1376:
1372:
1367:
1362:
1358:
1354:
1347:
1343:
1337:
1334:
1329:
1325:
1320:
1315:
1311:
1307:
1303:
1299:
1293:
1290:
1279:
1278:
1273:
1267:
1264:
1251:
1247:
1241:
1238:
1225:
1221:
1215:
1212:
1199:
1195:
1189:
1186:
1173:
1169:
1163:
1160:
1154:
1150:
1147:
1145:
1142:
1141:
1137:
1135:
1131:
1129:
1125:
1121:
1117:
1113:
1109:
1104:
1102:
1098:
1093:
1085:
1079:
1076:
1071:
1070:deterministic
1067:
1066:
1062:
1060:
1056:
1054:
1050:
1045:
1043:
1034:
1031:
1028:
1025:
1024:
1021:
1018:
1017:
1013:
1010:
1009:
1006:
1003:
1002:
1001:
999:
994:
992:
987:
980:
978:
975:
971:
966:
964:
960:
955:
951:
946:
942:
938:
934:
930:
922:
920:
916:
913:
909:
905:
901:
897:
893:
890:
882:
880:
878:
874:
869:
864:
862:
858:
854:
852:
848:
840:
838:
835:
831:
828:
823:
821:
815:
813:
809:
808:stop-and-copy
804:
802:
797:
789:
787:
783:
779:
775:
767:
763:
759:
755:
752:
747:
743:
742:
741:
737:
734:
726:
721:
719:
715:
713:
707:
701:
698:
695:
692:
691:
690:
682:
679:
676:
675:condemned set
672:
671:
670:
668:
664:
660:
655:
653:
649:
646:
637:
630:
628:
626:
620:
618:
613:
610:
605:
603:
595:
591:
587:
582:
575:
573:
571:
562:
560:
557:
553:
550:
546:
539:
537:
535:
534:Microsoft.NET
531:
527:
523:
519:
515:
510:
504:
498:
496:
492:
484:
482:
480:
476:
472:
467:
465:
461:
457:
453:
449:
445:
301:
299:
295:
286:
282:
279:
275:
271:
267:
263:
262:
261:
254:
252:
250:
246:
242:
238:
235:is a form of
234:
230:
219:
216:
201:
191:
185:
183:
178:
173:
169:
164:
163:
154:
151:
143:
132:
129:
125:
122:
118:
115:
111:
108:
104:
101: –
100:
96:
95:Find sources:
89:
85:
79:
78:
73:This article
71:
67:
62:
61:
56:
54:
47:
46:
41:
40:
35:
30:
21:
20:
1912:
1600:
1589:
1578:. Retrieved
1569:
1562:
1554:the original
1549:
1539:
1528:the original
1475:
1471:
1458:
1441:
1437:
1424:
1416:the original
1407:
1397:
1386:. Retrieved
1356:
1352:
1336:
1309:
1305:
1292:
1281:. Retrieved
1275:
1266:
1254:. Retrieved
1249:
1240:
1228:. Retrieved
1223:
1214:
1202:. Retrieved
1197:
1188:
1176:. Retrieved
1171:
1162:
1132:
1105:
1100:
1096:
1089:
1057:
1046:
1038:
995:
988:
984:
969:
967:
944:
941:conservative
940:
936:
932:
928:
926:
917:
911:
907:
903:
899:
898:
894:
888:
886:
865:
859:
855:
850:
846:
844:
836:
832:
826:
824:
816:
807:
805:
800:
798:
795:
785:
771:
738:
730:
716:
711:
708:
705:
687:
674:
666:
662:
658:
656:
651:
644:
642:
625:paged memory
621:
616:
614:
608:
606:
601:
599:
569:
566:
558:
554:
543:
525:
511:
502:
499:
488:
473:and unboxed
468:
459:
455:
451:
447:
441:
407:do_something
290:
258:
240:
232:
226:
211:
195:
179:
177:lead section
146:
137:
127:
120:
113:
106:
94:
82:Please help
77:verification
74:
50:
43:
37:
36:Please help
33:
1977:Memory leak
1252:. Microsoft
1063:Determinism
981:Performance
908:Incremental
900:Incremental
648:abstraction
617:sweep stage
549:hash tables
475:value types
454:, and uses
1741:Page table
1580:2022-04-25
1388:2022-04-25
1283:2022-04-25
1155:References
1053:functional
1049:imperative
963:C language
912:Concurrent
904:concurrent
762:cache line
751:fragmented
745:available.
609:mark stage
274:parameters
266:call stack
198:March 2024
110:newspapers
39:improve it
1888:Finalizer
1769:Real mode
1609:CiteSeerX
1516:0302-9743
1484:CiteSeerX
1361:CiteSeerX
1092:real-time
868:heuristic
627:systems.
530:finalizer
241:reachable
182:summarize
140:July 2016
45:talk page
2081:Category
1822:ptmalloc
1817:mimalloc
1807:jemalloc
1797:dlmalloc
1693:Hardware
1524:14565934
1408:cap-talk
1328:29412244
1226:. Oracle
1200:. Oracle
1174:. Oracle
1138:See also
991:overhead
937:accurate
875:and the
684:scanned.
1893:Garbage
1812:libumem
1714:(IOMMU)
1383:2575400
929:precise
887:Simple
849:or the
780:). For
602:cleared
590:objects
124:scholar
1965:Issues
1629:
1611:
1522:
1514:
1504:
1486:
1381:
1363:
1326:
1256:25 May
1230:25 May
1204:25 May
1178:25 May
1128:J9 JVM
954:32-bit
950:64-bit
931:(also
758:conses
422:System
323:Object
305:Object
126:
119:
112:
105:
97:
1991:Other
1802:Hoard
1708:(TLB)
1702:(MMU)
1605:(PDF)
1574:(PDF)
1531:(PDF)
1520:S2CID
1468:(PDF)
1434:(PDF)
1379:S2CID
1349:(PDF)
1324:S2CID
933:exact
861:Ungar
663:black
659:white
503:lapse
131:JSTOR
117:books
1627:ISBN
1512:ISSN
1502:ISBN
1480:LNCS
1412:EROS
1258:2013
1232:2013
1206:2013
1180:2013
902:and
873:Java
667:grey
665:and
586:heap
507:null
428:exit
350:Quux
272:and
103:news
1619:doi
1494:doi
1446:doi
1371:doi
1314:doi
1126:'s
1124:IBM
1112:JVM
974:C++
943:or
935:or
786:pin
764:or
395:())
353:();
347:new
338:();
335:Bar
332:new
320:();
317:Foo
314:new
227:In
86:by
2083::
1625:.
1617:.
1548:.
1518:.
1510:.
1500:.
1492:.
1478:.
1442:36
1440:.
1436:.
1406:.
1377:.
1369:.
1357:25
1355:.
1351:.
1322:.
1310:18
1308:.
1304:.
1274:.
1248:.
1222:.
1196:.
1170:.
1101:Tm
825:A
810:.
669::
661:,
520:,
481:.
437:);
416:);
380:if
377:*/
365:*/
231:,
48:.
1665:e
1658:t
1651:v
1635:.
1621::
1583:.
1496::
1452:.
1448::
1391:.
1373::
1330:.
1316::
1286:.
1260:.
1234:.
1208:.
1182:.
1097:T
1077:.
460:P
456:X
452:P
448:X
434:0
431:(
425:.
419:}
413:y
410:(
404:.
401:x
398:{
389:.
386:x
383:(
344:=
341:x
329:=
326:y
311:=
308:x
287:.
280:.
218:)
212:(
200:)
196:(
186:.
153:)
147:(
142:)
138:(
128:·
121:·
114:·
107:·
80:.
55:)
51:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
