Following my previous post about implementing an AVL tree in Objective-C, here’s an ImmutableArray that makes use of it:

ImmutableArray gist

It’s very loosely based on .NET & Mono’s ImmutableList<T>, but follows conventions similar to NSMutableArray (the main difference is most methods return a new ImmutableArray).

The main overhead compared to a regular NSMutableArray is from the extra object allocations and deletions it may need.  If you need to add many objects quickly, retaining a cache of “old” trees and then releasing it afterwards (perhaps asynchronously on a dispatch queue) will squeeze out a little more performance.  Here’s a simple example:

__block NSMutableArray *cache = [NSMutableArray new];
ImmutableList *myList = [ImmutableList empty];

for ( int n = 0; n < 10000; ++ n )
{
    myList = [myList addObject:@( n )];
    [cache addObject:myList];
}

dispatch_async(
    dispatch_get_global_queue( DISPATCH_QUEUE_PRIORITY_BACKGROUND, 0 ),
    ^{ cache = nil; } );

Note this will use a little more memory (as old tree nodes will be retained by the cache).

Finally, here are some rough timings (adding 20000 NSNunbers):

AVL tree (mutable)
2014-01-18 00:24:09.075 AVLTree[99465:303] elapsed subtime = 27.864
2014-01-18 00:24:09.109 AVLTree[99465:303] elapsed subtime = 30.158
2014-01-18 00:24:09.140 AVLTree[99465:303] elapsed subtime = 29.922
2014-01-18 00:24:09.173 AVLTree[99465:303] elapsed subtime = 32.26
2014-01-18 00:24:09.209 AVLTree[99465:303] elapsed subtime = 35.307
2014-01-18 00:24:09.245 AVLTree[99465:303] elapsed subtime = 36.04
2014-01-18 00:24:09.282 AVLTree[99465:303] elapsed subtime = 34.085
2014-01-18 00:24:09.314 AVLTree[99465:303] elapsed subtime = 31.594
2014-01-18 00:24:09.349 AVLTree[99465:303] elapsed subtime = 32.881
2014-01-18 00:24:09.439 AVLTree[99465:303] elapsed time = 391.271

AVL node (immutable)
2014-01-18 00:24:09.540 AVLTree[99465:303] elapsed subtime = 100.848
2014-01-18 00:24:09.617 AVLTree[99465:303] elapsed subtime = 75.399
2014-01-18 00:24:09.694 AVLTree[99465:303] elapsed subtime = 76.56
2014-01-18 00:24:09.771 AVLTree[99465:303] elapsed subtime = 76.792
2014-01-18 00:24:09.857 AVLTree[99465:303] elapsed subtime = 84.679
2014-01-18 00:24:09.940 AVLTree[99465:303] elapsed subtime = 82.133
2014-01-18 00:24:10.021 AVLTree[99465:303] elapsed subtime = 81.026
2014-01-18 00:24:10.105 AVLTree[99465:303] elapsed subtime = 82.746
2014-01-18 00:24:10.197 AVLTree[99465:303] elapsed subtime = 91.938
2014-01-18 00:24:10.287 AVLTree[99465:303] elapsed time = 847.492

ImmutableArray
2014-01-18 00:24:10.363 AVLTree[99465:303] elapsed subtime = 64.775
2014-01-18 00:24:10.447 AVLTree[99465:303] elapsed subtime = 83.325
2014-01-18 00:24:10.526 AVLTree[99465:303] elapsed subtime = 77.767
2014-01-18 00:24:10.606 AVLTree[99465:303] elapsed subtime = 80.301
2014-01-18 00:24:10.718 AVLTree[99465:303] elapsed subtime = 100.795
2014-01-18 00:24:10.808 AVLTree[99465:303] elapsed subtime = 88.625
2014-01-18 00:24:10.897 AVLTree[99465:303] elapsed subtime = 88.9
2014-01-18 00:24:10.988 AVLTree[99465:303] elapsed subtime = 90.065
2014-01-18 00:24:11.076 AVLTree[99465:303] elapsed subtime = 87.954
2014-01-18 00:24:11.169 AVLTree[99465:303] elapsed time = 870.628

ImmutableArray with cache (deferred release)
2014-01-18 01:21:42.137 AVLTree[99599:303] elapsed subtime = 60.761
2014-01-18 01:21:42.210 AVLTree[99599:303] elapsed subtime = 71.828
2014-01-18 01:21:42.293 AVLTree[99599:303] elapsed subtime = 82.437
2014-01-18 01:21:42.379 AVLTree[99599:303] elapsed subtime = 84.563
2014-01-18 01:21:42.470 AVLTree[99599:303] elapsed subtime = 91.247
2014-01-18 01:21:42.557 AVLTree[99599:303] elapsed subtime = 85.93
2014-01-18 01:21:42.630 AVLTree[99599:303] elapsed subtime = 72.06
2014-01-18 01:21:42.706 AVLTree[99599:303] elapsed subtime = 76.108
2014-01-18 01:21:42.788 AVLTree[99599:303] elapsed subtime = 80.562
2014-01-18 01:21:42.873 AVLTree[99599:303] elapsed time = 796.389

NSMutableArray
2014-01-18 00:24:11.180 AVLTree[99465:303] elapsed subtime = 0.176013
2014-01-18 00:24:11.181 AVLTree[99465:303] elapsed subtime = 0.177979
2014-01-18 00:24:11.181 AVLTree[99465:303] elapsed subtime = 0.234008
2014-01-18 00:24:11.182 AVLTree[99465:303] elapsed subtime = 0.231981
2014-01-18 00:24:11.183 AVLTree[99465:303] elapsed subtime = 0.162005
2014-01-18 00:24:11.183 AVLTree[99465:303] elapsed subtime = 0.295997
2014-01-18 00:24:11.184 AVLTree[99465:303] elapsed subtime = 0.153005
2014-01-18 00:24:11.184 AVLTree[99465:303] elapsed subtime = 0.147998
2014-01-18 00:24:11.185 AVLTree[99465:303] elapsed subtime = 0.147998
2014-01-18 00:24:11.186 AVLTree[99465:303] elapsed time = 6.36405

NSMutableArray with locking (@synchronized)
2014-01-18 00:24:11.187 AVLTree[99465:303] elapsed subtime = 0.769973
2014-01-18 00:24:11.188 AVLTree[99465:303] elapsed subtime = 0.718951
2014-01-18 00:24:11.190 AVLTree[99465:303] elapsed subtime = 0.68599
2014-01-18 00:24:11.191 AVLTree[99465:303] elapsed subtime = 0.788987
2014-01-18 00:24:11.192 AVLTree[99465:303] elapsed subtime = 0.699997
2014-01-18 00:24:11.193 AVLTree[99465:303] elapsed subtime = 0.711024
2014-01-18 00:24:11.194 AVLTree[99465:303] elapsed subtime = 0.693977
2014-01-18 00:24:11.195 AVLTree[99465:303] elapsed subtime = 0.721037
2014-01-18 00:24:11.196 AVLTree[99465:303] elapsed subtime = 0.687957
2014-01-18 00:24:11.198 AVLTree[99465:303] elapsed time = 10.95

NSArray (arrayByAddingObject:)
2014-01-18 00:24:11.238 AVLTree[99465:303] elapsed subtime = 39.774
2014-01-18 00:24:11.366 AVLTree[99465:303] elapsed subtime = 127.631
2014-01-18 00:24:11.573 AVLTree[99465:303] elapsed subtime = 205.681
2014-01-18 00:24:11.862 AVLTree[99465:303] elapsed subtime = 288.225
2014-01-18 00:24:12.238 AVLTree[99465:303] elapsed subtime = 375.7
2014-01-18 00:24:12.685 AVLTree[99465:303] elapsed subtime = 446.18
2014-01-18 00:24:13.208 AVLTree[99465:303] elapsed subtime = 522.149
2014-01-18 00:24:13.844 AVLTree[99465:303] elapsed subtime = 635.206
2014-01-18 00:24:14.604 AVLTree[99465:303] elapsed subtime = 759.399
2014-01-18 00:24:15.589 AVLTree[99465:303] elapsed time = 4391.24