[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Simpler Garbage Collection

From: Greg Parker
Subject: Re: Simpler Garbage Collection
Date: 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 binary * 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 solution.

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 references.)

Greg Parker     address@hidden     Runtime Wrangler

reply via email to

[Prev in Thread] Current Thread [Next in Thread]