Sweetened Cocoa: A Pinch of C++

In the last couple of blog entries, we talked in general terms about how you can sweeten your Cocoa with a bit of C++, and covered a bit of history to help us understand how Objective-C and C++ are related.

Now it's time to get serious about actually applying this stuff.

There are basically three ways to think about combining ObjC and C++ in a project:

  • mostly C++, calling through to Cocoa for UI support
  • mostly ObjC, with a few C++ bits thrown in as needed
  • mostly ObjC, but with extensive use of a few really handy C++ classes


We're going to start with the middle approach, which is the easiest place for most Cocoa programmers to begin.  And to illustrate, I'm going to present an actual, real-life, not-making-this-up case study that happened in our office a little while back.

We were working on InkPaint, and had the need to do a flood-fill operation on a mask buffer.  The algorithm for this is well known, and wasn't too hard to implement in standard Cocoa.  It's basically a recursive algorithm, but unwound by keeping our own work stack.

    NSMutableArray *toDoList = [NSMutableArray arrayWithCapacity:1000];
    [toDoList addObject:[NSNumber numberWithInt:(contentSize.height - startPoint.y) * ystep + startPoint.x]];

    while (toDoList.count) {
        int pixelIndex = [[toDoList lastObject] intValue];
        [toDoList removeLastObject];
        int x = pixelIndex % ystep;
        int y = pixelIndex / ystep;
        
        // check this item in our ink buffer; if it's not black, then
        // set that pixel in our mask to 1, and add its neighbors to
        // our to-do list.
        UInt32 inkColor = inkBuf[y * inkPixPerRow + x];
        UInt8 inkAlpha = inkColor & 0xFF;
        if (inkAlpha > 0xCC) continue;  // hit an opaque ink pixel; nothing to do here
        
        maskBuf[pixelIndex] = 1;
        if (x > 0 && !maskBuf[y*ystep + (x-1)]) {
            [toDoList addObject:[NSNumber numberWithInt:y * ystep + (x-1)]];
        }
        if (x < contentSize.width-1 && !maskBuf[y*ystep + (x+1)]) {
            [toDoList addObject:[NSNumber numberWithInt:y * ystep + (x+1)]];
        }
        if (y > 0 && !maskBuf[(y-1)*ystep + x]) {
            [toDoList addObject:[NSNumber numberWithInt:(y-1) * ystep + x]];
        }
        if (y < contentSize.height-1 && !maskBuf[(y+1)*ystep + x]) {
            [toDoList addObject:[NSNumber numberWithInt:(y+1) * ystep + x]];
        }        
    }

 
We coded this up, and it worked.  But the problem was that it was slow.  Dog slow.  No, that's an insult to dogs; our app would sit there and chug for over 4 seconds every time we tapped the screen.

It's not too hard to see why it was so slow; we're creating a bunch of NSNumbers every time we add stuff to the stack, which then get retained by the mutable array, and then released and destroyed when we pop them off.  All that boxing and unboxing is required because NSMutableArray can only hold objects, and not (for example) integers.  But, unfortunately, it also makes the code slow (and, to be fair, it makes it ugly as well).

So I pulled out an old friend from years back: a little vector class (SimpleVector.h/.cpp).  This is an STL-ish template class, but doesn't depend on the STL.  That was good for us, because we didn't want to drag that whole can of worms into our Cocoa project just to see if we could speed up this algorithm.  Instead we just changed the extension of this Cocoa source file from ".m" to ".mm", activating the Objective-C++ compiler, #included SimpleVector.h, and then changed the code above to:

    SimpleVector<UInt32> toDoList;
    toDoList.push_back((contentSize.height - startPoint.y) * ystep + startPoint.x);

    while (toDoList.size()) {
        int pixelIndex = toDoList.pop_back();

        int x = pixelIndex % ystep;
        int y = pixelIndex / ystep;
        
        // check this item in our ink buffer; if it's not black, then
        // set that pixel in our mask to 1, and add its neighbors to
        // our to-do list.
        UInt32 inkColor = inkBuf[y * inkPixPerRow + x];
        UInt8 inkAlpha = inkColor & 0xFF;
        if (inkAlpha > 0xCC) continue;  // hit an opaque ink pixel; nothing to do here
        
        maskBuf[pixelIndex] = 1;
        if (x > 0 && !maskBuf[y*ystep + (x-1)]) {
            toDoList.push_back(y * ystep + (x-1));
        }
        if (x < contentSize.width-1 && !maskBuf[y*ystep + (x+1)]) {
            toDoList.push_back(y * ystep + (x+1));
        }
        if (y > 0 && !maskBuf[(y-1)*ystep + x]) {
            toDoList.push_back((y-1) * ystep + x);
        }
        if (y < contentSize.height-1 && !maskBuf[(y+1)*ystep + x]) {
            toDoList.push_back((y+1) * ystep + x);
        }        
    }


Comparing the two, you should be able to quickly see that these do the same thing (though the latter is has considerably less noise syntax around what it's doing).  But more importantly, it was fast: 0.5 seconds, versus 4.2 for the Cocoa version.  That's over an 8X speedup!
Speed increase graph
No other changes to the code were required; it really was that easy.  C++ didn't start creeping into the rest of the code, taking over like a zombie plague.  It was content to just help with the heavy lifting, where pure ObjectiveC wasn't quite good enough.

Next week, we'll talk about the opposite extreme: an app written mostly in C++, but with enough Cocoa to make it run natively on an iPhone or Mac.  That's an approach that's useful mainly for cross-platform development, though it may be a good fit in a few other circumstances as well.  After that, we'll get to the third case, and perhaps the most interesting one: using mostly standard Cocoa, but with liberal use of some really handy wrapper classes.  Stay tuned!