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.

+3


source to share


2 answers


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.

+3


source


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/

+1


source







All Articles