CCArray: Performance and usability

cocos2d for iPhone » Programming » cocos2d support (graphics engine)

CCArray: Performance and usability

(43 posts) (14 voices)

Started 1 year ago by manucorporat
Latest reply from cocos

Tags:

12 Next »

manucorporat
Member
I have developed a great class, and I have implemented it in cocos2d.

"CCArray" is like "NSArray" but it's much faster. (based in ccArray)

Some example using CCArray versus NSArray:

Init:
```
CCArray *array = [CCArray arrayWithCapacity:30];

for (int i = 0; i<30; i++){
[array addObject:[NSNumber numberWithInt:435]]; //Same that NSArray
}
```
1. - Very very faster. (This way should be used in the cocos2d kernel)
```
ccArray *arrayData = [array data];
for(int i = 0; i< arrayData->num; i++){
id object = arrayData->arr[i];
//Here your code
}
```
2. - The usability code (like NSArray):
```
for(id object in array){ //CCArray is conforms to NSFastEnumerator protocol
//Here your code
}
```
And the better is that you can replace all NSArray in cocos2d and it works sucessfully.

Edit: I am going to publish the code very soon.
Posted 1 year ago #
jd
Member

CCArray is much faster than NSArray? What percentage faster are you getting? Do you have performance test cases and results? That would be great.

Posted 1 year ago #
manucorporat
Member
Take a look at this: http://memo.tv/nsarray_vs_c_array_performance_comparison

I haven't implemented CCArray completly in cocos2d, because I must replace
```
for(id object in array)
```
with:
```
ccArray *arrayData = [array data];
for(int i = 0; i< arrayData->num; i++)
```
to get the maximum performance.
Posted 1 year ago #
jd
Member

I realize c array is faster than NSArray. I thought you created a class that is faster than NSArray, but not as fast as c array.

Posted 1 year ago #
riq
Key Master

@manucorporat:
It is possible to implement the fast enumeration protocol ?
If so, It would be awesome!!

Posted 1 year ago #

manucorporat
Member

@riq:
Yeah, You can create a custom array class with NSFastEnumerator protocol :)

This is the draw function in CCSpriteSheet optimized with the new array class:

#pragma mark CCSpriteSheet - draw
-(void) draw
{
	if( textureAtlas_.totalQuads == 0 )
		return;

	// Optimization: Fast Dispatch
	typedef BOOL (*DIRTY_IMP)(id, SEL);
	typedef BOOL (*UPDATE_IMP)(id, SEL);
	SEL selDirty = @selector(dirty);
	SEL selUpdate = @selector(updateTransform);
	DIRTY_IMP dirtyMethod = nil;
	UPDATE_IMP updateMethod = nil;

	ccArray *array = descendants_->data;
	CCSprite *child = array->arr[0];
	dirtyMethod = (DIRTY_IMP) [child methodForSelector:selDirty];
	updateMethod = (UPDATE_IMP) [child methodForSelector:selUpdate];

	for(int i = 0; i<array->num; i++)
	{
		child = array->arr[i];

		// fast dispatch
		if( dirtyMethod(child, selDirty) )
			updateMethod(child, selUpdate);

#if CC_SPRITESHEET_DEBUG_DRAW
		CGRect rect = [child boundingBox]; //Issue #528
		CGPoint vertices[4]={
			ccp(rect.origin.x,rect.origin.y),
			ccp(rect.origin.x+rect.size.width,rect.origin.y),
			ccp(rect.origin.x+rect.size.width,rect.origin.y+rect.size.height),
			ccp(rect.origin.x,rect.origin.y+rect.size.height),
		};
		ccDrawPoly(vertices, 4, YES);
#endif // CC_SPRITESHEET_DEBUG_DRAW
	}

	// Default GL states: GL_TEXTURE_2D, GL_VERTEX_ARRAY, GL_COLOR_ARRAY, GL_TEXTURE_COORD_ARRAY
	// Needed states: GL_TEXTURE_2D, GL_VERTEX_ARRAY, GL_COLOR_ARRAY, GL_TEXTURE_COORD_ARRAY
	// Unneeded states: -

	BOOL newBlend = NO;
	if( blendFunc_.src != CC_BLEND_SRC || blendFunc_.dst != CC_BLEND_DST ) {
		newBlend = YES;
		glBlendFunc( blendFunc_.src, blendFunc_.dst );
	}

	[textureAtlas_ drawQuads];
	if( newBlend )
		glBlendFunc(CC_BLEND_SRC, CC_BLEND_DST);
}

but the current code works too.

Posted 1 year ago #

riq
Key Master

@manucorporat:
cool! Hey, when you have it ready, could you attach the patch? or better yet, could you fork cocos2d (git / github), and send me a "pull" request ? Thanks!

Posted 1 year ago #
saim80
Member

I hope it can support NSPredicate filtering... ? even better with NSSortDescriptor... just my little hope...

Posted 1 year ago #

manucorporat
Member

@saim80 Do you are using NSPredicate and NSSortDescription with the children array?

Here some speed tests. (200 elements)
Test A (NSArray) : 0.000445

for(int w = 0; w<100; w++){
		for(id object in arrayNS){
			//Do something
		}
	}

Test B (CCArray) : 0.000401

for(int w = 0; w<100; w++){
		for(id object in array){ //CCArray
			//Do something
		}
	}

Test C (CCArray) : 0.000120

ccArray *arrayData = array->data;
id object;
int nu = arrayData->num;
for(int w = 0; w<100; w++){
		for(i=0; i<nu; i++){
			object = arrayData->arr[i];
			//Do something
		}
	}

The test C is x3.7 faster than the Test A

Posted 1 year ago #

manucorporat
Member

Here, you can see how CCArray works:
http://github.com/manucorporat/cocos2d-iphone

Posted 1 year ago #
riq
Key Master
Nice work Manu!! Thanks!!
I've merged your changes in the "develop" branch.

I've added the MIT license to your files. Are you OK with it ?
http://github.com/cocos2d/cocos2d-iphone/blob/develop/cocos2d/CCArray.h
http://github.com/cocos2d/cocos2d-iphone/blob/develop/cocos2d/CCArray.m

Also, I've noticed that you have cloned the "master" branch, and not the "develop" branch.
The "develop" branch is that one that contains the "unstable" stuff.

So, if you want to merge the "develop" branch in your repo, you have to do this:
```
$ git pull git://github.com/cocos2d/cocos2d-iphone.git develop
```
Regarding CCArray
a) I think that we should make some "real-scenario" performance tests. I've noticed that CCArray uses a c-array internally.
Probably the c-array is the best alternative... But if a game is constantly adding/removing nodes perhaps a list would suit it better.
For example, I think that a c-array is the right choice for almost all the nodes. But perhaps a list will perform better in a CCSpritesheet. This is just a thought and I'm not quite sure about it.

If this is the case, we could solve it using an strategy pattern: http://en.wikipedia.org/wiki/Strategy_pattern

b) The name conflicts with ccArray. In OS X 'Hello.m' is the same as 'hello.m'. So to avoid possible conflicts, I would like to either rename the files CCArray.[mh], or ccArray.[hm]. I don't have any suggestions for the moment, but if you have, please, let me know.

c) When b) is done, I would like to move the CCArray.[mh] files into the Support directory, since the data structure files are there

As always, nice work!
Posted 1 year ago #
riq
Key Master

regarding b), perhaps we could rename Support/ccArray.[hm] to Support/cArray.[hm] or Support/ccCArray.[mh]

Posted 1 year ago #
CJ
Moderator

nice work manu!

@riq I agree that it is probably important to factor in add/remove performance for at least spritesheet.

Posted 1 year ago #
manucorporat
Member

@riq no problem, add the MIT license.

I don't understand the "lists" very well, What are the advantages of lists?

I love looking for new techniques to increase performance.

Posted 1 year ago #
riq
Key Master

@manu: Thanks.

regarding list:
A list is another data structure ( http://en.wikipedia.org/wiki/List_of_data_structures#Lists )

Differences with an array:
+: cheaper to add/remove elements: 1 or 2 variable assignment vs. a mem-copy. O(1) vs. O(n)
-: iteration is a bit more expensive, but not too much expensive. In both cases both are O(n).
-: more expensive to obtain an object at a certain index: O(n) vs. O(1)

O() means the complexity of the operation: http://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities

Posted 1 year ago #
mobilebros
Moderator

Looking at the ccArray.h file... Am I correct in assuming that the memory footprint is only capable of getting larger and never smaller (unless destroying whole array)? Not sure if this is a considered issue or not.

If it is, realloc would be your friend.

Posted 1 year ago #
riq
Key Master

@mobilebros: yes, I think ccArray nerver gets smaller.

I started adding some performance tests.
So far I only added 2:
-> iterate using the Fast Enum API
-> iterate using the C array API

The C array API seems to be just a little bit faster than the Fast Enum API.

I'll add more during the week, and then I'll backport these test to v0.99.3 to compare both versions.

To try them:
-> download "develop" branch
-> edit cocos2d/ccConfig.h -> Enable CC_ENABLE_PROFILING
-> open tests/PerformanceTests/PerformanceTests.xcodeproj/

Posted 1 year ago #
riq
Key Master

Tests:

http://www.cocos2d-iphone.org/wiki/doku.php/perf_test:0_99_3
http://www.cocos2d-iphone.org/wiki/doku.php/perf_test:0_99_4

Iteration time seems to be more or less the same, at least with 2500 sprites...
However adding/removing sprites, to my surprise, is MUCH faster than in v0.99.3... (twice as fast)

So, as it is now, v0.99.4-pre performs faster than v0.99.3 in adding/removing sprites from an spritesheet (and probably from any other node too).

TODO:
Try using a list instead of a c-array in CCArray. I guess that the iteration time should be more or less the same, but the add/remove time would be MUCH faster.

Posted 1 year ago #
manucorporat
Member

@riq Then, Do you have planed replace the descendants_ array to a list ? the children array? or both?

Posted 1 year ago #
riq
Key Master

@manucorporat: Tomorrow I'll implement CCArray with a list just to test the performance.
If the iteration performance is about the same, and the add/remove is noticeable faster, I would use just one "version", the "list" version.
I'm still not sure if is better to implement the "strategy pattern" on CCArray or create a CCList.

Posted 1 year ago #
riq
Key Master

I made some changes:
Support/ccArray.h renamed to Support ccCArray.h
CCArray.[mh] moved to Support/

@manucorporat: I've fixed an important bug in CCArray#lastObject. If you are using it in your game, I suggest "pulling" the fixed version from the "develop" branch.

Posted 1 year ago #
manucorporat
Member

thanks @riq, I have just updated my code.
I think that the best solution would be to integrate a list in CCArray.
Because if you have planed replace all CCArrays to a "CCList", then, What would be the usefulness of the CCArrays?

I also think the iteration performance is very important.
For example:
I have 20 bullets, 50 enemies and 50FPS= 20x50x50= 50000 per second.
In this case a good performance reading arrays is very important.

Posted 1 year ago #
riq
Key Master

I think that there are places where a c-array is better than a list, so I'm still not sure how to approach this issue.

I started implementing CCList, but then SDK4.0 came out, so I "paused" the CCList feature in order to support the new higher res.

As CCArray is faster than NSArray, I'm not in a hurry to finish the CCList implementation.

Posted 1 year ago #
CJ
Moderator

I'd like to see CCList in Spritesheet :) Maybe if I get some free time I'll take a crack at it.

Posted 1 year ago #
riq
Key Master

@CJ: that would be cool. v0.99.3 already includes a list implementation with useful macros: Support/utlist.h

Posted 1 year ago #
Karl
Member

Traversal of a CCArray vs NSArray won't be much different since both use a C array for their Fast Enum implementation.

Posted 1 year ago #

manucorporat
Member

I have programmed a new method to read a CCArray easily.

Current way:

CCArray *array = ...

if(array){ //Check if the pointer is nil
      ccArray *data = array->data;
      CCNode *node;
      for(int i = 0; i<data->num; i++){
             node = data->arr[i];
             [node doSomething];
      }
}

New code:

CCArray *array = ...
CCNode *node;
CCARRAY_FOREACH(array, node){
[node doSomething],
}

Some implementation in cocos2d:

-(CCNode*) getChildByTag:(int) aTag
{
	NSAssert( aTag != kCCNodeTagInvalid, @"Invalid tag");

        CCNode *node;
        CCARRAY_FOREACH(children_, node){
                if(node.tag == aTag)
			return node;
	}
	// not found
	return nil;
}

This is the magic code

// Fast iteration, easy integration
#define CCARRAY_FOREACH2(object, array)																																										\
for(ccArrayForeachData _d=(array && (object=array->data->arr[0])) ? (ccArrayForeachData){0,array->data->num,array->data->arr}: (ccArrayForeachData){0,0,nil}; _d.i<_d.num ; _d.i++, object=_d.arr[_d.i])	\

Posted 1 year ago #

riq
Key Master

nice :) could you commit it in your repo and send me a pull request ? thanks!

Posted 1 year ago #
manucorporat
Member
@riq
Ok riq, but I don't know what name choose

Reading a ccArray -> CCARRAYDATA_FOREACH(array, object)
Reading a CCArray -> CCARRAY_FOREACH(array, object)

¿?

Edited: ccFor or ccForeach ->could be so cool
```
CCNode *child;
ccFor(child, children_)
{

}
```
What do you think?
Posted 1 year ago #
riq
Key Master
By convention, all macros should be in upper case, so I would call it:
```
CCARRAY_FOREACH(array, object)
{
}
```
Posted 1 year ago #

RSS feed for this topic

12 Next »

Reply »

You must log in to post.