Adding Sorted Inserts to Cocoa Arrays

NSArray and NSMutableArray have methods for sorting arrays, NSArray returns new sorted arrays and NSMutableArray can be sorted in place. The sort methods comes in three flavours; using a function, using a selector, or using an array of NSSortDescriptor objects.

NSArray admits to sorts being a slow operation, and adds a method pair for comultive sorts using hints. This way the operation is done in O(P*LOG(P)+N) time, instead of O(N*LOG(N)). Where N is number of elements, and P is number of additions and deletions since the last sort. Unfortunately that do not work on NSMutableArray. So even if memory consumption will not hit the roof, release retain cycles will take it’s toll.

So why not add methods to find the insertion points, and insert new objects into already sorted NSArray and NSMutableArray object? Best case for inserting single elements should be O(LOG(N)^2), so lets hit that target. And on the way there, we will learn how to;

  • Add functionality to standard classes using categories.
  • Implement high performant Obj-C code for tight loops.

New Categories on NSArray and NSMutableArray

This will become a bit complex on the inside, but the public front should be as simple as this:

Base Implementation

We want to follow suit with NSArray and NSMutableArray, so we too shall support inserts based on functions, selectors, and an array of sort descriptors. In practice we only need to implement indexForInsertingObject:sortedUsingfunction:context:, the other methods can use this one, each with a private compare method of their own. So we begin by implementing this method.

The Objective-C runtime header is included so we can go around the usual method dispatch, and instead use the method implementations as function pointers. In most cases this is a neglectable optimization, for this case we will be the bottle neck since we are intended to be the low level API.

The algorithm is a simple binary search, and we have a worst case O(LOG(N)^2) time for index search. Using this for implementing the sibling method in NSMutableArray is as simple as this:

Sort Using Selector

With functions in place, writing a utility compare function that uses selectors, and can be used with our indexForInsertingObject:sortedUsingfunction:context: method is a breeze.

Notice that objc_msgSend(id, SEL, ...) is used instead of the performSelector:withObject: method. This is a small performance improvement, as what performSelector:withObject: do behind the scene is just a call to objc_msgSend() anyway. We have removed one method invokation per compare.

Sort Using Sort Descriptors

Or rather sort with an array or NSSortDescriptor objects. This will be the least performant, but also the most flexible sort. An array of sort descriptors is used because we want to be able to sort using several criteria, one sort descriptor per criteria. For example when sorting on last name, then first name, or even more complex sorts.

A NSSortDescriptor is initialized with a key, sort order (ascending or descending) and optionally a selector to do the comparison with, by default compare:. There are quite a few method invokations involved, and it will be good for performance to avoid as many as we can.

Just as performSelector:withObject: uses objc_msgSend() behind the scene, so do objc_msgSend use a function pointer internally. After doing a hash-table lookup with the selector as key that is. This look-up is cached and very fast, but avoiding it all together is always faster. So let us fetch those when the category is first loaded, and do our calls straight through the functions pointers avoiding at least two or more function calls for each compare operation.

The class method inilialize is kind of magic, it is called once for each class and category, when the class or category is loaded into the run-time. It is the Obj-C equivalent of static initializers.

With the function pointers to the hot-spot method implementations in hand, here is the fast implementation:

Conclusions

The fact that Objective-C is a strict superset of C have some good benefits. The obvious one is that your Obj-C code is both source-code and binary compatible with the vast collection of code that has been written in C over the past 30+ years.

The second benefit is that when performance is needed, Obj-C gives us as developers full access to the internals of the dynamic run-time.

But best of all, most developers never need to care. They can, blissfully unaware, reap the benefits of the performance tuning under the hood. Tuning by both Apple and considerate third party library developers willing to go the extra mile (or a few metres at least).

The code is released under BSD license, and works on both Mac OS X and iPhone OS. You can download it here.

9 Comments

  1. It looks very useful, although personally I would want to see a simpler API for the most common cases: for instance, it would be nice to have a version of the sorted insert methods that don’t require a sorting method to passes in, and would instead simply use the compare: selector. That way it would immediately work with NSNumber, NSString and NSDate, and you could support new objects easily by implementing compare: for those classes.

    Thanks for sharing the concept and the code!

    • For the most common use cases you mentioned, you can use for example: [myArray insertObject:myDate sortedUsingSelector:@selector(compare:)];.

      As a rule of thumb; in Cocoa you should not make wrapper code to simplify something that is already a single statement. Making this even simpler by enforcing a single selector would also break the 1 to 1 feature mapping of the sort methods already available in the official Cocoa classes.

  2. Thank you for this very relevant article. It’s a mystery why there is no SortedCollection counterpart in Cocoa/NextStep from the Smalltalk-80 environment, which so clearly have been the main inspiration for Objective-C.

    Cheers
    Rikard

  3. Ilya Levin

    Very nice addition, but you have a fatal bug. Your search should be compare (…) >0 instead of compare(…) < 0 for it to work, because NSOrderedAscending is returned when the second object is larger then the receiver, which means we need to the lower part of the search range, not the apper part (as long as the same comparison is used as the one used to sort the array)

  4. Great work! I created a small repository on Github to hold a debugged version of the code: http://github.com/benlenarts/NSArray-CWSortedInsert

  5. Hello! I could have sworn I’ve been to this blog before but after checking through some of the post I realized it’s new to me. Anyhow, I’m definitely glad I found it and I’ll be book-marking and checking back frequently!

  6. Vladimir

    This code will crash on arm64 (e..g, iPhone 5s), unfortunately :( this is because objc_msgSend can no longer be used as a variadic function, but must be cast into a non-variadic form. Instead of this:

    static NSComparisonResult cw_SelectorCompare(id a, id b, void* aSelector) {
    return (NSComparisonResult)objc_msgSend(a, (SEL)aSelector, b);
    }

    You should use this:

    static NSComparisonResult np_cw_SelectorCompare(id a, id b, void* aSelector)
    {
    NSComparisonResult (*compareFunction) (id, SEL, id) = (NSComparisonResult(*)(id, SEL, id))objc_msgSend;
    return compareFunction(a, (SEL)aSelector, b);
    }

    For more information, see here:

    https://developer.apple.com/Library/ios/documentation/General/Conceptual/CocoaTouch64BitGuide/ConvertingYourAppto64-Bit/ConvertingYourAppto64-Bit.html#//apple_ref/doc/uid/TP40013501-CH3-SW26

  7. Vladimir

    Calling naked IMP functions also won’t work (e.g., in indexForInsertingObject:…). Again, they must either be cast into the type of the target function (non-variadic), or not be used altogether.

Trackbacks for this post

  1. Sorting NSArray at Under The Bridge

Leave a Reply