This post was originally planned to be about how I’ve adapted the pointer
arithmetic used with standard data a fairly standard data structure to work
NSMutableData in objective-C. However, in making a sample project
to demonstrate this, I’ve expanded it a little to speeding up a very specific
type of array in objective-C.
Motivation in image processing
I have been working recently on some image processing algorithms, one of which
required a priority queue of pixel locations. Now, this essentially requires a
list of integers, but since images have lots of pixels, it’s a very long list.
NSArray is a really useful all-purpose collection class used an awful lot
in objective-C. The one ‘restriction’ is that it is a collection of objects -
it’s not possible to collect primitives in an NSArray without wrapping them in
NSNumber is an object which represents all the different number
types and, more often than not, wrapping your numbers in this is the best way
to go. However, I mentioned that I want to build a list of a large number of
integers (think tens of millions). At this point, the overhead of wrapping
NSNumber to put them in an
NSArray becomes significant.
In the past, when doing image processing work, it is at this point I would
drop down to C (from python, matlab, ruby etc) and use low-level memory management
functionality to exactly create the data structures as expected. This is also
an option when using objective-C - it’s just a superset of C, so
it’s associated functionality are available to use. However, in using this
we loose all of the memory management functionality made available by
objective-C. There is another way though -
NSMutableData as a chunk of memory
NSMutableData is a class which provides the user with a writeable contiguous block of
memory of a given size. It inherits from
NSObject so the memory management
of reference counting and autorelease pools comes for free. It also has the
advantage that we can ask for the block of memory to be dynamically resized and
iOS will take care of this for us. There is one proviso with this - and that is
that iOS reserves the right to move our block of data (primarily when resize
is requested). This makes perfect sense, but does cause some issues with
standard pointer-based data structures.
In this post I’ll describe how to implement a basic linked-list of integers using
NSMutableData and compare its performance to that of an
Linked lists are one of the simplest pointer-based data structures. It is a collection of nodes, each of which contains some data and a pointer to where you can find the next element in the list. I’m not going to talk much more about them - checkout Wikipedia - it knows all.
As I mentioned before, there is an issue when using pointers with
in that you cannot guarantee that your block of data won’t be moved around.
Therefore, instead of using a pointer to the next node, we record the offset.
Whenever the block of memory is relocated, the pointers of each node will change,
but their relative offset from the front of the block will remain the same:
In order to demonstrate this process with a toy project, I defined a pretty simple protocol which my dynamically-sized arrays should implement:
I’m not going to reproduce the entirety of the code within this post, but I’ve put together a sample project on GitHub to demonstrate it, so you can pull it down from there. It’s at github.com/sammyd/LinkedList-NSMutableData.
At initialisation time we create a cache of nodes of the correct size and then initialise it:
Every time we further extend the nodeCache then we’ll need to initialise the newly created nodes, so have pulled that out into another method:
Pushing a new value into the array is pretty simple:
Pushing to the end of the array is pretty similar - both use a method which gets them the next free node:
This method is the one responsible for resizing the nodeCache if required.
NSMutableData has the method to
increaseLengthBy:, it’s just a matter
of setting them as empty nodes and resetting the free node location. It
is at this point that pointer-based addressing would fail since the memory
block is likely to move location. We could implement a method which loops
through all the existing nodes and updates their pointers, but the offset
addressing seems cleaner and works just as well.
And finally, the last method required by the protocol is popping nodes:
Here we grab the first node, move the ‘pointer’ to the first node to the second node, move the old first node to the available nodes cache and return the value.
Obviously, this kind of code is perfect for some unit testing. I’ve written the bare bones of a test suite - enough to iron out one or two bugs I came across. I’m not going to bore you with the tests here in this blog, but they’re in github.
As a comparison, I have made an implementation which uses
salient parts are below:
Profiling the two approaches
The original purpose behind this work was dealing with large numbers of integers in an array, so to compare the two approaches we’ll see how long it takes to push 10 million integers into the array and then popping them off again:
The demo app in the github repo allows the user to run this once with each implementation and displays the results. The following is a screen shot from running it on the simulator on my ageing MacBook.
As you can see, for 10 million integers, the linked list implementation is significantly
faster - over 3 times faster in fact. Since the integers don’t have to be wrapped in
the memory footprint is also smaller.
So, I’ve managed to create a basic array implementation which is faster than
for primitive data types. I’m not suggesting that it should replace
NSArray - far from
it. For 99% of cases,
NSArray is likely to be the best choice. But if you’ve got
a large number of primitive types you need to put in an array, then it might be worth
NSMutableData and building your own implementation.
Use the demo implementation on github at your own risk. I built it to discover whether significant performance gains are possible
- it’s not necessarily production-ready ;)