The Object Pool is now open!

“Okay, so the Horseman has been learning Java and Android development… does this mean he won’t ever write about ActionScript again?”

Of course I will, dear reader. In my last entry about ActionScript, I mentioned that I believed that you could gain performance benefits in Box2DAS3 by using object pooling. I’ve been toying with the concept, and so far my idea seems sound.

The concept of an object pool is of benefit when you work in an environment where instantiation is an expensive process, and you’ll find yourself instantiating repeatedly, possibly ceaslessly for the life of the program. In other words, the dictionary definition of the Flash Player.

In examining the source code for the version of Box2D I’ve used for my site’s banner, just at a glance it appears that the most commonly instantiated object in the library is the humble b2Vec2. It is used everywhere, and is frequently instantiated in a one-off fashion to generate throw-away data. When using the default version of the library, my banner instantiates between 600 and 2400 b2vec2 objects every frame during the very first word drop. That is not a small number. Even worse, it grows with every new word on the screen. It doesn’t take very long to have 12000 instantiations every frame. Where do all these instances come from and are they a symptom of a bigger problem? What is the solution, if so?

You can hunt for every instance of new b2Vec2 in the source code and come up with some interesting results. For instance, take the definition for the ClipVertext object:

package Box2D.Collision{
 
 
import Box2D.Common.Math.*;
import Box2D.Collision.*;
 
 
public class ClipVertex
{
	public var v:b2Vec2 = new b2Vec2();
	public var id:b2ContactID = new b2ContactID();
 
};
 
 
}

Notice that any time you instantiate one of these, you create a new b2Vec2. So how often is a ClipVertex instantiated? Quite frequently, and all in one single class file! They are generated exclusively in b2Collision:

var incidentEdge:Array = [new ClipVertex(), new ClipVertex()];
var clipPoints1:Array = [new ClipVertex(), new ClipVertex()];
var clipPoints2:Array = [new ClipVertex(), new ClipVertex()];

Well that’s not so bad, right? I mean, that only appears in one function call: b2CollidePolygons. Well… b2Contact.b2CollidePolygons is called inside of b2PolygonContact.Evaluate, which is… well… here’s a stack trace:

	at Box2D.Dynamics.Contacts::b2PolygonContact/Evaluate()
	at Box2D.Dynamics.Contacts::b2Contact/Update()
	at Box2D.Dynamics::b2ContactManager/Collide()
	at Box2D.Dynamics::b2World/Step()

Hey, that’s a really familiar set of functions. They’re ones we looked at last time. How often were they being called, anyhow? Well, c.Update happens any time a collision persists between “awake” objects… as it turns out, that’s a lot. So what can we do here? One way to handle this is with an object pool for ClipVertex.

The basic idea behind a pool is that you perform several expensive instantiations in one process, taking a relatively small hit upfront, so that you can recycle a limited number of objects without re-instantiating. Bear in mind that maintaining the pool requires some processor overhead itself, and in the case of a very simple object (like b2Vec2) will not gain you a direct advantage in terms of processing performance, though in the Flash context fewer junk objects created mean fewer runs for the garbage collector, which is itself an expensive process.

So, what might our pool look like? Here is a very simple object pool for ClipVertex instances:

package Box2D.Pools {
	import Box2D.Collision.b2ContactID;
	import Box2D.Collision.ClipVertex;
	/**
	 * ...
	 * @author The Horseman @ http://www.scriptocalypse.com
	 */
	public class ClipVertexPool{
 
		public static var m_pool:Array = [];
		public static var m_poolLength:uint;
 
		public static function get poolLength():Number {
			return m_pool.length;
		}
 
 
		public static function Retrieve():ClipVertex {
 
 
 
			if (!m_pool.length) {
				for (var i:int = 0; i < 6 ; i++) {
					m_pool[m_pool.length] = new ClipVertex();
				}
			}
			m_poolLength = m_pool.length - 1;
			var result:ClipVertex = m_pool[int(m_poolLength)];
			m_pool.length = m_poolLength;
			result.v.x = result.v.y = 0.0;
			result.id = new b2ContactID();
			return result;
 
 
		}
 
		public static function Recycle(pClipVertex:ClipVertex):void {
			if(pClipVertex is ClipVertex){
				m_pool[m_pool.length] = pClipVertex;
			}
		}
 
		public static function RecycleMany(pClipVertices:Array):void {
			var cv:ClipVertex
			for (var i:int = 0, ilen:int = pClipVertices.length ; i < ilen ; i++) {
				cv = pClipVertices[int(i)] as ClipVertex;
				if (cv) m_pool[m_pool.length] = cv;
			}
		}
 
 
	}
 
}

Here’s what we’re doing:

When you want an instance of ClipVertex, you call ClipVertexPool.Retrieve(). If there are any spare instances in the pool, one will be sent back to you in an initialized state. Otherwise, we will instantiate six more objects, add them to the pool, and keep them for use later.

Now you replace all the calls to new ClipVertex with calls to ClipVertexPool.Retrieve(), and at the end of the function’s lifecycle remember to pass the instances back to ClipVertexPool.Recycle(). You will quickly notice a few things:

  1. Your Retrieve function only seems to ever have to instantiate one time. The first time it’s ever called.
  2. The number of b2Vec2 instantiations per frame has just dropped by several hundred.

There’s a one-to-one relationship between instantiations of ClipVertex and instantiations of b2Vec2, and as we’ve seen we eliminated hundreds of wasteful calls to new ClipVertex with a single code construct. It’s interesting to note that in fact for the purposes of the flaming banner the application truly only needs six instances of ClipVertex to exist for the entire lifetime of the program.

“But Mr. Horseman, why go to the trouble of implementing a pool for these six instances of ClipVertex? We could store them as static variables in b2PolygonContact and just re-initialize them there.”

Well that’s a valid point. Pooling ClipVertex is slightly (but only just slightly) academic, as you’ve surmised. Here’s a more meaty version of the object pool. Allow me to introduce to you the b2OBB object:

package Box2D.Collision{
 
import Box2D.Common.Math.*;
 
/// An oriented bounding box.
public class b2OBB
{
	public var R:b2Mat22;		///< the rotation matrix
	public var center:b2Vec2 = new b2Vec2();	///< the local centroid
	public var extents:b2Vec2 = new b2Vec2();	///< the half-widths
 
 
 
};
 
 
}

Here we have another object that implicitly instantiates b2Vec2 (2 of them) as part of its own instantiation. So, how often is b2OBB instantiated?

 
package Box2D.Collision.Shapes{
 
 
 
import Box2D.Common.Math.*;
import Box2D.Common.*;
import Box2D.Collision.Shapes.*;
import Box2D.Dynamics.*;
import Box2D.Collision.*;
import Box2D.Factories.b2OBBPool;
import Box2D.Factories.b2Vec2Pool;
 
/// Convex polygon. The vertices must be in CCW order for a right-handed
/// coordinate system with the z-axis coming out of the screen.
 
public class b2PolygonShape extends b2Shape
{
 
/// ***  SNIP
 
// implicitly instantiated as part of instantiation of b2PolygonShape
public var m_obb:b2OBB = new b2OBB();

Well, how often is a b2PolygonShape instantiated? Not nearly every frame, but definitely any time we generate a new physics body. So why not create a pool for it just like the one we created for ClipVertex?

package Box2D.Pools {
	import Box2D.Collision.b2OBB;
	import Box2D.Common.Math.b2Mat22;
	import Box2D.Common.Math.b2Vec2;
	/**
	 * ...
	 * @author The Horseman @ http://www.scriptocalypse.com
	 */
	public class b2OBBPool{
 
		private static var m_pool:Array = [];
		private static var m_poolLength:uint = 0;
 
		public static function get poolLength():Number {
			return m_pool.length;
		}
 
		public static function Retrieve(x:Number = 0.0, y:Number = 0.0):b2OBB {
 
			var result:b2OBB;
 
			if (!m_pool.length) {
				for (var i:int = 0 ; i < 500 ; i++) {
					m_pool[int(m_pool.length)] = new b2OBB();
				}
			}
			m_poolLength = m_pool.length - 1;
			result = m_pool[int(m_poolLength)];
			m_pool.length = m_poolLength;
			result.R = new b2Mat22();
			result.center.x = 0;
			result.center.y = 0;
			result.extents.x = 0;
			result.extents.y = 0;
			return result;
		}
 
		public static function Recycle(pOBB:b2OBB):void {
 
 
			if (!(pOBB is b2OBB)) return;
			m_pool[m_pool.length] = pOBB;
		}
 
	}
 
}

And now instead of calling new b2OBB() we will call b2OBBPool.Retrieve().

“But hold your horses, Horseman! When are those objects ever recycled? Aren’t you going to create them until the cows come home?”

Aaaaah, but that is not precisely true! You see, the library has built into it a non-implemented set of Create / Destroy functions for just such things as polygon shapes. In fact I believe the intention of the library authors was to have pooling of Bodies and Joints judging by the way they are created. You see, there is only one place where a call to new b2PolygonShape is ever made: b2Shape.Create(); Similarly, b2Shape has a .Destroy() function but the AS3 version of it is unimplemented. Such a shame to have an empty function call! Well since we now actually have something for that Destroy function to do (clean up our b2PolygonShape and its b2OBB) let’s implement Destroy().

static public function Destroy(shape:b2Shape, allocator:*) : void
	{
 
 
		/*b2Shape does not natively have a 
RecycleInstanceProperties function.  I have however, 
defined one for it and left it unimplemented.  The 
b2PolygonShape subclass, does override and
 implement the function.*/
 
		shape.RecycleInstanceProperties();
	}
// in b2PolygonShape
override public function RecycleInstanceProperties():void {
	super.RecycleInstanceProperties();
	b2OBBPool.Recycle(m_obb);
}

The recycle functions are called when a body is destroyed. This means that until the number of b2PolygonShape instances in existence at one time exceeds the number available in the pool we won’t ever have to re-instantiate another one. As it turns out, the most we ever seem to need is around 250. Once that number has been reached, we save on creation of b2OBB and its associated b2Vec2.

So then, when will the Horseman become adventuresome enough to fully implement those unimplemented Create/Destroy functions and give the Box2D library the ultimate in pooling?

Not anytime soon. I believe I’ve found most of the major bottlenecks already and opened them. Recycling bodies and joints might be nice, but probably won’t yield the benefits I’ve managed to gain by pooling ClipVertex, b2OBB, b2Mat22, b2XForm, b2Manifold, and the like. I’ve reduced the number of both explicit and implicit instantiations of my canary in the coal mine from 2400 per frame down to about 500 per frame during the first word drop. My changes seem to have improved the time in the physics step in the test bed applications and don’t appear to have broken them. Similarly, my banner also runs faster and has not yet shown itself to have been compromised. This is enough for the time being.

Tags: , , , , ,

  1. No comments yet.