Simpler Garbage Collection

[David Chisnall]

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

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

I have started implementing this, and it shows potential.  For now, I  
will develop it in an external framework, and move it into GNUstep  
base later if other people are interested in it.

One other thing I have been pondering is altering the behaviour of  
NSAutoreleasePools so that:

1) +alloc adds the newly-created object to the autorelease pool.
2) -autorelease is a no-op
3) Objects are only free'd when their ref count is 0 and the top  
autorelease pool is pop'd.

This would make interacting with GNUstep from other languages (which  
expect full GC) simpler, and would simplify memory management since  
every created object would have a refcount of 1 (irrespective of how  
it was created) and autorelease would never need to be explicitly  
called.

Thoughts?

David