JacksonDunstan.com

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!

#1 by Ben on April 29th, 2013

On my system Array is faster than the If-Else Tree:
Release player version: 11,7,700,169
OS: Windows 7 64 Bit
CPU: i7-2600 @ 3.4 GHz
Compiled with the AIR 3.6 SDK.

Map,Time
Object,1140
Dictionary (weak),382
Dictionary (strong),379
Array,44
Vector,14
Vector (fixed),15
If-Else Tree,106
Switch,156

#2 by jackson on April 29th, 2013

Did you use ASC 2.0 with the same compile flags that I did? If not, the if-else tree and switch tests will run much slower due to the lack of function inlining via [Inline].
- #3 by Ben on June 3rd, 2013
  
  Sorry that it took a while. I retested it and with the -inline option I had the following results:
  OS: Windows 7 64 Bit
  CPU: i7-2600 @ 3.4 GHz
  Compiled with the AIR 3.7 SDK.
  
  Map,Time
  Object,1125
  Dictionary (weak),375
  Dictionary (strong),390
  Array,46
  Vector,16
  Vector (fixed),16
  If-Else Tree,46
  Switch,47
  
  The results match your results in my opinion.

#4 by henke37 on April 29th, 2013

You forgot ByteArray with a manually computed position.

#5 by jackson on April 29th, 2013

I’m not sure I know what you mean. Do you mean that the key should be transformed into a position index and then some value read at that location? Like this:

[Inline]
static private function byteArray(key:int, bytes:ByteArray): int
{
    bytes.position = key * 4; // integers are four bytes long
    return bytes.readInt();
}

#6 by ben w on April 29th, 2013

Could you include a standard if else in there too, and as you are using ASC2.0 makes sense to try out the fast mem op codes, in my tests they allow for faster access that Vector. Not as practical but would probably be the fastest contender.

#7 by jackson on April 29th, 2013

I could include if-else ladders, but I disqualified them based on its poor showing in ASC 2.0 Conditionals Performance.

As for the domain memory (a.k.a. “Alchemy”, “fast memory”) opcodes support in ASC 2.0, that is a good idea. I may combine it with Ben’s comment above. I’ve also got some more general articles on the subject in the works, but I’d love to hear any specific ideas you (or anybody reading this) may have for articles on domain memory opcode support in ASC 2.0.

#8 by Glen Blanchard on April 29th, 2013

Good find, always love to see these types of tests.

Using integer indexes for the Object test will improve it’s speed and make it comparable to Dictionary in my tests though still way slower than the other faster tests.

If-Else Trees vs. Array and Vector

Comments