NSArray vs. CCArray

In next release of cocos2d, I am planning to remove CCArray, and replacing it with NSArray ( or NSMutableArray actually ), but for analogy, and since CCArray should actually be CCMutableArray, I will just call it NSArray in this article.

There has been a lot of controversy about the performance of NSArray, and that it was slow. “Use CCArray, my grandma always told me“, seems to be consensus. It even lies so deep in the community, that some told me to expect a performance drop, if switching to NSArray. Nothing could be further from the truth.

I will not turn this into a “how to setup a test”, but unlike others – and I will mention no names – let me just try to just flesh out the basics of how to test this.

First, I have created a load function, only making one call to a function, returning a random integer, inside the range of the array.count, as I need that value later, for random access to the arrays.

for ( int i = 0; i < array.count; i++ ) {

    int RandomPosition = [ self returnRandomIndex:array ];

    // test function goes here

}

The test is performed on arrays with approximately 1000 objects. This is somewhat higher than what cocos2d will normally work on. Most arrays will be much smaller, but there seems to be little difference, unless you do linear large array searches, which I will not cover, as it simply is bad design. The loops are repeated, with each time sampled. When the spread of time samples drops below 1%, the test is stopped. Usually after a few seconds. As the basic loop time is known, the actual time spend in the test function, can be calculated accurately.

Every number is then put in relation to this load, so the milage will not vary, depending on your device. This will be a normalised value. If a test has a load of 1.0, it will take the same time to execute as the above load. Hold it up against how much else you do in your update loops, and do the math yourself. There could be fluctuations for older devices, sporting a much different hardware layout, but my guess is, that the result will be consistent for anything running iOS5 or better. For those who wants to know, the load loops ticks in at around 250 nS / loop, on an iPad3, running iOS6. The arc4random call in returnRandomIndex, alone takes 200 nS. For now – this very light load – will be our 100% load reference. For higher and more realistic loads … be patient, I will address it later.

Every number I present, is then rounded to 2-5 % accuracy, as even this test setup probably can not guarantee more. So I will not be writing “It took 138.1 mS”, as this is what we in danish call “talknepperi” ( No, Google has nu clue to what that is, but I bet you have an educated guess ). I will be writing, “It took 140 mS”

Before I get to the raisin in the hotdog-end, let me talk a bit about how cocos2d uses array. The fantastic four are.

1) Forward iteration

2) Backward iteration

3) Appending objects

4) Removing objects at a specific index

There will of course be exceptions from this, but this is basically what arrays will do in cocos2d. I have not made estimates as to the balance of this, but it is clear, that the number of times an object is iterated, compared to how many times objects are added and removed, easily could be a factor 100, 1000, or much higher.

As for the timing results.

1)

For forward iteration, both NSArray and CCArray has a load overhead of  less than 0.1 when switching from an integer loop – as in the load – to fast iteration. Basically this means, that all what matters in loops, is what is done inside the loop. But we all knew that.

In this case, it means that fast iterations was timed at 22 nS for NSArray, and 24 nS for CCArray, compared to the 250 nS of the loop.

2)

For backwards iteration, NSArray spends 2.8 load, and CCArray 2.5, meaning that CCArray is around 10% faster on backwards iteration.

This equals the functionality of getting an object from a random index. I will come back to that.

3)

For appending objects, NSArray spends 1.8 load, and CCArray really puts the foot down, and spends only 1.3 load.

Before we continue to 4, judging from these answers, you would say that CCArray is the way to go, and the numbers certainly are against NSArray. However, in cocos2d, any object added, will at some point be removed. So …

4)

For removing an object at an indexed position, NSArray spends 31 loads, while CCArray spends a whopping 150+ loads.

And yes, the loads are comparable, so the 0.5 load you earned when adding, you lost 250 fold when removing.

The bottom line is, that CCArray will be ~0.5 times an arc4random faster, for every time you add an object, but only if you plan to let your arrays grow forever. The fact that CCArray is slightly faster to backwards iterate is irrelevant, because the only reason you would ever want to backwards iterate, if is you want to remove on the fly.

I hope this will help bust the myth.

.

.

About arrays in general, Cocos2d will approach this in 3 ways.

1) Arrays which need fastest possible iteration, and little need for object removal

Forward iteration

2) Arrays which need fastest possible iteration, and often needs for object removal

Backwards iteration with on the fly deletion

3) Arrays which need fastest possible iteration, and fast random access

Double linked list with CCArray and CCDictionary

.

.

.

.

Ohhh … I forgot about the heavy load.

If you have any load, just marginally more complex than what I used above, you can divide the importance of using XXArray, with the magnitude of the complexity of your load. Meaning, that at the end of the day, what kind of array you use, is completely and utterly irrelevant.

The reason I remove CCArray, is not because cocos2d will become faster, because that part will not be measurable. I only remove it to make the cocos2d codebase cleaner and easier to access.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: