Annotated edit history of
GarbageCollection version 11, including all changes.
View license author blame.
| Rev |
Author |
# |
Line |
| 11 |
AristotlePagaltzis |
1 |
GarbageCollection means letting the computer track memory usage and free unused blocks automatically. This works surprisingly well, and is used in many ProgrammingLanguage~s -- in just about every very high level language, and also [Java]. Since manually managing memory is notoriously difficult, GarbageCollection can cut a huge portion out of development time and nowadays won't even negatively impact (in fact, may improve) the performance of an application. |
| 4 |
AristotlePagaltzis |
2 |
|
| |
|
3 |
GarbageCollection protects programmers from |
| |
|
4 |
* forgetting to deallocate memory, ie creating memory leaks |
| |
|
5 |
* getting in trouble with responsibility, where one part of the code may deallocate a [DataStructure]s still needed by another part |
| |
|
6 |
|
| |
|
7 |
but not from |
| |
|
8 |
* filling up all avaliable memory |
| 6 |
StuartYeates |
9 |
* attempting to dereference null pointers or references (although languages such as [ML] use the type system to do this) |
| 4 |
AristotlePagaltzis |
10 |
|
| 6 |
StuartYeates |
11 |
There are several algorithms |
| 4 |
AristotlePagaltzis |
12 |
|
| 11 |
AristotlePagaltzis |
13 |
* Reference counting. Antique GarbageCollection systems (and some [C++] [Template]s) use reference counting algorithms. This involves marking every block in memory with a counter to how many times it is referenced and deallocating it when the count reaches zero. This is gentle on the cache and closely ties the deallocation to the operation that made a block unreachable. Unfortunately they are unable to reclaim cyclic DataStructure~s (such as doubly linked lists). |
| 5 |
GlynWebster |
14 |
|
| 11 |
AristotlePagaltzis |
15 |
* Copying algorithms periodically sweep the entire memory for objects still in use and move these to one "end" of the memory, much as some disk de fragmenters work. This technique can be very efficient, since only the active objects are moved the cost is dependant only on the size of the active memory rather than the total memory (this assumes that no finalisers are being run and that page-level memory operations are avaliable). Unfortunately this copying requires a global read/write lock on memory and the ability to change pointer on the stack to point to the new locations of objects. Because copying algorithms leave all the free memory in a single block they also solve memory fragmentation problems. |
| 5 |
GlynWebster |
16 |
|
| 11 |
AristotlePagaltzis |
17 |
* Mark and Sweep algorithms periodically sweep the entire memory for objects no longer in use and deallocate them. With a little inguenity this can be done in a back-ground thread or process. These are less efficient than copying algorithms, because the deallocation cannot normally be achived using the page-based memory operations. |
| 6 |
StuartYeates |
18 |
|
| 11 |
AristotlePagaltzis |
19 |
* Train Algorithms are an innovation on copying and mark and sweep algorithms. Based on the observation that most objects are very short lived they divide memory into generations (either physically or virtually) and concentrate their attention on the most recently allocated generations. |
| 6 |
StuartYeates |
20 |
|
| |
|
21 |
---- |
| |
|
22 |
StuartYeates did his MSc on GarbageCollection |
