Have a look at the following code, and then answer these questions before reading on:
- Which function will run faster?
- What will be the framerate for each function when run 100 times per frame on an iPhone 3G?
- Will wrapping the 100 calls to function1 in an NSAutoreleasePool show any difference?
[cc lang=”ObjC” height=”465″]
-(void) function1
{
CGPoint pos = [self position];
id x = [NSNumber numberWithFloat:pos.x];
id y = [NSNumber numberWithFloat:pos.y];
id objects = [NSArray arrayWithObjects:x, y, nil];
id keys = [NSArray arrayWithObjects:@”x”, @”y”, nil];
id dict = [NSDictionary dictionaryWithObjects:objects forKeys:keys];
dict; // avoid compiler warning, is a noop
}
-(void) function2
{
CGPoint pos = [self position];
id x = [[NSNumber alloc] initWithFloat:pos.x];
id y = [[NSNumber alloc] initWithFloat:pos.y];
id objects = [[NSArray alloc] initWithObjects:x, y, nil];
id keys = [[NSArray alloc] initWithObjects:@”x”, @”y”, nil];
id dict = [[NSDictionary alloc] initWithObjects:objects forKeys:keys];
[x release];
[y release];
[objects release];
[keys release];
[dict release];
}
[/cc]
The Answers
- Which function will run faster? Answer: function1
- What will be the framerate for each function when run 100 times per frame on an iPhone 3G? Answer: 27 fps for function1 and 24 fps for function2.
- Will wrapping the 100 calls to function1 in an NSAutoreleasePool show any difference? Answer: no, but memory of temporary objects is released immediately.
Needless to say, on an iPod (4th Generation) and an iPad these tests all run at 60 fps and give no indication whatsoever that the performance on an iPhone 3G would suffer this much (and neither does the Simulator, of course). All the more reason to test early and often on older devices.
To autorelease or not?
Common wisdom may tell you that alloc/release is faster than autorelease. Even Apple recommends avoiding autorelease, right?
Not quite, because this is often misunderstood: Apple recommends to avoid autorelease but only for functions which create a lot of temporary objects and because of the constrained memory - not because it’s slow or even dangerous - autorelease is not dangerous.
Since memory is so constrained on 1st and 2nd generation iOS devices, it’s best to release that memory as soon as possible and don’t leave it allocated for longer than necessary. To achieve this, you can choose to do two things in this case: use alloc/release or enclose the loop in an NSAutoreleasePool. The latter option is preferred since it will release the memory right away, and not some time later. And autorelease is generally preferable because you will never, ever forget to send a release message to an object - which means it’ll be leaked and forever use up memory.
You can write well-performing, even better-performing code by using autorelease and using NSAutoreleasePool around tight loops creating many temporary autorelease objects.
Innocent looking code kills framerate
Did you expect that creating 100 rather simple NSDictionary instances each frame would drag the framerate down to around 24-27 fps? Me neither. I knew the code wasn’t going to be blazing fast, but I never expected it to have such an impact. However, it can be optimized somewhat since I’m unnecessarily creating two NSArray instances to hold the keys and values respectively before using them to create the NSDictionary. In fact we can get rid of them by using dictionaryWithObjectsAndKeys and doing this in a single step:
[cc lang=”ObjC”]
-(void) function1Optimized
{
CGPoint pos = [self position];
id x = [NSNumber numberWithFloat:pos.x];
id y = [NSNumber numberWithFloat:pos.y];
id dict = [NSDictionary dictionaryWithObjectsAndKeys:x, @”x”, y, @”y”, nil];
dict; // avoid compiler warning, is a noop
}
[/cc]
Sometimes it helps to look around what other ways there are to run the same code. In terms of performance this is an order of a magnitude faster and now clocks in at 42 fps. Still not good enough for realtime rendering obviously but an improvement of over 50% by cutting two NSArray allocations is a very simple and effective optimization.
Just as a general guideline, when I get rid of the two NSNumber instances and simply pass empty strings for x and y the framerate went back up to 60 fps. Of course that’s over-optimizing to the point where the code doesn’t work anymore. It just goes to show how expensive the creation of NSDictionary and NSArray are, as is wrapping simple types in NSNumber or NSValue objects.
If you can avoid allocation and temporary objects, avoid it. If you can’t, at least avoid creating temporary objects every frame. Re-use objects as much as possible. Unfortunately, that’s not an option for NSNumber objects since you can’t change the value of a NSNumber instance.
My Cocos2D Xcode project is now on Github. Open-source, free, properly MIT Licensed, includes the rootViewController and supports Cocos2D v0.99.5 rc0.
I’m also working on (with) a greatly enhanced version of the Xcode project. It integrates wax (Lua) and a Game Object Component System that i termed “gocos”. Also comes with a lot more useful convenience classes.
But the big idea is to actually upload (or link within github, if I can figure out if and how that works) all dependent projects into one repository, so that you can download everything at once and it works out of the box. Currently there are 3 projects referenced by cocos2d-project: gocos (let’s call it a library of convenience and gameplay code for Cocos2D), wax (Lua support) and obviously cocos2d-iphone. So everything that’s needed is going to be bundled in one big package, which voids all of the version incompatibility issues.
You can still experiment with different versions of these libraries but in that case I think you know what you’re doing and that issues are to be expected. But being a github repository, you can of course clone and commit changes.
Appetizer
Here’s what I’ve done with Lua. I’m currently using it only as a better plist replacement for settings. It’s better than plist because you can comment on each item, you can sort them easily, you can run functions and algorithms to generate values or load additional data, and in general it’s a lot easier to work with than the plist editor. Here’s a reduced config.lua that is loaded at runtime into a hierarchy of NSDictionary objects:
[cc lang=”lua”]
local config =
{
AccelerometerControls =
{
UpdatesPerSecond = 60, — 60 Hz
Responsiveness = 0.997,
SensitivityX = -2,
SensitivityY = 2,
MaxVelocity = 100,
},
}
return config
[/cc]
And this line of code loads these values and assigns them to the correspondingly named properties of the target class:
[cc lang=”objc”]
[Config loadPropertiesFromKeyPath:@”AccelerometerControls” target:self];
[/cc]
That’s all you need to do to transfer the values from config.lua into a class instance. Huge timesaver! The only drawback is that it currently can’t differentiate between float, int and bool (due to NSNumber), so it currently only supports float properties.
When TechnoKinetics mentioned on Twitter he was annoyed with cocos2d, I wanted to know why. It turns out it was the change away from NSMutableArray to CCArray in cocos2d which required him to update his codebase after he upgraded to the latest cocos2d version. He called it a “seemingly insignificant” change. At the time CCArray was introduced I didn’t think much about it but now I wondered, how significant or insignificant is it?
As far as I looked, there were only vague results published and the cocos2d forum thread ends with Pearapps asking for a performance test, so I believe there are no CCArray performance test results available. The conversation also lead me to this NSArray vs. C-Array performance comparison. To my dismay, it is comparing apples with oranges, as the NSArray had to wrap and unwrap the floating point values into NSNumber objects, so the results are terribly skewed in favor of the C-Array. Since this article was referred to in the CCArray cocos2d forum thread, it made me skeptical about the initial performance tests putting ccArray (the C implementation which is wrapped by CCArray, mind the case) at 3.7 times faster, or just plain text “very very faster”. I’m an engineer and not a believer, such “much faster” statements always make me very skeptical (how much is “very”?). I thought I should put in some time to generate some actual numbers.
Test Setup
I decided to take parts of Mehmet Akten‘s array test code (eg. measuring the time), then use all available array types in a way that is most common to cocos2d: storing pointers. I wanted to do a little more real-world-ish test. Internally cocos2d uses CCArray to store the children of a node, which are pointers. Without the boxing & unboxing of NSNumber we can better compare the results of how the individual array types perform. So I derived my own testing project to figure out how fast read access is between a C-Array, CCArray, NSMutableArray and NSArray by looping over each element in the array, retrieving the element (a CCLabel) and changing its tag property, just to give the loop something to do. I’m wary of the compiler possibly over-optimizing the loop if it doesn’t do anything. I’m also wary of any caches (whichever the iOS devices may or may not have) affecting the test, so I made sure that the item count (50,000) was large enough to not fit into any caches.
Code that is measured for for loops:
|
1 2 3 4 5 |
for(int i=0; i<NumItems; i++) { CCNode* node = [c2Array objectAtIndex:i]; node.tag = i; } |
Using fast enumeration:
|
1 2 3 4 5 |
int i = 0; for (CCNode* node in nsMutArray) { node.tag = i++; } |
Using CCARRAY_FOREACH fast enumeration:
|
1 2 3 4 5 6 |
int i = 0; CCNode* node; CCARRAY_FOREACH(c2Array, node) { node.tag = i++; } |
Sequential Read Performance
The results: a mere 10% read access performance increase for CCArray compared to NSMutableArray when using a for loop (2nd and 3rd column from the right in the chart below). And a tiny, negligible improvement when using the CCARRAY_FOREACH keyword compared to NS(Mutable)Array’s fast enumerator for(CCNode* node in array) to iterate over the array. Both these results are in the same ballpark with the C-Array, and I was pleasantly surprised to see the CCArray and NS(Mutable)Array all perform basically the same as the C-Array when using fast enumeration, with CCArray just a tiny fraction faster - exactly the same performance as a pure C-Array.
The test did also reveal an interesting effect I hadn’t expected: the NSArray’s read access performance without fast enumeration is noticeably slower than NSMutableArray. It really shouldn’t be slower, but NSArray consistently performed around 70% slower than NSMutableArray when using a for loop. I have no explanation for this anomaly. And with fast enumeration both are exactly the same speed-wise.
The Y axis is in milliseconds:
These results indicate that you do not need to use a C-Array over NSMutableArray or CCArray when the array is fixed in size and only read from. If you’re only concerned about access speed, and you use the fast enumerator respectively CCARRAY_FOREACH, you can use CCArray, NSArray, NSMutableArray and a C-Array interchangeably. The performance difference is indeed insignificant. There’s a lot of other things you can do to improve your game’s performance before you should start considering which type of array to use. But for a fixed-size array, NSArray is definetely the worst choice.
Things change of course if you need to store primitive data types like float, int, double. In that case, the C-Array will win hands down against its competitors because it doesn’t need to wrap primitive data types in a NSNumber object. But in the other cases, when you store actual pointers, by all means use the convenience collections available to you and benefit from bounds checks and a better interface to set, retrieve and iterate over objects. In this read access test, CCArray only has an advantage if you’re using a regular for loop to iterate over the elements (see the last 3 columns in the chart above). But at most it’s just 10% faster than NSMutableArray, that’s still negligible, especially if you consider the time spent running whatever code within the loop.
Add, Insert & Remove Performance
I also wanted to find out how much of an improvement CCArray is over NSMutableArray for adding and removing objects. It causes the array to expand or shrink as the number of objects increase and decrease, which creates an additional and sometimes significant overhead. That’s where CCArray should shine. Here’s the test setup:
Add object to end of array:
|
1 2 3 4 |
for(int i=0; i<NumItems; i++) { [nsMutArray addObject:label]; } |
Insert object at first position (shifting the remaining part of the array back by 1):
|
1 2 3 4 |
for(int i=0; i<NumItems; i++) { [nsMutArray insertObject:label atIndex:0]; } |
Remove last object:
|
1 2 3 4 |
for(int i=0; i<NumItems; i++) { [nsMutArray removeObjectAtIndex:NumItems - i - 1]; } |
Remove object at index 0 (first position):
|
1 2 3 4 |
for(int i=0; i<NumItems; i++) { [nsMutArray removeObjectAtIndex:0]; } |
The initial finding was promising, the CCArray is 40% to 50% faster than NSMutableArray for the addObject and removeObjectAtIndex:last operations (meaning: to add or remove and item at the last position in the array) on my iPhone 3G. On the iPad as native application, the difference is even more significant with CCArray being 8 times faster than NSMutableArray for the addObject operation, and 2.2 times faster for the removeAtIndex:last operation. That’s great news!
But then came the shock when I tried insertObject:AtIndex:0 and removeObjectAtIndex:0 … I thought my iPhone had locked up and crashed, but alas CCArray is just dead slow in these cases! And by dead slow I mean: broken. Over 200 times slower, even on the iPad. Unless I made a grave mistake in my test (which I don’t see), it’s very likely a bug in the CCArray implementation. Or a design flaw. In any case, something isn’t right when it takes CCArray 53 seconds to insert or remove an object at the first index when NSMutableArray only needs 0.2 seconds to perform the same operations. If you rely on the removeAtIndex and insertAtIndex methods you should refrain from using CCArray until this problem is fixed. As far as I can tell, cocos2d rarely uses these methods internally so this issue shouldn’t have a measurable impact on cocos2d’s overall performance.
Update: @manucorporat has already fixed this CCArray performance issue (within minutes!!), it should be integrated in a new cocos2d build soon. I’ll update the performance test results soon.
Update #2: Apparently the fix was not all encompassing. It was faster on the iPad but just about 8 times, but still at least 13 times slower than NSMutableArray. On my iPhone 3G the results were worse and went down to a factor of 360. It’s being worked on. Stay tuned.
Note that this diagram is not to scale! If it were, you wouldn’t be able to make out the blue bars for NSMutableArray!
All tests were done on an iPhone 3G running iOS 4.1 with a release build of cocos2d v0.99.5 beta. The results for iPad were only glanced at to check for relative differences, see text above. All results are in milliseconds, averaged over several runs (3-5) with an iteration count of 50,000. The read speed tests were run individually, not in sequence, because running all read speed tests in sequence caused slightly different results depending on the order in which the tests were run. For example, the slower speed of NSArray was less pronounced if the tests ran in sequence.
Feel free to download my ArraySpeedTest.zip project and try to reproduce the results. Only run the tests on a device and in release builds to get comparable numbers. Let me know if you find flaws in the test setup. I’m also interested to hear if the relative speeds vary on other devices.
