I wrote a post some time back on the value of singletons in a garbage collected language as an important component of scalability. The majority of my work these days targets Apple iOS devices and so a reduced memory footprint and overall memory management is not only fundamental but paramount. The use of singleton objects and an effective caching strategy are simple patterns to get you started.

I suggest reading Apple’s Thread Programming Guide as a prerequisite, which also covers some of the basic concepts behind Blocks and Grand Central Dispatch (GCD).

Singletons

For purposes of this discussion, a singleton is a class that only allows a single instance of itself to be created within an operating system process.

Apple’s documentation on creating a singleton recommends a pattern that works for most iOS applications but is not thread-safe. Beginning with iOS 2.0 and prior to iOS 4.1, one of the most widely used methods to introduce a thread-safe singleton was through the use of the @synchronized directive.

1
2
3
4
5
6
7
8
9
+ (MyClass*) instance {
    static MyClass *gInstance = nil;
    @synchronized(self) {
        if(nil == gInstance) {
            gInstance = [[MyClass alloc] init];
        }
    }
    return (gInstance);
}

There are a few inefficiencies with this approach because not only generates a recursive mutex lock but also introduces an exception handler. Specifically, Apple’s documentation indicates that as a precautionary measure, the @synchronized block implicitly adds an exception handler to the protected code. This handler automatically releases the mutex in the event that an exception is thrown. This means that in order to use the @synchronized directive, you must also enable Objective-C exception handling in your code. If you do not want the additional overhead caused by the implicit exception handler, you should consider using the lock classes.

At the time of this writing, the @synchronized directive turns into this basic pseudo-code:

1
2
3
4
5
6
7
8
id _eval_once = ;
objc_sync_enter( _eval_once );
@try {
    /* code goes here */
}
@finally {
    objc_sync_exit( _eval_once );
}

For implementation details see: http://www.opensource.apple.com/source/objc4/objc4-437.1/runtime/objc-sync.m

Much of Apple’s sample code prior to iOS 4.0 use this approach. There is a technically more efficient and lock-free approach for applications that target operating systems earlier than Mac OS X version 10.5 or iOS 4.0.

1
2
3
4
5
6
7
8
9
10
+ (MyClass*) gInstance {
    static void * volatile gInstance = nil;
    while (!gInstance) {
        MyClass *temp = [MyClass [alloc] init];
        if(!OSAtomicCompareAndSwapPtrBarrier(0x0, temp, &gInstance)) {
            [temp release];
        }
    }
    return (gInstance);
}

You can read more about preferred versions of the atomic and synchronization operations here.

For applications that target operating systems equal to or greater than Mac OS X 10.6 or iOS 4.0, the recommended singleton pattern uses dispatch_once, which relies on components of Grand Central Dispatch (GCD).

1
2
3
4
5
6
7
8
9
+ (MyClass *) instance {
    static MyClass* gInstance = nil;
    static dispatch_once_t pred;
 
    dispatch_once(&pred, ^{
        gInstance = [[MyClass alloc] init];
    });
    return (gInstance);
}

It should go without saying but I’ll do so for completeness. All instance-level methods of classes that implement a singleton pattern MUST be thread-safe.

NSCache

I suspect this class remains relatively unused by most iOS developers. NSCache is essentially a container that it stores key-value pairs but unfortunately does so without an O(1) time complexity (like that of NSMutableDictionary) but does automatically evicts objects from its store when the ‘cost’ (a heuristic that of course involves memory pressure) of the cache rises above a configurable threshold.

Per Apple’s documentation, NSCache objects differ from other mutable collections in a few ways:

  • The NSCache class incorporates various auto-removal policies, which ensure that it does not use too much of the system’s memory. The system automatically carries out these policies if memory is needed by other applications. When invoked, these policies remove some items from the cache, minimizing its memory footprint.
  • You can add, remove, and query items in the cache from different threads without having to lock the cache yourself.
  • Retrieving something from an NSCache object returns an autoreleased result.
  • Unlike an NSMutableDictionary object, a cache does not copy the key objects that are put into it.These features are necessary for the NSCache class, as the cache may decide to automatically mutate itself asynchronously behind the scenes if it is called to free up memory.

Though not required, NSCache works in conjunction with objects that implement the NSDiscardableContent protocol in that the discardContentIfPossible method is called when an object is removed.

The two most widely used caching strategies are proactive and reactive loading.

  1. Proactive Cache Loading. A proactive cache loading strategy attempts to retrieve all required state when a process or application starts and cache it for the lifetime of the process or application. A decision to use a proactive cache loading strategy is generally done so in conjunction with either asynchronous pull loading based on expected not actual usage of the information being cached or notification-based loading whereby an application’s services are notified when cached state changes.
  2. Reactive Cache Loading. A reactive cache loading strategy retrieves data as it is requested by the application and caches it for future requests. A decision to use a reactive cache loading strategy is generally done so in conjunction with synchronous pull loading since the pattern is relatively easy to test and implement.

Regardless of the selected caching strategy, determining a cache expiration policy is is key for most applications. There are a plethora of expiration policy patterns but the majority of them fall into the following general categories:

  • Time-based. Cached information is invalidated based on relative (sliding window) or absolute time periods.
  • Notification-based. Cached information is invalidated based on instructions from a source.
  • Counter-based. Cached information is invalidated based on a reference counts.

Regardless of the expiration policy, scavenging based on memory pressure and other heuristics are key to a proper cache design and symmetry of that design is a key component in any distributed algorithm.

For most applications, a reactive cache loading strategy with a synchronous pull model is the most appropriate option. NSCache does evict objects based on memory pressure and so I strongly recommend you implement the NSDiscardableContent protocol for any objects you plan to store in NSCache. NSDiscardableContent is a simple counter-based pattern. For information stored in NSCache that represents NSData objects, Apple provides the NSPurgeableData class. NSPurgeable data inherits from NSMutableData and is available in iOS 4.0 and Mac OS X 10.6 and later. A description of how to use this class can be found be reading Caching and Purgeable Memory.

I’d like to make one last point. Please be careful not to over-engineer your caching strategy but be elegant about your design.