Weak Referencing Dictionary
Kolin Krewinkel, the talented developer behind the App.net client Stream, shared an interesting article on NSMapTable tonight. In the article, Charles Parnot subjects NSMapTable to a battery of tests to see if it performs as promised. The results were surprisingly disappointing.
For those not familiar, NSMapTable is best described as a mutable dictionary with weak referencing capabilities. Typically, you use a map table when you need a collection of objects in which each object persists as long at least one other object in your app has a strong reference to the it.1 For example, if you were writing an App.net client, you might want to store a local cache of user objects in a map table. As long as at least one post or profile view controller keeps a strong reference to a given user, the map table will keep a reference to the user, too. In short, it’s a way to keep things around as long as you need them, without having to manually keep track of when you no longer need them.
The problems that Parnot uncovered are related to what happens after all other objects have released an object that is a member of a map table. The expected behavior is that both keys and values for these objects will be released. In practice, the results are unpredictable. Often, only half of such objects actually get removed from the collection. The rest are just hanging around and may never get purged in a non-garbage-collected environment like iOS.
On a whim last year, I tried writing an alternative to NSMapTable that would perform the same function, but that would be able to run on iOS 5 (NSMapTable is only available on iOS 6 or later). I put the result up on Github. It’s a funny little thing. It was written before my morning coffee, so I don’t recommend using it in a production app unless you absolutely need to. Nonetheless it worked as expected in my limited tests. Here’s how it was put together:
JTSWeakReferencingDictionary
The technique begins by adding an object via a category method on NSMutableDictionary, jts_setWeakReferencedObject:forKey: You add the object you want to be weakly referenced with this method instead of using the standard method.2.
This method does not add the object to the dictionary directly, but instead wraps the object in an NSValue using valueWithNonretainedObject. Later on, this plays a crucial role.
Just before adding the NSValue from step 2 to itself, the dictionary sets a custom property on the object passed into step 1 (the object we want to weakly reference). This is accomplished via associated objects, a form of voodoo too supernatural to cover here. The custom property is a strong reference to an instance of JTSDeallocNotifier, a subclass of NSObject that notifies a delegate whenever it is about to be deallocated. The mutable dictionary sets itself as the delegate of the dealloc notifier.
So at this point, each object passed into step 1 is given a JTSDeallocNotifier and wrapped in a weak-referencing NSValue. The NSValue is then added to the mutable dictionary.
As long as at least one other object in your app retains the weak-referenced object, it will persist via the NSValue as a member of the dictionary.
When all strong references to the object are broken, the NSValue’s weak reference will be zeroed, and ARC will begin the process of deallocating the object and cleaning up the object’s own references. During this process, the object’s JTSDeallocNotifier is also deallocated since no other object retains it.
Inside of JTSDeallocNotifier’s dealloc implementation, it notifies its delegate that it is about to be deallocated.
The mutable dictionary receives the message from the dealloc notifier. The dealloc notifier has a key that is a copy of the key passed in step 1 when the original caller added the weak-referenced object to the dictionary. Using this key, the dictionary knows which NSValue it should remove from itself.
The dictionary removes the NSValue for the key from step 8.
At this point, ARC finishes its deallocation steps, and the weak-referenced object, its dealloc notifier, and the NSValue are all released.
I ran brief tests of this technique with collections of 10 to 20 objects, using GCD and blocks to experiment with timing. Everything worked as expected.