If-else trees have some of the best performance of any conditional code, including if-else ladders, the ternary (? :) operator, and the switch statement. But how do they stack up against the O(1) lookups that Object and Dictionary offer us AS3 programmers? Today’s article finds out!

Clearly you won’t want to use if-else trees in place of every Object and Dictionary since they require you to write AS3 code that handles every possible key and value. But what if you really do know all the keys and values at compile time and you want the best possible performance? In that case you might consider replacing code like this:

// Create the Dictionary
myDictionary = new Dictionary();
myDictionary[0] = "a";
myDictionary[1] = "b";
myDictionary[2] = "c";
myDictionary[3] = "d";
 
// Look up the value later on
someValue = myDictionary[someKey]

With an if-else tree containing the key-value pairs (only four shown):

// No need to create anything. Lookup is an if-else tree
if (someKey < 2)
{
	if (someKey < 1)
	{
		someValue = "a"; // key = 0, value = "a"
	}
	else
	{
		someValue = "b"; // key = 1, value = "b"
	}
}
else
{
	if (someKey < 3)
	{
		someValue = "c"; // key = 2, value = "c"
	}
	else
	{
		someValue = "d"; // key = 3, value = "d"
	}
}

Will the extra typing pay off with increased performance? The following test app is designed specifically to find that out. It tests the performance of getting one million values given one of 20 keys. In the case of Object this is necessarily a String key. In all other cases an int key is used. All values are of type int. Some [Inline] functions are used to dramatically reduce the amount of code necessary with if-else trees. For this reason you’ll need to compile with ASC 2.0 for best performance.

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 REPS:int = 1000000;
 
			for (i = 0; i < 20; ++i)
			{
				object[i] = i;
				dictionaryWeak[i] = i;
				dictionaryStrong[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 = 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;
		}
	}
}

I ran this test in the following environment:

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

And here are the results I got:

Map Time
Object 1423
Dictionary (weak) 568
Dictionary (strong) 567
If-Else Tree 47
Switch 56

Performance Chart

Launch the test app

It’s clear that Object is by far the slowest way to map keys to values. Dictionary is more than twice as fast and supports additional features like weak and non-String keys. This makes Dictionary the go-to class for your general purpose key-value mapping needs.

If you don’t need general purpose mapping then your options expand to incude if-else trees and switch statements. Both are radically faster than either Object or Dictionary. You get about a 10x boost in either case! For the ultimate speed you should opt for the if-else tree and get another 20% speedup. Just keep in mind that you’ll have to type a lot more code and arguably be left with a less readable and maintainable function than with a switch statement. But for truly maximal performance it’s hard to turn down a 10x speedup!

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