JacksonDunstan.com

I recently received an e-mail from asking which is faster: a DisplayObjectContainer or a Vector of DisplayObject. To ask this is to question whether or not we can do better than the Flash Player’s native container of DisplayObjects using AS3. It turns out that we can. Read on for several ways to improve on DisplayObjectContainer‘s speed.

For today’s comparison test I’ll be taking the above challenge but adding, out of curiosity, a few more collections. Here’s the complete list of what I’m testing and why:

Sprite– the simplest form of DisplayObjectContainer
Vector– the fastest indexed collection as of Flash Player 10.1
Array– in case Flash Player 9 support is required
MovieClip– in case we’re dealing with animation or an FLA
QuickSpriteVector– a Sprite derivative that holds a Vector of its children
QuickSpriteArray– a Sprite derivative that holds an Array of its children, in case of Flash Player 9

We should compare them in multiple ways so as to get a full picture of the performance characteristics in a variety of use cases. The following test will use three approaches:

Index– get a DisplayObject by index
Search (best case)– linear search for a DisplayObject that happens to be the first in the list
Search (worst base)– linear search for a DisplayObject that happens to not be in the list

Let’s take a look at the performance test:

package
{
	import flash.display.*;
	import flash.utils.*;
	import flash.text.*;
 
	public class HoldingDisplayObjects extends Sprite
	{
		private var __logger:TextField = new TextField();
		private function log(msg:*): void { __logger.appendText(msg + "\n"); }
 
		public function HoldingDisplayObjects()
		{
			__logger.autoSize = TextFieldAutoSize.LEFT;
			addChild(__logger);
 
			const SIZE:int = 100;
			const REPS:int = 1000000;
			const INDEX:int = SIZE / 2;
			var i:int;
			var j:int;
			var beforeTime:int;
			var afterTime:int;
			var childFirstArr:DisplayObject;
			var childFirstVec:DisplayObject;
			var childFirstSpr:DisplayObject;
			var childFirstMov:DisplayObject;
			var childFirstQSA:DisplayObject;
			var childFirstQSV:DisplayObject;
			var childNotInList:DisplayObject;
			var arr:Array = [];
			var vec:Vector.<DisplayObject> = new Vector.<DisplayObject>();
			var spr:Sprite = new Sprite();
			var mov:MovieClip = new MovieClip();
			var qsa:QuickSpriteArray = new QuickSpriteArray();
			var qsv:QuickSpriteVector = new QuickSpriteVector();
			var qsaChildren:Array = qsa.children;
			var qsvChildren:Vector.<DisplayObject> = qsv.children;
 
			for (i = 0; i < SIZE; ++i)
			{
				arr.push(new Sprite());
				vec.push(new Sprite());
				spr.addChild(new Sprite());
				mov.addChild(new Sprite());
				qsa.addChild(new Sprite());
				qsv.addChild(new Sprite());
			}
			childFirstArr = arr[0];
			childFirstVec = vec[0];
			childFirstSpr = spr.getChildAt(0);
			childFirstMov = mov.getChildAt(0);
			childFirstQSA = qsaChildren[0];
			childFirstQSV = qsvChildren[0];
 
			log("Index");
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				arr[INDEX];
			}
			afterTime = getTimer();
			log("\tArray: " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				vec[INDEX];
			}
			afterTime = getTimer();
			log("\tVector: " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				spr.getChildAt(INDEX);
			}
			afterTime = getTimer();
			log("\tSprite: " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				mov.getChildAt(INDEX);
			}
			afterTime = getTimer();
			log("\tMovieClip: " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				qsaChildren[INDEX];
			}
			afterTime = getTimer();
			log("\tQuickSpriteArray: " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				qsvChildren[INDEX];
			}
			afterTime = getTimer();
			log("\tQuickSpriteVector: " + (afterTime-beforeTime));
 
			log("Search (best case)");
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = 0; j < SIZE; ++j)
				{
					if (arr[j] == childFirstArr)
					{
						break;
					}
				}
			}
			afterTime = getTimer();
			log("\tArray: " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = 0; j < SIZE; ++j)
				{
					if (vec[j] == childFirstVec)
					{
						break;
					}
				}
			}
			afterTime = getTimer();
			log("\tVector: " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = 0; j < SIZE; ++j)
				{
					if (spr.getChildAt(j) == childFirstSpr)
					{
						break;
					}
				}
			}
			afterTime = getTimer();
			log("\tSprite: " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = 0; j < SIZE; ++j)
				{
					if (mov.getChildAt(j) == childFirstMov)
					{
						break;
					}
				}
			}
			afterTime = getTimer();
			log("\tMovieClip: " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = 0; j < SIZE; ++j)
				{
					if (qsaChildren[j] == childFirstQSA)
					{
						break;
					}
				}
			}
			afterTime = getTimer();
			log("\tQuickSpriteArray: " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = 0; j < SIZE; ++j)
				{
					if (qsvChildren[j] == childFirstQSV)
					{
						break;
					}
				}
			}
			afterTime = getTimer();
			log("\tQuickSpriteVector: " + (afterTime-beforeTime));
 
			log("Search (worst case)");
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = 0; j < SIZE; ++j)
				{
					if (arr[j] == childNotInList)
					{
						break;
					}
				}
			}
			afterTime = getTimer();
			log("\tArray: " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = 0; j < SIZE; ++j)
				{
					if (vec[j] == childNotInList)
					{
						break;
					}
				}
			}
			afterTime = getTimer();
			log("\tVector: " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = 0; j < SIZE; ++j)
				{
					if (spr.getChildAt(j) == childNotInList)
					{
						break;
					}
				}
			}
			afterTime = getTimer();
			log("\tSprite: " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = 0; j < SIZE; ++j)
				{
					if (mov.getChildAt(j) == childNotInList)
					{
						break;
					}
				}
			}
			afterTime = getTimer();
			log("\tMovieClip: " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = 0; j < SIZE; ++j)
				{
					if (qsaChildren[j] == childNotInList)
					{
						break;
					}
				}
			}
			afterTime = getTimer();
			log("\tQuickSpriteArray: " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = 0; j < SIZE; ++j)
				{
					if (qsvChildren[j] == childNotInList)
					{
						break;
					}
				}
			}
			afterTime = getTimer();
			log("\tQuickSpriteVector: " + (afterTime-beforeTime));
		}
	}
}
import flash.display.*;
class QuickSpriteVector extends Sprite
{
	public var children:Vector.<DisplayObject> = new Vector.<DisplayObject>();
	override public function addChild(child:DisplayObject): DisplayObject
	{
		super.addChild(child);
		if (this.children.indexOf(child) < 0)
		{
			this.children.push(child);
		}
		return child;
	}
	// TODO: Implement addChildAt, removeChild, removeChildAt, setChildIndex,
	//       swapChildren, and swapChildrenAt
}
class QuickSpriteArray extends Sprite
{
	public var children:Array = [];
	override public function addChild(child:DisplayObject): DisplayObject
	{
		super.addChild(child);
		if (this.children.indexOf(child) < 0)
		{
			this.children.push(child);
		}
		return child;
	}
	// TODO: Implement addChildAt, removeChild, removeChildAt, setChildIndex,
	//       swapChildren, and swapChildrenAt
}

Most of this test is quite straightforward, but the QuickSpriteVector and QuickSpriteArray need a bit of explaining:

Both are incomplete, as evidenced by the “TODO” comment. addChild is sufficient for the performance test.
children is public, which allows outside objects to get and change it:
- They can break this object’s internal state
- Access (dot operator) is much faster than an interface function (e.g. getChildren)
- Use (index operator) is much faster than interfaces like getChildAt function calls

With that in mind, let’s take a look at the performance results using Flash Player 10.1 on a 2.4 Ghz Intel Core i5 with Mac OS X:

Collection	Index	Search (best case)	Search (worst case)
Array	9	20	2270
Vector	7	20	2070
Sprite	30	31	3139
MovieClip	30	32	3096
QuickSpriteArray	9	21	2255
QuickSpriteVector	7	19	2082

From the above, we can glean a few key findings:

QuickSpriteVector and QuickSpriteArray predictably perform as well as their Vector and Array counterparts since all operations on them are via cached local variable references to their children
Vector and Array are about 3x faster when indexing
Searching in the best case (first element) and worst case (element not found) is about 50% faster with Vector and Array
Vector edges out Array slightly, as seen in many other tests on this site

So if accessing the elements of your DisplayObjectContainers is a cause of slowness for you, consider using an approach like QuickSprite. You’ll get a 3x performance boost for indexing and a 50% performance boost for searching!

#1 by skyboy on October 26th, 2010 · Reply

Since you don’t (nor do you need to) reassign the child vector/array, you can also make it a const, it might improve performance slightly, and will prevent accidental assignments to an unrelated array/vector. I’m also currently working on a class that will improve performance with shift/unshift/reverse operations (comparable to linkedlists) while also retaining the performance of arrays and vectors in other areas (push/pop and possibly element access. We’ll see how well that goes when I get to it).

Initial results look promising too, each has 10,000 elements

create(push) (1 operations):  12.0 array /  1319 DenseMap
-------------------------------------------------------
     pop (10000 operations):   1.0 array /     6 DenseMap
    push (10000 operations):   1.0 array /    22 DenseMap
 reverse (10000 operations): 455.0 array /     4 DenseMap
   shift (10000 operations): 130.0 array /     7 DenseMap
 unshift (10000 operations): 122.0 array /    26 DenseMap
                   Averages: 141.8 array /    13 DenseMap
 ------------------------------------------------------
                   Averages:  76.9 array / 153.8 DenseMap

#2 by jackson on October 26th, 2010 · Reply

I’ll definitely be looking at the differences between var and const again soon.

Can’t wait to see how far you can take DenseMap!
- #3 by skyboy on October 27th, 2010 · Reply
  
  I just did a quick test to see how Array and DenseMap scale with the reverse operations, and DenseMap scales at a 1:1 ratio while Array scales at .5:1
  
  10,000 elements each
  
  reverse (1000000 operations): 27827 Array / 541 DenseMap
  
  Compared to estimated:
  
  reverse (1000000 operations): 45500 Array / 400 DenseMap
  
  and statistical:
  
  reverse (1000000 operations): 22750 Array / 400 DenseMap
  
  It’s nice to know that Array doesn’t scale like I thought it would, the only thing is that for this increase in speed is an increase in the memory footprint (4x estimated when I finish the class).

#4 by DieTapete on October 27th, 2010 · Reply

Hey Jackson,
thanks for the comparison. :)
The performance of getChildByName would be interesting, too.

Holding DisplayObjects

Comments