mikeash.com: just this guy, you know?

Posted at 2006-07-14 00:00 | RSS feed (Full text feed) | Blog Index
Next article: Getting Answers
Previous article: Autorelease is Fast
Tags: c++ chemicalburn cocoa objectivec stl
Using Evil for Good
by Mike Ash  

People who know me as a programmer probably know that I am a great hater of C++. As someone who does a lot of Cocoa, this extends naturally into hating Objective-C++. But I made good use of Objective-C++ in ChemicalBurn and I thought I'd share.

I've been quoted as saying things such as:

ObjC++ also allows you to create an incredible menagerie of abominations such as the world has never seen
Indeed, I shudder every time I think about the autoptr/autorelease or exceptions conversion wrappers I've seen people construct. On the other hand, C++ does have a lot of fast, standard data structures.

Ordinarily I don't sympathize much with people who complain about Cocoa lacking data structures. It's true that having nothing but arrays", sets, and dictionaries can be a bit limiting at times. On the other hand, people who complain about the limited choice tend to be complaining for its own sake, and don't have any actual need for other things.

And really, you can press these things into service reasonably well in place of other data structures. NSMutableArray makes for a fine stack and a decent (if slowish) queue, and NSDictionary and NSSet take care of many of the things that a tree structure would be used for in other languages.

But sometimes you just need something better. ChemicalBurn 1.0 is about ten times faster than the first working version I produced that I deemed acceptable. A good chunk of the optimization was giving up Cocoa drawing and moving to OpenGL. Once that was done, I profiled the app and noticed that it was spending approximately all of its time doing route finding.

As we all know, the best optimizations are algorithmic improvements. If you have a reasonably large data set, all the low-level diddling in the world won't save you as much as switching from an O(n^5) to an O(n^3) algorithm.

ChemicalBurn uses Dijkstra's algorithm to perform pathfinding. It's a fairly straightforward algorithm. Basically, you brute-force all of the connections, but do it in a clever way so that you can stop your search early.

One of the key structures used in this algorithm is the set of all untraversed nodes. Every time through the algorithm's outer loop, the node with the lowest cost is removed from that set and examined. If that node is your destination then your work is complete, otherwise you use that node to update the cost of all the other nodes.

The simple implementation of that set is to just keep all of the nodes in no particular order. Then you can scan them all and pick out the smallest one. This takes O(n). In the worst case this is done n times, once per node, and then in each node we need to perform n-1 operations in order to compare the cost of connecting to every other node in the graph. This makes the final performance O(n^3), which is not so great.

The obvious fix for this is to use a priority queue for the set of untraversed nodes. This changes selection from O(n) to O(lg n), making the entire algorithm run at O(n^2 lg n), a clear improvement.

But, oops, Cocoa doesn't have a priority queue. I went hunting around for an implementation but I couldn't find a decent one, and I didn't feel like writing one myself. Finally, I realized that STL probably had one, so I looked it up and sure enough, it does. And better yet, it has priority queue algorithms that work on plain C arrays, so I could wrap a Cocoa class around a plain C array and dump in the STL algorithms and I'm all set.

Without further ado, here's my (short) implementation of the wrapper. You may use it at will in any place and for any purpose which does not involve radioactive monkeys. Oh, and don't ask me why I called it an OrderedQueue instead of a PriorityQueue or a Heap, I really couldn't tell you:

// .h
@interface ChemicalBurnOrderedQueue : NSObject {
	struct CBOQNode*	mObjs;
	unsigned			mCount;
	unsigned			mCapacity;
	
	BOOL				mHeapified;
}

- init;

- (unsigned)count;
- (void)addObject: (id)obj value: (unsigned)val;
- (id)pop;

@end

// .m
#import 


struct CBOQNode {
	id obj;
	unsigned val;
};

static bool NodeLessThan( struct CBOQNode &n1;, struct CBOQNode &n2; )
{
	if( n1.val != n2.val )
		return n1.val > n2.val;
	else
		return (unsigned)n1.obj < (unsigned)n2.obj;
}

@implementation ChemicalBurnOrderedQueue

- init
{
	if( ( self = [super init] ) )
	{
		mCount = 0;
		mCapacity = 100;
		mObjs = (struct CBOQNode *)malloc( mCapacity * sizeof( *mObjs ) );
	}
	return self;
}

- (void)dealloc
{
	free( mObjs );
	
	[super dealloc];
}

#pragma mark -

- (void)buildheap
{
	std::make_heap( mObjs, mObjs + mCount, NodeLessThan );
	mHeapified = YES;
}

#pragma mark -

- (unsigned)count
{
	return mCount;
}

- (void)addObject: (id)obj value: (unsigned)val
{
	mCount++;
	if( mCount > mCapacity )
	{
		mCapacity *= 2;
		mObjs = (struct CBOQNode *)realloc( mObjs, mCapacity * sizeof( *mObjs ) );
	}
	
	mObjs[mCount - 1].obj = obj;
	mObjs[mCount - 1].val = val;
	
	if( mHeapified )
		std::push_heap( mObjs, mObjs + mCount, NodeLessThan );
}

- (id)pop
{
	if( !mHeapified )
	{
		[self buildheap];
	}
	
	std::pop_heap( mObjs, mObjs + mCount, NodeLessThan );
	mCount--;
	return mObjs[mCount].obj;
}

- (NSString *)description
{
	NSMutableString *str = [NSMutableString string];
	
	[str appendString: @"ChemicalBurnOrderedQueue = (n"];
	unsigned i;
	for( i = 0; i < mCount; i++ )
		[str appendFormat: @"t%@ = %un", mObjs[i].obj, mObjs[i].val];
	[str appendString: @")n"];
	
	return str;
}

@end

And so there you have it. It's delightfully simple with STL doing the heavy lifting, and it sped ChemicalBurn up by around a factor of two with no other changes. Not bad for something this simple!

Did you enjoy this article? I'm selling a whole book full of them. It's available for iBooks and Kindle, plus a direct download in PDF and ePub format. It's also available in paper for the old-fashioned. Click here for more information.

Comments:

Ahruman at 2006-07-15 09:25:00:
There’s no NSPriorityQueue, no… but there is a CFBinaryHeap. ;-)

mikeash at 2006-07-15 15:34:00:
Good ol’ CoreFoundation, I missed that one. I’m still happy with my STL wrapper because it gives me warm performance fuzzies, and because with CF I would have to do some extra memory management due to wanting to store each node next to its cost in the queue.

Scott A at 2007-01-03 19:11:00:
This was great, I was using the sortUsingSelector on my hypothesis generation code for, I had stacks of hypothesis around 10000 each and it was taking forever but the (log n) totally kicks ass! I was wondering why my code was taking forever to run, I assumed that the sortUsingSelector might be a priority queue but I guess not quite haha… Anyways, thanks for this tidbit, I also abhor C++, due to my lack of understanding it’s memory management. Anyways, I was able to adapt the code a little bit since my objects already had their values stored within them and along with some retain/release messages when adding and popping.

mikeash at 2007-01-04 05:27:00:
Discovering why your app is slow is best done with Shark. A bit of time with that would have told you for sure that the sorting was taking up all of your time. But anyway, you managed to figure it out all on your own so it worked out, Shark just makes the job a lot easier. I’m glad you found the code helpful


Comments RSS feed for this page

Add your thoughts, post a comment:

Spam and off-topic posts will be deleted without notice. Culprits may be publicly humiliated at my sole discretion.

Name:
Web site:
Comment:
Formatting: <i> <b> <blockquote> <code>. URLs are automatically hyperlinked.
Hosted at DigitalOcean.