We’ve seen that if-else trees are way faster than Object, Dictionary, and even switch at key-value mapping, but how do they stack up against Array and Vector? Today’s article puts them to the test and uncovers some unexpected results.

Let’s be clear up front that this isn’t really an “apples to apples” test. Both Array and Vector require integer keys. Well, technically Array doesn’t because it’s a dynamic class and you can therefore add arbitrary fields to it like you can with Object or even integer keys beyond the contiguous sequence at the start. However, if you want the full speed benefits you’ll want to use a densely-packed Array. You’ll also need to make sure your keys are contiguous integers starting at zero. This is a lot more restrictive than Object, Dictionary, switch, and if-else trees which can all include keys that are not contiguous integers starting at zero.

Regardless of these differences there are still many cases where you can use contiguous integer keys starting at zero, so let’s put Array and Vector to the test against all of the previous contestants:

  • Object
  • Dictionary (weak keys)
  • Dictionary (strong keys)
  • Array
  • Vector (dynamic length)
  • Vector (fixed length)
  • if-else trees
  • switch
package
{
	import flash.utils.Dictionary;
	import flash.text.TextField;
	import flash.utils.getTimer;
	import flash.display.Sprite;
 
	public class IfElseTreesVsObjectDictionary extends Sprite
	{
		public function IfElseTreesVsObjectDictionary()
		{
			init();
		}
 
		private function init(): void
		{
			var beforeTime:int;
			var afterTime:int;
			var i:int;
			var resInt:int;
			var object:Object = new Object();
			var dictionaryWeak:Dictionary = new Dictionary(true);
			var dictionaryStrong:Dictionary = new Dictionary(false);
			var array:Array = new Array();
			var vector:Vector.<int> = new Vector.<int>();
			var vectorFixed:Vector.<int> = new Vector.<int>(true);
			var REPS:int = 1000000;
 
			for (i = 0; i < 20; ++i)
			{
				object[i] = i;
				dictionaryWeak[i] = i;
				dictionaryStrong[i] = i;
				array[i] = i;
				vector[i] = i;
				vectorFixed[i] = i;
			}
 
			var out:String = "Map,Time\n";
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				resInt = object["0"];
				resInt = object["1"];
				resInt = object["2"];
				resInt = object["3"];
				resInt = object["4"];
				resInt = object["5"];
				resInt = object["6"];
				resInt = object["7"];
				resInt = object["8"];
				resInt = object["9"];
				resInt = object["10"];
				resInt = object["11"];
				resInt = object["12"];
				resInt = object["13"];
				resInt = object["14"];
				resInt = object["15"];
				resInt = object["16"];
				resInt = object["17"];
				resInt = object["18"];
				resInt = object["19"];
			}
			afterTime = getTimer();
			out += "Object," + (afterTime-beforeTime) + "\n";
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				resInt = dictionaryWeak[0];
				resInt = dictionaryWeak[1];
				resInt = dictionaryWeak[2];
				resInt = dictionaryWeak[3];
				resInt = dictionaryWeak[4];
				resInt = dictionaryWeak[5];
				resInt = dictionaryWeak[6];
				resInt = dictionaryWeak[7];
				resInt = dictionaryWeak[8];
				resInt = dictionaryWeak[9];
				resInt = dictionaryWeak[10];
				resInt = dictionaryWeak[11];
				resInt = dictionaryWeak[12];
				resInt = dictionaryWeak[13];
				resInt = dictionaryWeak[14];
				resInt = dictionaryWeak[15];
				resInt = dictionaryWeak[16];
				resInt = dictionaryWeak[17];
				resInt = dictionaryWeak[18];
				resInt = dictionaryWeak[19];
			}
			afterTime = getTimer();
			out += "Dictionary (weak)," + (afterTime-beforeTime) + "\n";
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				resInt = dictionaryStrong[0];
				resInt = dictionaryStrong[1];
				resInt = dictionaryStrong[2];
				resInt = dictionaryStrong[3];
				resInt = dictionaryStrong[4];
				resInt = dictionaryStrong[5];
				resInt = dictionaryStrong[6];
				resInt = dictionaryStrong[7];
				resInt = dictionaryStrong[8];
				resInt = dictionaryStrong[9];
				resInt = dictionaryStrong[10];
				resInt = dictionaryStrong[11];
				resInt = dictionaryStrong[12];
				resInt = dictionaryStrong[13];
				resInt = dictionaryStrong[14];
				resInt = dictionaryStrong[15];
				resInt = dictionaryStrong[16];
				resInt = dictionaryStrong[17];
				resInt = dictionaryStrong[18];
				resInt = dictionaryStrong[19];
			}
			afterTime = getTimer();
			out += "Dictionary (strong)," + (afterTime-beforeTime) + "\n";
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				resInt = array[0];
				resInt = array[1];
				resInt = array[2];
				resInt = array[3];
				resInt = array[4];
				resInt = array[5];
				resInt = array[6];
				resInt = array[7];
				resInt = array[8];
				resInt = array[9];
				resInt = array[10];
				resInt = array[11];
				resInt = array[12];
				resInt = array[13];
				resInt = array[14];
				resInt = array[15];
				resInt = array[16];
				resInt = array[17];
				resInt = array[18];
				resInt = array[19];
			}
			afterTime = getTimer();
			out += "Array," + (afterTime-beforeTime) + "\n";
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				resInt = vector[0];
				resInt = vector[1];
				resInt = vector[2];
				resInt = vector[3];
				resInt = vector[4];
				resInt = vector[5];
				resInt = vector[6];
				resInt = vector[7];
				resInt = vector[8];
				resInt = vector[9];
				resInt = vector[10];
				resInt = vector[11];
				resInt = vector[12];
				resInt = vector[13];
				resInt = vector[14];
				resInt = vector[15];
				resInt = vector[16];
				resInt = vector[17];
				resInt = vector[18];
				resInt = vector[19];
			}
			afterTime = getTimer();
			out += "Vector," + (afterTime-beforeTime) + "\n";
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				resInt = vectorFixed[0];
				resInt = vectorFixed[1];
				resInt = vectorFixed[2];
				resInt = vectorFixed[3];
				resInt = vectorFixed[4];
				resInt = vectorFixed[5];
				resInt = vectorFixed[6];
				resInt = vectorFixed[7];
				resInt = vectorFixed[8];
				resInt = vectorFixed[9];
				resInt = vectorFixed[10];
				resInt = vectorFixed[11];
				resInt = vectorFixed[12];
				resInt = vectorFixed[13];
				resInt = vectorFixed[14];
				resInt = vectorFixed[15];
				resInt = vectorFixed[16];
				resInt = vectorFixed[17];
				resInt = vectorFixed[18];
				resInt = vectorFixed[19];
			}
			afterTime = getTimer();
			out += "Vector (fixed)," + (afterTime-beforeTime) + "\n";
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				resInt = ifElseTree(0);
				resInt = ifElseTree(1);
				resInt = ifElseTree(2);
				resInt = ifElseTree(3);
				resInt = ifElseTree(4);
				resInt = ifElseTree(5);
				resInt = ifElseTree(6);
				resInt = ifElseTree(7);
				resInt = ifElseTree(8);
				resInt = ifElseTree(9);
				resInt = ifElseTree(10);
				resInt = ifElseTree(11);
				resInt = ifElseTree(12);
				resInt = ifElseTree(13);
				resInt = ifElseTree(14);
				resInt = ifElseTree(15);
				resInt = ifElseTree(16);
				resInt = ifElseTree(17);
				resInt = ifElseTree(18);
				resInt = ifElseTree(19);
			}
			afterTime = getTimer();
			out += "If-Else Tree," + (afterTime-beforeTime) + "\n";
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				resInt = doSwitch(0);
				resInt = doSwitch(1);
				resInt = doSwitch(2);
				resInt = doSwitch(3);
				resInt = doSwitch(4);
				resInt = doSwitch(5);
				resInt = doSwitch(6);
				resInt = doSwitch(7);
				resInt = doSwitch(8);
				resInt = doSwitch(9);
				resInt = doSwitch(10);
				resInt = doSwitch(11);
				resInt = doSwitch(12);
				resInt = doSwitch(13);
				resInt = doSwitch(14);
				resInt = doSwitch(15);
				resInt = doSwitch(16);
				resInt = doSwitch(17);
				resInt = doSwitch(18);
				resInt = doSwitch(19);
			}
			afterTime = getTimer();
			out += "Switch," + (afterTime-beforeTime) + "\n";
 
			var tf:TextField = new TextField();
			tf.width = stage.stageWidth;
			tf.height = stage.stageHeight;
			tf.text = out;
			addChild(tf);
		}
 
		[Inline]
		static private function ifElseTree(key:int): int
		{
			if (key < 10)
			{
				if (key < 5)
				{
					if (key < 2)
					{
						if (key == 0)
						{
							return 0;
						}
						else
						{
							return 1;
						}
					}
					else
					{
						if (key == 2)
						{
							return 2;
						}
						else if (key == 3)
						{
							return 3;
						}
						else
						{
							return 4;
						}
					}
				}
				else
				{
					if (key < 7)
					{
						if (key == 5)
						{
							return 5;
						}
						else
						{
							return 6;
						}
					}
					else
					{
						if (key == 7)
						{
							return 7;
						}
						else if (key == 8)
						{
							return 8;
						}
						else
						{
							return 9;
						}
					}
				}
			}
			else
			{
				if (key < 15)
				{
					if (key < 12)
					{
						if (key == 10)
						{
							return 10;
						}
						else
						{
							return 11;
						}
					}
					else
					{
						if (key == 12)
						{
							return 12;
						}
						else if (key == 13)
						{
							return 13;
						}
						else
						{
							return 14;
						}
					}
				}
				else
				{
					if (key < 17)
					{
						if (key == 15)
						{
							return 15;
						}
						else
						{
							return 16;
						}
					}
					else
					{
						if (key == 17)
						{
							return 17;
						}
						else if (key == 18)
						{
							return 18;
						}
						else
						{
							return 19;
						}
					}
				}
			}
			return -1;
		}
 
		[Inline]
		static private function doSwitch(key:int): int
		{
			switch (key)
			{
				case 0: return 0;
				case 1: return 1;
				case 2: return 2;
				case 3: return 3;
				case 4: return 4;
				case 5: return 5;
				case 6: return 6;
				case 7: return 7;
				case 8: return 8;
				case 9: return 9;
				case 10: return 10;
				case 11: return 11;
				case 12: return 12;
				case 13: return 13;
				case 14: return 14;
				case 15: return 15;
				case 16: return 16;
				case 17: return 17;
				case 18: return 18;
				case 19: return 19;
			}
			return -1;
		}
	}
}

Launch the test app

I ran this test in the following environment:

  • Release version of Flash Player 11.7.700.169
  • 2.3 Ghz Intel Core i7
  • Mac OS X 10.8.3
  • ASC 2.0 build 352231 (-debug=false -verbose-stacktraces=false -inline)

And here are the results I got:

Map Time
Object 1522
Dictionary (weak) 563
Dictionary (strong) 561
Array 76
Vector 16
Vector (fixed) 16
If-Else Tree 45
Switch 56

If-Else Trees vs. Array and Dictionary Performance Graph

If-Else Trees vs. Array and Dictionary Performance Graph (fast maps only)

The unexpected result here is that Array is actually performing worse than if-else trees despite using it with densely-packed sequential integer keys starting at zero. That’s a lot of restrictions only to take about 70% longer than the if-else trees approach.

Vector, on the other hand, fulfills its purpose as the “faster Array” class and runs about 3x faster than the second-fastest if-else trees. So, if you can handle all of the restrictions that it requires then you should definitely go with a Vector. If you need something more flexible, if-else trees still reign supreme.

Spot a bug? Have a question or suggestion? Post a comment!