Posts Tagged ‘experimental’

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 Comment


A Horseman with a Battle-HaXe?

Different developers are attracted to Flash and ActionScript for different reasons. The Horseman’s own personal reasons were (and largely still are) that the platform offers a powerful way to present deeply interactive content (e.g. Games) across the web without worrying about cross-browser limitations and the iffy performance and radically different implementations of JavaScript engines. Also, there was a time when The Horseman found the vagaries of “real” programming languages intimidating, and back before the days of the internet he considered himself too much a starving artist to afford a decent book on programming to find out otherwise.

Obviously The Horseman is not the only person on the web who is interested in the prospect of interoperability and code portability. It was practically the rallying cry of Java in the early days, and the authors of jQuery and MooTools are quick to point out that they are at war with the web browser, not with other libraries. Of course as portable as these solutions are, Java, Flash, the Ajax libraries, all of these languages, and the codebases on which they’re built, are only as portable as their targets. I grant you that many of those targets are pretty darn portable! But there are other things to consider as well…

Let’s say you spend a lot of time building up a library of components using the Flex 2 framework. Let’s say it’s something like the Flare project. If you try to make use of Flare in a Flex 4 project, things break all over the place. Many things simply won’t compile. You’ll have to use addElement instead of addChild, which is a problem as nothing in the library is a UIComponent… it’s all based on Sprite. This is particularly troublesome since the whole library is in a .swc file which means getting to and editing the source code is a pain. Even once you get various samples “working” in the sense that they visualize you may find that radial text won’t render properly, and embedding doesn’t work as it did in the Flex 2 demos.

How then are you to develop a Flare app in a modern Flex project? Is Flare not written in AS3? It absolutely is! It made the terrible mistake however, of marrying itself to the Flex Framework at the wrong time and in the wrong ways. Despite the fact that it exists to be compiled into a swf, a filetype whose very intention is to be a universal medium and which ostensibly should be usable for years as long as there is an AS3, is in fact quite limited now in how it can be deployed in its most ideal form.

There’s something very wrong with this picture. Consider that the .swf is currently about the best we actually have in terms of delivering consistent, cross-browser, multi-platform rich interactive experience with reasonable performance and adoption rates. Regardless of what you might hear from certain company’s marketing departments, the alternatives to Flash in this capacity are mostly grim. But isn’t the sort of self-obsolescence that plagues the Flare library grim as well? Isn’t that one of the things *we wanted to get away from* when we came to the world of Flash?

That was what led me to give a serious look at a language that I’d not paid much attention to previously : haXe. I think in the early going the promise and potential of this language wasn’t quite as clear as it is (slowly) becoming. Picture a world in which you write one codebase and run the build script. You now have on your hard drive:

  • A .swf file,
  • A .js file,
  • And an .exe

All three of these files, when run in their native environments, do precisely the same thing. Even better, your .swf is leaner and higher performance than it would be if you’d built it with the Flash compiler, your .js file runs as reasonably well as .js can be considered to run (but still probably has some kinks, browser vendors being what they are), and the .exe is ready to be distributed as you see fit.

That is the promise of haXe.

But can it deliver?

I’d like to think that it has the potential to deliver, though I know that there are astonishing challenges it would have to overcome, not all of which are technical.

I don’t pretend that I have a vast readership, but if there’s sufficient interest out there I may detail some of my early stumbling in getting set up with the haXe environment and working with the various open source libraries that are written for it. Would anyone be interested in such reading? I can’t promise all the entries would be interesting (or illustrate any particular successes), but they certainly would add to the body of errors (and solutions?) one might find when doing a Google search for some bit of haXe arcana.

Tags: , ,

3 Comments