What is the performance of childNodeWithName in SpriteKit?
In SpriteKit, the SKNode method childNodeWithName:
looks for the children of the receiver node for a node with a specific name. I know it.
But what about performance? I mean, is it known how this is implemented?
Possible answers to this question:
- It has O (n) computational complexity as it iterates over all children
- It has O (log n) computational complexity because it uses some indexed structure
Reson why I ask
If implemented with for a loop , then it has a complexity of O (n) (where n is the number of children of the current node). Then we should avoid calling at any critical point, for example, the update method GameScene. At least when there are many children.
source to share
After several hours of optimizing my iOS game, I find the runtime to childNodeWithName:
be linear, not logarithmic.
The situation I'm dealing with is this: There were 500 nodes in the scene and each node had a unique name (4 bytes UUID and I know this is not best practice). Every 100ms I called childNodeWithName
for each node to apply a server side update. Then, obviously, I saw an unexpected drop in fps, even though there was no update from the server (which means it only childNodeWithName
gets called and returns immediately).
So, I decided to replace childNodeWithName
with a customized Set<String>
one to check if the SKNode contains a node with a specific name. And it worked, the fps drop disappeared.
source to share
As a semi-responder, Apple strongly recommends that we cache the call results childNodeWithName
or enumerateChildNodesWithName
.
Cm:
WWDC 2014 - Session 608 - Best Practices for Making Sprite Kit Games, 16 Minute Mark
The implication is clear: no matter how fast the lookup table is, if you have objects that you reference frequently, then you should keep references to them. (Especially at 60 frames per second).
In terms of search mechanics, these prefab containers / clusters are highly optimized and use different algorithms depending on a number of factors. Therefore, we cannot assume that NSDictionary, NSArray, NSSet or their Swift variants actually work as hash tables or whatever. And, unless otherwise stated, certain O (*) characteristics cannot be assumed.
(Google for a fascinating analysis of the NS [Collection] runlevel details.)
eg. http://ciechanowski.me/blog/2014/03/05/exposing-nsmutablearray/
source to share