Fast low-level arrays

Some apps need fast processing involving variable-length arrays. NSMutableArray is pretty efficient and easy-to-use, but it requires a lot of Objective-C overhead. In this post, I introduce CArray, a low-level, superfast framework for variable-length arrays.

CArray is useful when:

  1. You’re working with C data types — pointers or primitive types or structs thereof;
  2. speed is a problem; and
  3. you don’t want to use cocos2d or a similar library.

CArray can play nicely with NSObject pointers, but it isn’t designed to hold strong pointers (i.e. it won’t call retain on them for you).

Speed

Suppose you’re willing to work with C, C++, or Objective-C, all of which play nicely with iOS. Which of the following function calls is fastest?

cPlusPlusArray.addElement(newElt);  // C++ method call
[objCArray addElement:newElt];      // Obj-C method call
CArrayAddElement(cArray, newElt);   // C function call

The C call is basically always faster than the other two. I could write a whole blog post (easily) about the speed of these three. It gets complicated, but the simple version is that the C++ and Obj-C calls are often comparable in speed (reference), and the C call could be anywhere from 20% faster to twice as fast (reference, see the comments).

Sometimes you may be working with mostly-dumb (i.e. needing very little encapsulation) pieces of data, such as floats or CGPoints (which are structs, not NSObjects). If you use NSArrays, you need to wrap these types in NSNumbers or NSValues. Just the wrapping and unwrapping takes time, in addition to the method call overhead vs straight C function calls. In this situation, CArray is faster by eliminating the overhead.

The root of all evil

Now is a great time to mention one of my favorite Donald Knuth quotes:

Premature optimization is the root of all evil.

I’ve seen a lot of code, and in at least 99.99% of it, the work it takes to replace object-oriented calls by straight C calls would have destroyed readability and maintainability without touching noticeable app speed. Almost all the time, it’s just not worth it. Every once in a while, when Friday the 13th falls on an equinox during a leap year, it’s worth it. That’s when you consider something like CArray.

You’ve been warned.

How to use CArray

int capacity = 16;
CArray *intArray = CArrayNew(capacity, sizeof(int));
int aPrime = 2;
for (int i = 0; i < 10; ++i) {
  CArrayAddElement(intArray, &aPrime);
  aPrime = NextPrimeAfter(aPrime);
}
CArrayFor(int *, intPtr, intArray) {
  printf("%d\n", *intPtr);
}
CArrayDelete(intArray);  // new <-> delete pair as bookends

CArray can also work nicely with pointers. For example, we can give an array a releaser function that it calls on elements as they are removed.

void IntRelease(void *vp) {
  free((int *)vp);
}

CArray *ptrArray = CArrayNew(capacity, sizeof(int *));
ptrArray->releaser = &IntRelease;
for (int i = 0; i < 100; ++i) {
  int *iPtr = malloc(sizeof(int));
  *iPtr = rand();
  // Array grows in capacity as needed.
  CArrayAddElement(ptrArray, &iPtr);
}
// Params are for custom sorting; default is memcmp order.
CArraySort(ptrArray, NULL, NULL);
int **iPtrInArray = CArrayFind(ptrArray, anotherIntPtr);
// Either iPtrInArray == NULL (not found), or *iPtrInArray == anotherIntPtr (found).
CArrayRemoveDuplicates(ptrArray, NULL, NULL);
// Get the 10th int.
int i = *(int *)CArrayElement(ptrArray, 10);
// Remove the 5th element; calls free on it from our releaser.
CArrayRemoveElement(ptrArray, CArrayElement(ptrArray, 5));
// Done with array; deallocate it; calls free on each element for us.
// The calls to free are opt-in; we set this up by setting ptrArray->releaser above.
CArrayDelete(ptrArray);

Even though CArray is so low-level, it’s fairly powerful. It’s also easy to memory manage if you follow the conventions that every CArrayNew is paired with a corresponding CArrayDelete; or CArrayInit paired with CArrayRelease if you want to handle the memory allocation yourself.

Getting CArray

CArray is now part of the moriarty library. Open source, Apache 2 license; free for use in personal or commercial products, including for redistribution (see the actual license for details).

To get the code just click on “Downloads” from moriarty’s github page. Unzip the downloaded file, and copy over CArray.{h,m} into your Xcode project.

PS

Long after writing this code, I learned that cocos2d already has something extremely similar. I basically rewrote ccArray from cocos2d. (Honestly, I’m sure things just like this have existed since the beginning of C. It’s a ridiculously common use case.) Now, there is some contention about the speed of ccArray in cocos2d. For example, this post argues that it’s unfair to count the NSNumber wrapping time against NSMutableArray. Well, technically that’s true. But if you have some time-critical code dealing with arrays of floats, the CArray approach is going to be much faster than the NSMutableArray approach overall (reference). So, in the end, I think the wrapping & unwrapping time is important, although maybe some people won’t want to think of that as part of NSMutableArray’s performance.

There’s also questions of NSMutableArray’s cleverness. I don’t know the implementation details, but based on others’ performance measurements, NSMutableArray does intelligent things under the hood. I don’t know what it does. For some operations, like inserting a new first element to the array repeatedly, NSMutableArray is much faster than CArray. But, if you’re in a position where you need something faster than NSMutableArray, then you need to understand the time complexity of each CArray operation so you can use it optimally — meaning, avoid slow thing like inserting elements at the beginning.

I added this last bit just to basically cover my butt and say “hey guys, I know about cocos2d’s array stuff. Yep, it’s similar.” Also CArray has fast custom sorting, duplicate-elimination, and binary search (which I don’t think ccArray has right now). Holla.

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*