Reference counting in FoundationKit

Question

What are the semantics of reference counting as used in the OpenStep FoundationKit?

Answer

Reference counting is a paradigm used in an attempt to solve the issue of the liveness of objects. To this purpose, every pointer to an object is marked through an increment of the object's reference count. Once the pointer to the object is no longer needed the object's reference count is decremented; the object is deallocated when its reference count reaches 0, i.e. when the last pointer to the object has been removed.

FoundationKit semantics

The FoundationKit provides reference counting through 2 basic methods, retain and release. Invoking an object's retain increments the object's reference count; invoking release decreases it. Since a newly allocated object implicitly has a pointer pointing to it, being the return value of alloc, an object returned by alloc is implicitly retained once.

When the last reference to an object is removed by invoking release (i.e. when the number of release invocations equals the number of explicit or implicit retain invocations), the object's dealloc method is invoked. In this method, the object should release all its instance variables (which it should have retained) and invoke [super dealloc]. At the end of this invocation chain, the implementation of dealloc by NSObject actually frees the memory occupied by the object.

There are occasions when an object should have been released by the end of the current method, while it is still needed during the current method and the invocation of release can not be guaranteed or is at least tiresome. Examples of such occasions are when the current method has a lot of return statements or when other methods are invoked which can raise exceptions.
There are other occasions when a direct release is not viable. When a method returns an object to the caller and the caller must get the opportunity to retain the returned object but the callee is no longer interested in the object and wants to release it. An immediate release could result in the object being deallocated and the caller to be returned a bogus value.
For these occasions, the concept of autorelease has been invented. Telling an object to autorelease will cause a release to be sent to the object the moment the current autorelease pool is released. This results in the following semantics: an autoreleased object will not be released before the end of the top-level expression leading to the current method invocation. (Implementation detail: normally, the top-level expression is the application's event loop, which allocates an autorelease pool at the start of an iteration and releases it at the end.)

With the concept of autoreleasing available, all FoundationKit classes provide easy class methods that return an autoreleased object. This concept makes it very easy for the programmer to create anonymous temporary objects, without needing to invoke release all the time.

One other method is available, retainCount. This returns the number of retains to the receiving object minus 1. Thus, if the retain count of an object is 0, the next release will cause its deallocation. retainCount is provided primarily for debugging purposes. (The most common programming errors when using FoundationKit are releasing an object which wasn't retained by the caller and retaining an object but forgetting to release it.)

Implementation

Since the concept of reference counting does not discriminate between objects being referenced, the FoundationKit provides a category to the Object class to allow subclasses of Object to be referenced as well. Since adding instance variables to Object is not really possible---all existing class would have to be recompiled to accommodate the extra instance variable---the reference count of objects is maintained by associating the address of the object with its integer reference count externally, e.g. in a hash table. Of course, an object only is inserted into this hash table upon receiving the first explicit retain.

The existence of this implementation means that subclasses of NSObject, the root class of the FoundationKit, can also be referenced this way. Of course, objects can override the default retain, release, autorelease and retainCount methods and use an explicit reference count in an instance variable in order to speed up the reference counting operations.

Speed

Below is a table indicating cpu time needed for certain operations on a NeXTstation Turbo Mono. All operations are performed 250000 times (weird number, but I had to stop my slab from paging). Note that when assuming an implementation as described before, neither the long time taken by the first release nor the long time for a retain compared to a release can be explained---I suspect that somehow the getrusage granularity has something to do with it.

n = 250000				time	-loop	normalized
					(sec)	(sec)
------------------------------------------------------------------
empty loop:				0.031	     0    0
a[i] = [[NSObject alloc] init]		5.546	 5.515    1
[a[i] retain]			       13.702	13.671    2.48
[a[i] retain]				9.765	 9.733    1.77
[a[i] release]			       11.404	11.373    2.06
[a[i] release]				4.014	 3.983    0.72
[a[i] release]			       12.265	12.234    2.22
[[[NSObject alloc] init] autorelease]	8.952	 8.921    1.62
[current_autoreleasepool release]:     15.433	15.433    2.80
------------------------------------------------------------------

Conclusions: The invocation of autorelease itself costs 13.6 micro seconds, releasing through an autorelease pool increases the cost of the release by 12.8 micro seconds, totalling 26.4 micro seconds. Thus, on a Turbo NeXT, 37900 autoreleases instead of plain releases cost a full second.

Problems

Reference counting has at least one obvious disadvantage, in that cyclic dependencies (such as an object A retains an object B, which in turn retains A) are not handled properly and should be avoided.