Lecture
Garbage collection in programming is a form of automatic memory management. A special process called the garbage collector periodically frees memory by removing objects that applications will no longer need.
In computer programming, tracing garbage collection is a form of automatic memory management that consists of determining which objects should be deallocated ("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. 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 to other methods such as reference counting - and a large number of algorithms are used in its implementation.
Garbage collection was first applied by John McCarthy in 1959 in the programming environment of the functional programming language Lisp, which he developed. It was subsequently used in other programming systems and languages, mainly functional and logic ones. The need for garbage collection in languages of these types arises because their structure makes it extremely inconvenient to track the lifetimes of objects in memory and to manage memory manually. Lists, which are widely used in these languages, and the complex data structures built on them are constantly created, built up, extended and copied while programs run, and it is difficult to determine correctly the moment at which a given object should be deleted.
In industrial procedural and object-oriented languages, garbage collection was not used for a long time. Manual memory management was preferred as more efficient and predictable. But from the second half of the 1980s, garbage collection technology began to be used in imperative and object-oriented programming languages as well, and from the second half of the 1990s an increasing number of newly created languages and environments aimed at application programming include a garbage collection mechanism, either as the only mechanism for managing dynamic memory or as one of the available ones. Today it is used in Oberon, Java, Python, Ruby, C#, D, F#, Go and other languages.
The traditional way of managing memory in imperative languages is manual. It works as follows:
In any language that allows objects to be created in dynamic memory, two problems are potentially possible: dangling references and memory leaks.
A dangling reference (dangling pointer) is a reference to an object that has already been deleted from memory. After an object is deleted, all references to it that remain in the program become "dangling". The memory previously occupied by the object may be returned to the operating system and become inaccessible, or it may be reused to hold a new object in the same program. In the first case, an attempt to access memory through the dangling reference will trigger the memory protection mechanism and cause the program to crash, while in the second case it leads to unpredictable consequences.
Dangling references usually result from a wrong estimate of an object's lifetime: the programmer calls the delete command before the object's use has ended.
Having created an object in dynamic memory, the programmer may fail to delete it after finishing with it. If the variable referring to the object is assigned a new value and there are no other references to the object, it becomes unreachable by the program but continues to occupy memory, because the command to delete it was never called. This situation is called a memory leak.
If objects whose references are lost are constantly created in the program, the memory leak shows up as a gradual increase in the amount of memory used; if the program runs for a long time, the amount of memory it uses keeps growing, and after a while the system slows down noticeably (because swapping has to be used for every memory allocation), or the program exhausts the available address space and terminates with an error.
Informally, an object becomes reachable if at least one variable in the program refers to it, either directly or through references from other accessible objects. More precisely, objects can be reached in only two ways:
The reachability definition of "garbage" is not optimal, because the program last uses an object long before that object falls out of the scope of the environment. A distinction is sometimes drawn between syntactic garbage, those objects the program cannot reach, and semantic garbage, those objects the program will in fact never use again. For example:
The problem of precisely identifying semantic garbage can easily be shown to be partially decidable: a program that allocates an object X, runs an arbitrary input program P, and uses X if and only if P terminates would require a semantic garbage collector to solve the halting problem. Although conservative heuristic methods for semantic garbage detection remain an active area of research, virtually all practical garbage collectors focus on syntactic garbage.
Another complication of this approach is that, in languages with both reference types and unboxed value types, the garbage collector must somehow 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 tagged pointers.
If a computer's memory were infinite, one could simply leave unneeded objects in memory. Automatic memory management with garbage collection is an emulation of such an infinite computer on finite memory. Many limitations of garbage collectors (there is no guarantee that a finalizer will run; only memory is managed, not other resources) follow from this metaphor.
In a system with garbage collection, the responsibility for freeing memory is assigned to the program's runtime environment. The programmer merely creates dynamic objects and uses them; he need not worry about deleting objects, since the environment does this for him. To this end, the runtime environment includes a special software module called the "garbage collector". This module runs periodically, determines which of the objects created in dynamic memory are no longer in use, and frees the memory they occupy.
How often the garbage collector runs is determined by the characteristics of the system. The collector may work in the background, starting when the program is inactive (for example, when the program is idle waiting for user input). The garbage collector also runs unconditionally, stopping program execution (stop-the-world), when the next memory allocation operation cannot be carried out because all available memory has been exhausted. After memory is freed, the interrupted allocation operation resumes and the program continues to execute. If it turns out that no memory can be freed, the runtime environment stops the program with an "Out of memory" error message.
The optimal approach would be to remove from memory the objects that will not be accessed at all during the further course of the program. However, identifying such objects is impossible, because it reduces to the algorithmically undecidable halting problem (it is enough to suppose that some object X will be used if and only if program P terminates successfully). Therefore garbage collectors use conservative estimates that guarantee that an object will not be used in the future.
Usually, the criterion for an object still being in use is the presence of references to it: if there are no more references to a given object in the system, then it obviously can no longer be used by the program and can therefore be deleted. This criterion is used by most modern garbage collectors and is also called the reachability of an object. It is not theoretically the best, since by it objects that will never be used again but to which references still exist count as reachable; however, it guarantees protection against dangling references and can be implemented quite efficiently.
Informally, the following recursive definition of a reachable object can be given:
The flagging algorithm
A simple algorithm for determining reachable objects, the "mark and sweep" algorithm, works as follows:
If two or more objects refer to each other, but none of these objects is referenced from outside, the whole group is considered unreachable. This algorithm makes it possible to reliably delete groups of objects whose use has ceased but which contain references to one another. Such groups are often called "islands of isolation".
The reference counting algorithm
Another variant of the reachability algorithm is plain reference counting. Its use slows down reference assignment operations, but in return determining the reachable objects is trivial: they are all the objects whose reference counter value exceeds zero. Without additional refinements, this algorithm, unlike the previous one, does not remove cyclically closed chains of obsolete objects that refer to each other.
Once the set of unreachable objects has been determined, the garbage collector can free the memory they occupy and leave everything else as it is. It is also possible, after freeing memory, to move all or some of the remaining objects to other areas of memory, updating all references to them at the same time. These two implementation options are called, respectively, non-moving and moving.
Both strategies have advantages as well as drawbacks.
Speed of memory allocation and deallocation
A non-moving garbage collector frees memory faster (since the operation amounts to marking the corresponding memory blocks as free), but spends more time on allocating it (since memory becomes fragmented, and during allocation it is necessary to find the required number of blocks of suitable size in memory).
A moving collector takes relatively more time during garbage collection (extra time is spent on defragmenting memory and changing all references to the moved objects), but moving makes it possible to use an extremely simple and fast (O(1)) memory allocation algorithm. During defragmentation the objects are moved so as to divide all memory into two large areas - occupied and free - and a pointer to the boundary between them is kept. To allocate new memory, it is enough to shift this boundary, returning a piece from the beginning of the free memory.
Speed of access to objects in dynamic memory
A moving collector makes it possible to place objects whose fields are used together close to each other in memory. They are then more likely to end up in the processor cache at the same time, which reduces the number of accesses to the relatively slow RAM.
Compatibility with foreign code
A moving garbage collector causes difficulties when using code that is not managed by the automatic memory management system (such code is called foreign in traditional terminology, or unmanaged in Microsoft terminology). A pointer to memory allocated in a system with a non-moving collector can simply be passed to foreign code for use, as long as at least one ordinary reference to the object is kept so that the collector does not delete it. A moving collector changes the positions of objects in memory, changing all references to them in sync, but it cannot change the references in foreign code; as a result, references passed to foreign code become invalid after the object is moved. Various special techniques are used to work with foreign code, for example pinning - explicitly locking an object, forbidding its movement during garbage collection.
Practice shows that recently created objects become unreachable more often than objects that have existed for a long time. In accordance with this pattern, many modern garbage collectors divide all objects into several generations - series of objects with similar lifetimes. As soon as the memory allocated to one of the generations runs out, a search for unreachable objects is performed in that generation and in all "younger" ones. All of these are deleted, and the remaining ones are promoted to an "older" generation.
The use of generations shortens the garbage collection cycle, since the number of objects scanned during collection is reduced, but this method requires the runtime environment to track references between different generations.
Immutable objects
The rules of a programming language may stipulate that objects declared in a special way, or belonging to certain types, are fundamentally immutable. For example, character strings in Java and a number of other languages are like this. Thanks to the information about immutability, the memory management system can save space. For example, when a string variable is assigned the value "Hello", the string is placed in memory and the variable receives a reference to it. But if another variable is later initialized with the same string, the system will find the previously created "Hello" string in memory and assign the second variable a reference to that same string, instead of allocating the string in memory again. Since the string is fundamentally immutable, this solution has no effect on the program's logic, but the string will not be duplicated in memory no matter how many times it is used. And only when all references to it have been removed will the string be destroyed by the garbage collector.
As a rule, such constant objects are stored in specially allocated areas of memory called "pools" (the area for storing immutable strings is the "string pool"), for efficient handling of which rather specific algorithms may be used.
Finalizers
A finalizer is code that is executed automatically immediately before an object is removed from memory by the garbage collector. Finalizers are used to check whether the object's cleanup has been performed, and to free additional memory if it was allocated during the object's creation or operation bypassing the memory management system.
Unskilled programmers often try to use finalizers to release files, network sockets and other system resources used by objects. This is extremely bad practice: since the moment an object is deleted by the garbage collector depends on the amount of available memory and how intensively the program uses it, it is impossible to predict when the finalizer will be called, or whether it will be called at all. Finalizers are not suitable for releasing any system resources other than RAM; the programmer must close files or sockets manually with a command such as close() when the object actually ceases to be used.
A garbage collector can reclaim only those objects that have no references pointing to them, directly or indirectly, from the root set. However, some programs require weak references, which should be usable for as long as the object exists but should not prolong its lifetime. In discussions of weak references, ordinary references are sometimes called strong references. An object is eligible for garbage collection if there are no strong (that is, ordinary) references to it, even though some weak references to it may still exist.
A weak reference is not merely any pointer to an object that the garbage collector does not care about. The term is usually reserved for a properly managed category of special reference objects that are safe to use even after the object disappears, because their value changes to a safe one (usually null). An unsafe reference that is unknown to the garbage collector will simply remain dangling, continuing to refer to the address where the object used to be. This is not a weak reference.
In some implementations, weak references are divided into subcategories. For example, the Java virtual machine provides three forms of weak references, namely soft references, phantom references, and ordinary weak references. An object with a soft reference is reclaimed only if the garbage collector decides that the program is short of memory. Unlike a soft reference or an ordinary weak reference, a phantom reference does not provide access to the object it refers to. Instead, a phantom reference is a mechanism that allows the garbage collector to notify the program when the referenced object has become phantom reachable.. An object is phantom reachable if it is still in memory and is referenced by a phantom reference, but its finalizer has already been executed. Similarly, Microsoft .NET provides two subcategories of weak references, namely long weak references (track resurrection) and short weak references.
Data structures with weak tracing features can also be designed. For example, weak hash tables are useful. Like an ordinary hash table, a weak hash table maintains an association between pairs of objects, where each pair is understood as a key and a value. However, the hash table does not actually hold strong references to these objects. Special behavior occurs when the key, the value, or both become garbage: the hash table entry is spontaneously deleted. There are further refinements, such as hash tables that have only weak keys (references to values are ordinary, strong references) or only weak values (references to keys are strong).
Weak hash tables are important for maintaining associations between objects, so that the objects participating in an association can still become garbage if nothing else in the program refers to them any longer (other than the associated hash table).
Using an ordinary hash table for this purpose can lead to a "logical memory leak": an accumulation of reachable data that the program does not need and will not use.
Tracing collectors are so called because they trace the working set of memory. These garbage collectors perform collection in cycles. Typically, cycles are triggered when there is not enough free memory for the memory manager to satisfy an allocation request. But cycles can often be requested directly by the mutator or run on a schedule. The original method involves a naive mark-and-sweep, in which the entire working set of memory is touched several times.
Naive mark-and-sweep in action on a heap containing eight objects. Arrows denote references to objects. Circles represent the objects themselves. Objects #1, #2, #3, #4 and #6 are strongly connected to the root set. On the other hand, objects #5, #7 and #8 have no direct or indirect references from the root set; therefore, they are garbage.
In the naive mark-and-sweep method, each object in memory has a flag (usually a single bit) reserved solely for use in garbage collection. This flag is always cleared, except during the collection cycle.
The first phase is the mark phase, which traverses the entire "root set" and marks every object pointed to by a root as "in use". All objects that those objects point to, and so on, are also marked, so that every object reachable through the root set is marked.
In the second phase, the sweep phase, all memory is scanned from start to finish, examining all free or used blocks; those that are not marked as "in use" are not reachable from any roots, and their memory is freed. For the objects that were marked as in use, the in-use flag is cleared, in preparation for the next cycle.
This method has several drawbacks, the most notable being that the entire system must be suspended during collection; no changes to the working set are permitted. This can cause programs to "freeze" periodically (and, as a rule, unpredictably), which makes some real-time and time-critical applications impossible. In addition, the whole working memory must be examined, most of it twice, which can cause problems in systems with paged memory.
An example of tri-color marking on a heap with 8 objects. White, gray and black objects are represented by light gray, yellow and blue respectively.
Because of these performance problems, most modern tracing garbage collectors implement some variant of the tri-color marking abstraction, although simple collectors (such as the mark-and-sweep collector) often do not make this abstraction explicit. Tri-color marking works as described below.
Three sets are created - white, black and gray:
In many algorithms, the black set starts out empty, the grey set is the set of objects directly referenced by the roots, and the white set includes all other objects. Every object in memory is always in exactly one of the three sets. The algorithm proceeds as follows:
When the grey set is empty, the scan is complete; the black objects are reachable from the roots, while the white objects are unreachable and can be garbage-collected.
Because all objects that are 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 object references a white object. This guarantees that the white objects can be freed once the grey set is empty. This is known as the tri-color invariant . Some variants of the algorithm do not maintain this invariant but use a modified form for which all the important properties hold.
The tri-color method has an important advantage: it can be performed "on the fly", without halting the system for a significant period of time. This is achieved by marking objects as they are allocated and during mutation, while maintaining the various sets. By controlling the size of the sets, the system can perform garbage collection periodically rather than only when needed. In addition, the need to touch the entire working set on every cycle is eliminated.
Once the unreachable set has been determined, the garbage collector can simply release the unreachable objects and leave everything else as it is, or it can 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.
At first, a moving algorithm may seem inefficient compared to a non-moving one, since it requires much more work on each cycle. But the moving algorithm brings several performance benefits, both during the garbage collection cycle itself and during program execution:
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 pointer arithmetic . This is because any pointers to objects will be invalidated if the garbage collector moves those objects (they become dangling pointers ). To interoperate with native code, the garbage collector must copy the object contents to a location outside the memory region in which the garbage collector operates. An alternative approach is to pin the object in memory, preventing the garbage collector from moving it and allowing the memory to be used directly by native pointers (and possibly allowing pointer arithmetic).
Collectors differ not only in whether they are moving or non-moving; they can also be categorized by how they treat the sets of white, grey and black objects during the collection cycle.
The simplest approach is the semispace collector , which dates back to 1969. In this moving collector, memory is divided into 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 the "to-space", until all reachable objects have been copied into the "to-space". Once the program resumes execution, new objects are again allocated in the "to-space".
This approach is very simple, but since only one semispace is used for allocating objects, memory usage is twice as high compared to other algorithms. This technique is also known as stop-and-copy . Cheney's algorithm is an improvement on the semispace collector.
A mark-and-sweep garbage collector keeps a bit or two with each object to record whether 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 the collection cycle (the "mark" phase), these bits are manipulated by the collector. A final "sweep" over the memory areas then frees the white objects. The mark-and-sweep strategy has the advantage that, once the condemned set has been determined, either a moving or a non-moving collection strategy can be used. This choice of strategy can be made at run time, as available memory permits. Its disadvantage is "bloating" the objects by a small amount, for example each object has a small hidden memory cost due to the list / extra bit. This can be mitigated somewhat if the collector also handles allocation, since it can then potentially use unused bits in the allocation data structures. Alternatively, this "hidden memory" can be eliminated using a tagged pointer , trading memory cost for CPU time. However, mark-and-sweep is the only strategy that easily interoperates with external allocators in the first place.
A mark-and-don't-sweep garbage collector, like mark-and-sweep, keeps a bit with each object to record whether 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 a mark-and-sweep collector. In a "mark-and-don't-sweep" collector, all reachable objects are always black. At the moment of allocation, an object is marked black, and it will remain 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 meaning (0 = white, 1 = black). If an allocation operation fails to find available (white) memory, it means that all objects are marked as used (black). The meaning of the black/white bit is then inverted (for example, 0 = black, 1 = white). Everything becomes white. This momentarily violates the invariant that reachable objects are black, but a full marking phase immediately follows, to mark them black again. Once this is done, all unreachable memory is white. No "sweep" phase is required.
The mark-and-don't-sweep strategy requires cooperation between the allocator and the collector, but it is incredibly space-efficient , since it requires only one bit allocated per pointer (which most allocation algorithms require anyway). However, this advantage is somewhat mitigated by the fact that, most of the time, large portions of memory are wrongly marked black (in use), which makes it difficult to return resources to the system (for use by other allocators, threads or processes) during periods of low memory usage.
Thus, the mark-and-don't-sweep strategy can be seen as a compromise between the strengths and weaknesses of the mark-and-sweep and stop-and-copy strategies .
It has been empirically observed that in many programs the most recently created objects are also the ones most likely to quickly become unreachable (this is known as infant mortality or the generational hypothesis.). A generational collector (also known as an ephemeral garbage collector) divides objects into generations and, in most cycles, places only the objects of a subset of the generations into the initial white (condemned) set. In addition, the runtime system maintains information about when references cross generations, by observing the creation and overwriting of references. When the garbage collector runs, it can 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.
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 references from the older generation(s) as roots. This usually results in most of the objects in the generation being collected (by the hypothesis), leaving it free for allocating new objects. When a collection does not reclaim many objects (the hypothesis does not hold, for example because the program has built up a large collection of new objects that it wants to keep), some or all of the surviving objects that are referenced from older memory regions are moved to the next highest region, and then the whole region can be overwritten with new objects. This technique allows garbage collection to be made very fast,
The classic generational garbage collector of Ungar has two generations. It divides the youngest generation, called the "new space", into a large "eden", in which new objects are created, and two smaller "survivor spaces", the past survivor space and the future survivor space. Objects in the old generation that may reference objects in the new space are kept in a "remembered set". At each scavenge, the objects in the new space are traced from the roots in the remembered set and copied to the future survivor space. If the future survivor space fills up, the objects that do not fit are moved to the old space, a process called "tenuring". At the end of the scavenge, some objects are in the future survivor space, and the eden and past survivor space are empty. The future survivor space and the past survivor space are then swapped, and the program continues, allocating objects in eden. In Ungar's original system, eden is 5 times larger than each survivor space.
Generational garbage collection is a heuristic approach, and some unreachable objects may not be reclaimed in 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, the runtime systems of modern programming languages (such as Java and the .NET Framework ) usually use some hybrid of the different strategies described so far; for example, most collection cycles may consider only a few generations, while a mark-and-sweep is occasionally performed, and a full copying collection is performed even more rarely to combat fragmentation. The terms "minor cycle" and "major cycle" are sometimes used to describe these different levels of collector aggressiveness.
Simple stop-the-world garbage collectors completely halt program execution to run a collection cycle, thereby guaranteeing that new objects are not allocated and that objects do not suddenly become unreachable while the collector is running.
This has the obvious disadvantage that the program cannot perform any useful work while a collection cycle is running (this is sometimes called the "embarrassing pause"). Stop-the-world garbage collection is therefore mainly suitable for non-interactive programs. Its advantage is that it is simpler to implement and faster than incremental garbage collection.
Incremental and concurrent garbage collectors are designed to reduce this disruption by interleaving their work with the activity of the main program. Incremental garbage collectors perform the garbage collection cycle in discrete phases, with program execution permitted between the phases (and sometimes during some phases). Concurrent garbage collectors do not stop program execution at all, except perhaps briefly to scan the program's execution stack. However, the sum of the incremental phases takes longer than a single batch garbage collection pass, so these garbage collectors may yield lower overall throughput.
These techniques require careful design 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 have to suspend it until the collection cycle is finished, or somehow notify the garbage collector that there is a new reachable object.
Some collectors can correctly identify all pointers (references) in an object; these are called precise (also exact or accurate ) collectors, the opposite being conservative or partially conservative collectors. 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 can produce false positives, where unused memory is not released because of improper pointer identification. In practice this is not always a problem unless the program handles a large amount of data that could easily be misidentified as a pointer. False positives are generally less problematic on 64-bit systems than on 32-bit 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 occur if pointers are "hidden", for example when using an XOR linked list . The practicality of a precise collector generally depends on the type-safety properties of the programming language in question. An example for which a conservative garbage collector may be required is the C language, which allows typed (non-void) pointers to be cast to untyped (void) pointers and vice versa.
A related problem concerns interior pointers, or pointers to fields within an object. If the semantics of a language allow interior pointers, then there may be many different addresses that can refer to parts of the same object, which makes it more difficult to determine whether an object is garbage or not. An example of this is the C++ language, in which multiple inheritance can cause pointers to base objects to have different addresses. In a heavily optimized program, the corresponding pointer to the object itself may have been overwritten in its register, so such interior pointers must be scanned.
For a program to be able to use garbage collection, a number of conditions related to the language, the runtime environment and the problem being solved must be met.
The need for a runtime environment with a garbage collector
Naturally, garbage collection requires a dynamic environment that supports program execution, and the presence of a garbage collector in that environment. For interpreted languages, or languages compiled to virtual machine bytecode, the garbage collector can be included in the code of the language or bytecode interpreter, but for languages compiled to object code the garbage collector necessarily becomes part of a system library that is linked (statically or dynamically) with the program code when the executable is created, increasing the size of the program and its load time.
Support from the programming language
A garbage collector can function properly only when it can accurately track all references to all created objects. Obviously, if a language allows references (pointers) to be converted to other data types (integers, byte arrays and so on), as C/C++ does, it becomes impossible to track the use of such converted references, and garbage collection becomes meaningless: it does not protect against dangling references and memory leaks. Therefore, languages oriented toward the use of garbage collection usually significantly restrict the freedom to use pointers, address arithmetic, and conversions of pointer types to other data types. Some of them have no "pointer" data type at all; in others it exists but allows neither type conversion nor modification.
Technical acceptability of brief slowdowns in program operation
Garbage collection is performed periodically, usually at times that are not known in advance. If suspending the program for a period comparable to the garbage collection time could lead to critical errors, garbage collection obviously cannot be used in such a situation.
Availability of some reserve of free memory
The more memory is available to the runtime environment, the less often the garbage collector runs and the more efficient its work is. Running a garbage collector in a system where the amount of memory available to it approaches the program's peak demand can be inefficient and unproductive. The smaller the excess of memory, the more often the collector is launched and the more time is spent on its execution. The drop in program performance in this mode can be too significant.
Contrary to frequently made claims, having garbage collection does not free the programmer from all memory management problems.
Releasing other resources held by an object
Besides dynamic memory, an object may own other resources, sometimes more valuable than memory. If an object opens a file when it is created, it must close it when it is done using it; if it connects to a DBMS, it must disconnect. In systems with manual memory management, this is done immediately before the object is removed from memory, most often in the destructors of the corresponding objects. Systems with garbage collection usually have the ability to execute some code immediately before an object is deleted, so-called finalizers, but they are not suitable for releasing resources, because the moment of deletion is not known in advance, and it may turn out that the resource is released much later than the object stops being used. In such cases the programmer still has to track the use of the object manually and manually perform the operations that release the resources held by the object. In C# there is the IDisposable interface specifically for this purpose, and in Java there is AutoCloseable.
Memory leak
Memory leaks can also occur in systems with garbage collection, although they are of a somewhat different nature. A reference to an unused object may be preserved in another object that is in use and becomes a kind of "anchor" holding the unneeded object in memory. For example, a created object is added to a collection used for auxiliary operations, then stops being used, but is not removed from the collection. The collection holds the reference, the object remains reachable and is not garbage-collected. The result is the same memory leak.
To eliminate such problems, the runtime environment may support a special facility: so-called weak references. Weak references do not hold on to the object and turn into null as soon as the object disappears, so the code must be prepared for the reference to point to nothing one day.
Loss of efficiency in operations with frequent allocation and deallocation of memory
Some actions that are perfectly harmless in systems with manual memory management can generate disproportionately large overhead in systems with garbage collection. A classic example of such a problem is given below.
String out = "";
// It is assumed that strings contains a large number of short strings,
// from which one large string must be assembled in the variable out.
for( String str : strings ) {
out += str; // On each iteration, this code will create
// a new string variable and allocate memory for it.
}
This Java code looks as if the variable out, created once, is "appended to" with a new string on each pass of the loop. In reality, however, strings in Java are immutable, so on each pass of the loop this code will do the following:
Each time, the block of memory that previously held the value of the variable out falls out of use and waits until the garbage collector runs. If 100 strings of 100 characters each are concatenated this way, more than 500,000 bytes of memory will be allocated in total for this operation, which is 50 times more than the size of the final "long" string.
Such operations, in which fairly large objects are frequently created in memory and immediately stop being used, lead to very fast unproductive filling of all available memory and frequent garbage collector runs, which under certain conditions can greatly slow down the program or, at the very least, require an inadequately large amount of memory to be allocated for it to work. To avoid such problems, the programmer must have a good understanding of the automatic memory management mechanism. Special facilities may also sometimes be used to perform dangerous operations efficiently. Thus, to optimize the example above, one should use the special StringBuilder class, which allows memory for the entire string to be allocated in one action, and in the loop only the next fragment is appended to the end of this string.
Problems of interaction with foreign code and direct work with physical memory
In practical programming in garbage-collected languages, it is almost impossible to avoid interacting with so-called foreign code: operating system APIs, device drivers, and external software modules written in other languages are not managed by the garbage collector. Sometimes it is necessary to work directly with the computer's physical memory; the memory management system restricts this as well, if it allows it at all.
Interaction with foreign code is provided in one of two ways: either a wrapper for the foreign code that hides the low-level details is written in a low-level language (usually C), or syntax is added directly to the language that makes it possible to write "unsafe" code, that is, individual fragments or modules for which the programmer is given fuller control over all aspects of memory management.
Both solutions have their drawbacks. Wrappers are, as a rule, complex, require high qualifications to develop, and can be poorly portable. (However, their creation can be automated. For example, there is the multi-language generator SWIG, which automatically creates wrappers for a number of garbage-collected languages from existing C/C++ header files.) They are prone to becoming obsolete: a wrapper written for one implementation of a language may become unusable in another, for example when moving from a non-moving garbage collector to a moving one.
Special syntax for unsafe code is a "legal loophole" in the memory management mechanism and a source of hard-to-detect errors; by its very existence it also tempts the programmer to circumvent the language's restrictions.
In addition, any interference with the operation of the garbage collector (which is unavoidable when interacting with foreign code) potentially reduces its efficiency. For example, pinning a certain region of memory, which is necessary so that the garbage collector does not delete or move it while foreign code is working with that memory, can limit the possibility of memory defragmentation and thereby make it harder to subsequently allocate blocks of the required size, even when there is enough free memory in total.
Compared with manual memory management, garbage collection is safer, since it prevents memory leaks and dangling references caused by untimely deletion of objects. It also simplifies the programming process itself.
Garbage collection is believed to noticeably reduce the effort spent on memory management compared with languages that do not implement it. According to one study, C programmers spend 30% to 40% of their total development time (not counting debugging) on memory management alone. However, there are studies with the opposite conclusions; for example, one work claims that the real difference in software development speed between C++, which has no automatic garbage collection, and Java, which does, is small.
The presence of a garbage collector can create in an inexperienced developer the false belief that they need not pay any attention to memory management at all. Although a garbage collector does reduce the problems of incorrect memory management, it does not eliminate them completely, and those that remain show up not as obvious errors, such as a general protection fault, but as unjustified memory consumption while the program runs. A typical example: if the programmer overlooked the fact that at least one non-nulled pointer to an object remains in the global scope, that object will never be deleted; finding such a pseudo-leak can be very difficult.
Often what is critical is not only the guarantee that a resource will be released, but also the guarantee that it will be released before some other procedure is called, for example open files and entries into critical sections. Attempts to hand the management of such resources over to the garbage collector (through finalizers) will be ineffective or even incorrect, so they have to be managed manually. Recently, even garbage-collected languages have been introducing syntax that guarantees the execution of "cleanup code" (for example, a special "destructor" method) when a variable referring to an object goes out of scope.
In many cases, garbage-collected systems show lower efficiency, both in speed and in the amount of memory used (which is inevitable, since the garbage collector itself consumes resources and needs some surplus of free memory to work normally). In addition, low-level algorithms that require direct access to the computer's RAM are harder to implement in garbage-collected systems, because free use of pointers is impossible and direct memory access requires special interfaces written in low-level languages. On the other hand, modern garbage-collected systems use very efficient memory management algorithms that give minimal overhead. One also cannot ignore the fact that RAM is now relatively cheap and available. Under such conditions, situations in which the cost of garbage collection itself becomes critical for a program's efficiency are extremely rare.
A significant advantage of garbage collection appears when dynamically created objects live for a long time, are duplicated many times, and references to them are passed between different parts of the program. Under such conditions it is quite difficult to determine the place where an object stops being used and can be deleted. Since exactly this situation arises with the widespread use of dynamically changing data structures (lists, trees, graphs), garbage collection is necessary in functional and logic languages, such as Haskell, Lisp or Prolog, that use such structures extensively. The use of garbage collection in traditional imperative languages (based on the structured paradigm, possibly supplemented with object-oriented features) is determined by the desired balance between the simplicity and speed of program development and the efficiency of its execution.
Support in some imperative languages (C++, Ada, Delphi) for automatically calling a destructor when an object leaves its lexical scope makes it possible to place the memory-freeing code in the destructor and be sure that it will be called in any case. This makes it possible to concentrate the dangerous places inside the implementation of a class, and it requires no extra resources, although it places higher demands on the programmer's qualifications. At the same time, it becomes possible to safely release in the destructor the other resources held by the object as well.
An alternative to garbage collection is the technique of "smart references", in which a reference to a dynamic object itself tracks the number of users and automatically deletes the object when that number becomes zero. A well-known problem with "smart references" is that when a program constantly creates many small short-lived objects in memory (for example, when processing list structures), they lose to garbage collection in performance.
Region-based memory management has existed since the 1960s. It is a technique in which memory is divided into relatively large fragments called regions, and memory is then allocated to individual objects within the regions. With manual management, regions are created and deleted by the programmer; with automatic management, various kinds of conservative estimates are used to determine when all the objects allocated within a region are no longer in use, after which the memory management system deletes the whole region. For example, a region is created in which memory is allocated for all objects created within a certain scope and not passed outside it, and this region is destroyed with a single command when program execution leaves that scope. Moving in memory management (whether manual or automatic) from individual objects to larger units makes it possible in many cases to simplify tracking of object lifetimes and at the same time reduce overhead. Implementations (with varying degrees of automation) of region-based memory management exist for many programming languages, including ML, Prolog, C, and Cyclone.
The Rust programming language offers the concept of "ownership," based on strict compiler control over the correspondence between the lifetime and the scope of objects. The idea is that when an object is created, the variable to which a reference to it is assigned becomes the "owner" of that object, and the scope of the owner variable limits the object's lifetime. When the owner goes out of scope, the object is deleted automatically. By assigning a reference to the object to another variable, it can be "borrowed," but borrowing is always temporary and must end within the lifetime of the object's owner. "Ownership" can be transferred to another variable (for example, an object can be created inside a function and returned as its result), but the original owner then loses access to the object. Taken together, the rules are designed to guarantee that the object cannot be modified in an uncontrolled way through outside references. The compiler statically tracks the lifetimes of objects: any operation that could even potentially lead to a reference to an object being retained after its owner goes out of scope results in a compilation error, which rules out dangling references and memory leaks. This approach complicates programming technique (and accordingly makes the language harder to learn), but it eliminates the need for both manual allocation and freeing of memory and for garbage collection.
The performance of tracing garbage collectors, both latency and throughput, depends to a great extent on the implementation, the workload, and the environment. Simple implementations, or use in environments with very limited memory, especially embedded systems, can lead to very poor performance compared with other methods, whereas sophisticated implementations and use in environments with ample memory can lead to excellent performance.
As for throughput, tracing by its nature requires some implicit runtime overhead, although in some cases the amortized cost can be extremely low, in some cases even lower than one instruction per allocation or collection, which beats stack allocation. Manual memory management requires overhead because of explicit memory deallocation, and reference counting has overhead from incrementing and decrementing reference counters and checking whether a counter has overflowed or dropped to zero.
As for latency, simple garbage collectors stop program execution to collect garbage, which can happen at arbitrary times and last arbitrarily long, making them unsuitable for real-time computing, especially embedded systems, and poorly suited for interactive use or any other situation where low latency is a priority. However, incremental garbage collectors can provide hard real-time guarantees, and in systems with frequent idle periods and enough free memory, such as personal computers, garbage collection can be scheduled for idle time and have minimal impact on interactive performance. Manual memory management (as in C++) and reference counting have a similar problem of arbitrarily long pauses when a large data structure and all of its children are freed, although these occur only at fixed times, independent of garbage collection.
Manual heap
продолжение следует...
Часть 1 Tracing Garbage Collection: Garbage Collection in Programming and Memory Leaks
Часть 2 Determinism - Tracing Garbage Collection: Garbage Collection in Programming and
Comments