[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Simpler Garbage Collection
Re: Simpler Garbage Collection
Mon, 7 Jul 2008 14:53:26 -0700
On Jul 6, 2008, at 6:00 AM, David Chisnall wrote:
So, I've been thinking for a while that the implementation of GC
that Apple seem to have settled upon is, to be polite, a complete
disaster. The need for weak pointers means that it has no
advantages over ref counting and lots of disadvantages.
One thing that Apple seem to have forgotten is that reference
counting is a form of GC - replacing it with a tracing collector
doesn't make much sense, especially if it's a very poor tracing
collector, and adding GC to the compiler, rather than the library,
goes against the spirit of Objective-C.
Reference counting is just memory management. Only *automatic*
reference counting is GC. The problem with a library-only solution is
that it won't be automatic.
The design constraints for Apple's garbage collector include:
* Be fully automatic for high-level Objective-C code
* Be usable in lower-level code, perhaps with extra programmer work
* Run existing CoreFoundation-based code unchanged
* Support both GC and non-GC operation from a single shared library
* Perform well with dozens of threads and heaps of hundreds of MB,
without hurting responsiveness for UI and media playback.
"Fully automatic" rules out anything that honors existing -retain/-
release/-autorelease. Heap size and responsiveness ruled out stop-the-
world collectors like Boehm. We did look at some automatic reference
counting algorithms, but went with a tracing system instead.
Reference counting works quite well, and doesn't have very large
overheads (it also plays nicely with swapping, which tracing doesn't
and leads to some quite pathological behaviour if you have low
memory), but it has one significant flaw - it doesn't handle
cycles. Adding a cycle detector to NSObject seemed like a better
Adding a cycle detector to a manual retain/release system solves
cycles. It does not solve over-retaining and (depending on the defined
behavior) doesn't solve over-releasing either.
I recently came across a paper from 2001 which suggests exactly
this. They observe that you only need to scan for cycles when -
release is called and the retain count is > 0. They propose a very
efficient algorithm for doing this, which we can make slightly more
efficient (they suggest deferring the cycle detection. If we defer
it until the current autorelease pool is popped then we can delete a
load of objects that might have been cycles and carry on).
But how do you detect cycles? The retain count is insufficient to
identify cycles - you also need to know which other object is
responsible for each retain. Discovering that looks much like a
tracing collector, especially in highly-connected cycle-rich code like
AppKit views and windows.
How do you handle non-retained references in existing code? You might
have two pointers but only one retain. If the object is then released,
do you delete it and leave the non-retained reference dangling? Or do
you keep it alive, and end up with a cycle that your detector won't
see? (The usual answer is "the compiler adds retain/release to
assignments so there are no non-retained references" plus "use zeroing
weak references if necessary". I have not seen a high-performance
automatic reference counting algorithm that also supports zeroing weak
Greg Parker address@hidden Runtime Wrangler