Differences between version 11 and predecessor to the previous major change of GarbageCollection.
Other diffs: Previous Revision, Previous Author, or view the Annotated Edit History
| Newer page: | version 11 | Last edited on Friday, October 15, 2004 2:13:54 am | by AristotlePagaltzis | Revert |
| Older page: | version 5 | Last edited on Tuesday, October 7, 2003 1:10:18 pm | by GlynWebster | Revert |
@@ -1,18 +1,22 @@
-GarbageCollection means letting the computer track memory usage and free unused blocks automatically. This works surprisingly well, and is used in many ProgrammingLanguages
- 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 it
won't even negatively impact (in fact, may improve) the performance of an application.
+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.
GarbageCollection protects programmers from
* forgetting to deallocate memory, ie creating memory leaks
* getting in trouble with responsibility, where one part of the code may deallocate a [DataStructure]s still needed by another part
but not from
* filling up all avaliable memory
-* attempting to dereference null pointers or references [1
]
+* attempting to dereference null pointers or references (although languages such as
[ML
] use the type system to do this)
-Antique GarbageCollection systems used reference counting
algorithms[2]. However, they need programmer assistance and reduce performance: reference counting code and reference counter data needs to be inserted all over the place, harming cache coherency. On top of that they're unable to reclaim cyclic [DataStructure]s. It is no wonder they have fallen from favour. However, they do have an advantage that more sophisticated approaches cannot offer without great pains, if at all: timely destruction, which means objects get reclaimed as soon as their last referent has vanished. This can be of immense value for ObjectOrientedProgramming under certain circumstances.
+There are several
algorithms
-''AddToMe: there should probably be separate pages
on !ReferenceCounting
and !MarkAndSweep,
the former having
the above paragraph moved
to.''
+* 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)
.
---
-[1] [ML] languages have a interesting (perhaps obvious) way
of preventing that: there are no null references
, references
can only
be created by applying
a ''ref'' operator
to an existing object. If you want an object
to be optional there is seperate ''option'' type for expressing that
.
+* 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
.
-[2] Older versions of [Python] (those before 2
.1?) used
this. I think
the excuse was
that it was fast
.
+* 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.
+
+* 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
.
+
+----
+StuartYeates did his MSc on GarbageCollection
