3

In SpriteKit the method childNodeWithName: of SKNode searches the children of the receiving node for a node with a specific name. I know that.

But what about performance? I mean, is it known how it is implemented?

Possible answers to this question are:

  1. It has computational complexity O(n) because it does iterate through all the children
  2. It has computational complexity O(log n) because it does use some indexed structure

Reson why I am asking

If it is implemented with a for loop, then it has complexity O(n) (where n is the number of children of the current node). Then we should avoid invoking it in some critical point like the update method of GameScene. At least when there are many children.

2
  • Why the down vote? I am simply asking about the performance of a method (e.g. O(n), O(log n), ...). Apr 27, 2015 at 19:07
  • Unless someone provides you with the answer and proof thereof (which I do not expect because who knows how Apple does most of their stuff), I would advise you to do some testing with n = {1000, 5000, 10000, 50000, etc.} children and see what you find. I'm curious too. Apr 28, 2015 at 11:54

2 Answers 2

3

After several hours on optimizing my iOS game, I believe the running time of childNodeWithName: is linear rather than logarithmic.

The situation that i am dealing with is: There were 500 nodes in the scene and each node had a unique name (4 bytes UUID and I know it is not the best practice). Every 100 msec I called childNodeWithName for each nodes to apply update from the server side. Then, obviously I observed unexpected fps drop even though there was no update from server (which means only childNodeWithName gets called and return immediately).

So I decided the replace the childNodeWithName with a customized Set<String> just to check the whether the SKNode contains a node with a certain name. And it worked, the fps drop disappeared.

2

By way of a semi-answer, Apple strongly advise that we cache the results of childNodeWithName or enumerateChildNodesWithName calls.

See:

WWDC 2014 - Session 608 - Best Practices for Building Sprite Kit Games, 16 minute mark

The implication is clear: no matter how fast the lookup table, if you have objects that you refer to frequently, then you should keep references to them. (Particularly at 60fps.)

As for the mechanics of the lookup, these collection containers/clusters are highly optimised, and use different algorithms depending on a number of factors. So we can't assume that NSDictionary, NSArray, NSSet or their Swift variants actually work as hash tables or whatever. And, unless otherwise marked, can't be assumed to have specific O(*) characteristics.

(Google for an exciting analysis of NS[Collection] low-level implementation details.)

e.g. http://ciechanowski.me/blog/2014/03/05/exposing-nsmutablearray/

1
  • Thank you for your answer and for the reference to the WWDC session. Jun 9, 2016 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.