Re: Simpler Garbage Collection

[Greg Parker]

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     gparker@apple.com     Runtime Wrangler