Friday, April 11, 2014

melonJS should be *All About Speed* Part 2

If you haven't already read Part 1, head over to that article for some important background information before continuing below.

Part 1 : http://blog.kodewerx.org/2014/03/melonjs-should-be-all-about-speed.html

Deep Copy

In version 0.9.11, we quietly rolled out a little feature that allows including complex objects in class descriptors for the inheritance mechanism we have been using (John Resig's Simple Inheritance). This allows, for example, creating classes with properties that instantiate other classes, or include arrays or dictionaries. It works by modifying Object.extend to do a deep copy on all of the non-function properties in the descriptor. This feature came about by ticket #307. You'll find some discussion in the ticket about why it doesn't work without deep copy, and some of the ugly prototype hacks we had to use to get it working.

Once the deep copy was all well and good, it came right back to bite us! That isn't surprising, to say the least. But it has caused one bug report so far, due to cyclic references and object pooling in #443. (Pooling is a method of reusing objects by resetting their internal state, which we will cover momentarily.)

Deep copy is unfortunately very slow. It's the process of iterating each property and determining the data type, then performing a shallow copy for simple objects like numbers and strings, or another deep copy for complex objects like arrays and dictionaries. Because the complex objects are reference types, they may create circular references, the simplest example being object A references object B, and B has a reference back to A. These object cycles are hard to deep copy, because you need to protect against copying the same object more than once. If that protection is missing, you quickly enter an infinite loop or stack depth overflow with recursion.

Even worse, this deep copy needs to be done at object instantiation time, so it will be dramatically slow to use the new keyword on any of your classes. Mix that with large classes, and your game will be in a lot of trouble!

That's why I decided not to include deep copy in Jay Inheritance. In fact, I took it even one step further and specifically made all properties immutable when added to a class. So if you define integers using the class descriptors, you'll find that you are not allowed to change the values in those properties. This should get the idea across that class descriptors are for methods only. No exceptions. And all in the name of speed.

Object Pooling

Deep copy was added as part of the object pooling revamp in 0.9.11. The idea was to simplify child object creation, by allowing child objects to be defined in the class descriptor. All children would be copied into the new object automatically as part of the Class constructor. And a bit of background on this decision: The pooling mechanism has to call the constructor to reconfigure objects when reusing them. And you don't want the constructor to create new child objects when the children already exist! That would defeat the purpose of pooling.

But now we know that was not the right way to fix child object creation with object pooling. A better approach is to embrace separation of responsibilities, allowing each part of the pooling mechanism to be responsible for one thing and one thing only. In the case of child object creation, that responsibility relies with the constructor, not the class descriptor.

We've supported pooling for quite a long time. But it has been broken, to be honest. The reason I say "broken" is due to the way the object life cycle works in melonJS. There's the init method which is the "user" constructor, and an onResetEvent method which is for resetting internal state of the object, and finally there is also a destroy method which can be used as a destructor.

  • init : Constructor, called when the object is created with new.
  • destroy : Destructor, called when the object is deactivated.
  • onResetEvent : Reset internal state, called when the object is reactivated.

Unfortunately, these methods are poorly defined within the object life cycle. For example, destroy is not called when the object is ready for garbage collection! Instead, it is called when the object is deactivated; when it is placed into the pool for later reuse. This means destroy cannot safely be used as a destructor unless onResetEvent also does constructor work, like creating child objects and event listeners. This is broken by definition; only the constructor should do constructor work.

To complicate matters, only a few classes have an onDestroyEvent callback that is called by the default destroy method. It's treated as a user-defined destructor, of sorts. But again, it is only called during object deactivation, and only very rarely used.

To fix all of these issues, we need to define the object life cycle concretely. A clear separation between construction and activation, and between deactivation and destruction is necessary to make pooling work effectively. To that end, here is my proposal for the life cycle methods, and when they are called:

  • init : Constructor, called when the object is created with new.
  • destroy : Destructor, called when the object is ready for garbage collection.
  • onResetEvent : Reset internal state, called when the object is activated/reactivated.
  • onDestroyEvent : Disable object, called when the object is deactivated.

For clarity, "deactivation" means the object is removed from the scene graph, and placed into the pool for later reuse. This is the signal to your object that it should remove any event listeners. Likewise, "activation" means placing the object into the scene graph ("reactivation" is when an object is reused from the pool). This is a signal to the object that it should reset its internal state, the internal state of its child objects, and adding any event listeners.

The constructor still needs to define all of the object's properties, and set values on them. This also means creating new child objects and setting their default internal state.

Finally, the destructor will make sure to remove any kind of "global state" changes that it has made, like event listeners, loaded resources, timers, tweens, etc.

The life cycle of an object without pooling then looks like this:

  1. init
  2. onResetEvent
  3. onDestroyEvent
  4. destroy

And as you might imagine, the life cycle of an object in the pool might look more like this:

  1. init
  2. onResetEvent
  3. onDestroyEvent
  4. onResetEvent
  5. onDestroyEvent
  6. ...

Without ever calling destroy. It will just continually be deactivated and reactivated as needed.

This API can make object pooling faster by being very strict about where in the object life cycle child objects can be created. For example, a shape object needs a vector for positioning. As long as this vector is only created in init, there will be no garbage collection thrashing when the shape object is pooled. Worst case, the position vector only gets reset (x and y properties updated) each time the object is reactivated with onResetEvent.

One final note here is that I want to establish these method names as the de facto object lifetime methods within the entire game engine. Not just for objects which get added to the scene graph, but for everything; even me.ScreenObject has had an onResetEvent callback implemented forever. It's slightly different though, called just after the registered state has been switched to. And onDestroyEvent is called when the state is switched away. But still very fitting.

Resetting Object Internal State

Now would be a good time to also touch on how I expect the object internal state to be set initially in the constructor. The answer is simply "don't care!" I cannot recommend having init call onResetEvent, due to inheritance rules; It would be a bad idea because both methods must call the overridden method on the super class. You would then have onResetEvent getting called multiple times at constructor-time! That would be slow and dumb. The right way to set initial state is to do so in the constructor only if you have to. Otherwise do all of the configuration when the object is added to the scene (handled by onResetEvent).

Here's some example code to help illustrate the concept:

var x = Math.random() * me.video.getWidth();
var y = Math.random() * me.video.getHeight();
var z = 9;
var particle = me.pool.pull("Particle", x, y, { "image" : "flame" });
me.game.world.addChild(particle, z);

This code will fetch an object from the pool that was registered with the class name "Particle", and pass some constructor/reset parameters. In the case that the "Particle" pool is empty, a new object will be instantiated, and the parameters are passed straight to the constructor. In the case that a "Particle" object is reused from the pool, it's constructor will not be called. Finally, the particle is added to the scene graph, and its z-index is set properly.

And this is where we need to make some big decisions! The pooling mechanism today actually does call the constructor in the latter case, which is very bad because the constructor should never have to worry about whether a child object already exists... In my mind, the child objects will never exist when the constructor is called, so it is only responsible for instantiating the children.

I would like this reuse path to rely on onResetEvent being called by me.game.world.addChild(), which will pass along the "object state" configuration parameters, probably even removing these parameters from the constructor entirely. In other words, the example code needs to be changed to this:

var x = Math.random() * me.video.getWidth();
var y = Math.random() * me.video.getHeight();
var z = 9;
var particle = me.pool.pull("Particle");
me.game.world.addChild(particle, x, y, z, { "image" : "flame" });

You will also notice the z parameter when adding the object to the scene graph. This has always been there! And it feels quite nice to finally put all of the coordinates together in the same place. The point to take away from this is that creating the object is not enough to actually use it, so why configure its internal state at constructor time? Especially if the constructor may not even be called because the object is just getting reused!

Simplified: create an unconfigured object, add it to the scene with configuration. The same pattern works equally well without pooling, just replace the me.pool.pull() call with the new keyword:

var x = Math.random() * me.video.getWidth();
var y = Math.random() * me.video.getHeight();
var z = 9;
var particle = new Particle();
me.game.world.addChild(particle, x, y, z, { "image" : "flame" });

Configuring Objects Without the Scene Graph

This is another good point to cover before I wrap up pooling changes! There are some objects which can be reused that never get added directly to the scene graph, or rather they discretely add themselves to the scene graph without the user's knowledge. me.Tween comes to mind immediately! This class uses the scene graph to ensure it updates object properties at the right time, and it adds itself to the scene graph when its start method is called. For this specific object though, I think it will be enough to reset internal state in onDestroyEvent, when it is removed from the scene. That will set it up for reuse later, without an extra reset step anywhere else.

For other objects like me.Color and me.Vector2d, my first thought is making the configuration step explicit, by calling onResetEvent directly. But that seems kind of silly, especially for people used to passing configuration parameters to the constructor in classical Object-Oriented Programming. But maybe it really is that easy? If you want to use pooling, call the object's onResetEvent to configure the object after it is retrieved from the pool. If you don't need pooling, pass configuration to the constructor!

// Object without pooling
var v1 = new me.Vector2d(10, 50);

// Object with pooling
var v2 = me.pool.pull("me.Vector2d").onResetEvent(10, 50);

These kinds of classes need to duplicate configuration code, because as mentioned earlier it's not a good idea to call onResetEvent from the constructor. Hopefully these classes will all be simple enough that the possibility of double-configuration (constructor directly followed by onResetEvent) will not be a large burden. Though we can be smart about it by counting arguments passed to the constructor, if necessary.

Conclusion

With that, we should be on our way to a very streamlined, GC-friendly game engine! Next time I'll talk about optimal array management; speeding up node addition/removal in the scene graph and object pool.

No comments: