Arrays vs. Dictionaries

WARNING! This post is totally nerdcore.  If you have a heart condition, increased risk of an anurism or have difficulties counting your fingers then this is not for you!

Overview

I’ve been scouring the Papervison 2 code over the past couple days and I noticed that they use a lot of Dictionaries in the very heart of the library.  Every single vertex has one, there are a bunch created on the fly for organizing (i.e. merging verticies).  I had always thought that Dictionaries were more resource intensive than arrays.  So I decided to do some benchmarking.

Although I only did one test per senario (I really should do multiple tests for a more complete statistical model), I’m sure it’s not too far from a true statistical analysis.

Set Up

For the primiative tests I just used a uint.  For the object tests I used this simple class:

package
{
	import flash.events.EventDispatcher;
 
	public class ValueObject extends EventDispatcher
	{
		public var x:Number;
		public var y:Number;
		public var z:Number;
 
		public function ValueObject(x:Number=0, y:Number=0, z:Number=0)
		{
			super();
 
			this.x = x;
			this.y = y;
			this.z = z;
		}
 
		override public function toString():String
		{
			return "[ValueObject x:"" + this.x + "" y:"" + this.y + "" z:"" + this.z + ""]";
		}
	}
}

Fill Time

The first part of the test was seeing how long it takes to fill the objects.  All I used was a simple “for” loop to fill each object to any given size.

Retrieval Time

To test retrival of data it was a simple matter of using a position for the Array and the actual primative/object for the Dictionaries.  The test was run grabbing a value that was added halfway through the filling test (i.e. size / 2).

Loop Time

Looping is where things change a bit.  To loop through the Dictionaries I used a “for each” loop and just a regular old “for” loop on the Array.

Conclusion

When dealing with primatives Dictionaries will perform better than Arrays when dealing with amounts of data over 50,000.  The results aren’t shown here because the graphs would be too skewed to get any real value out of them.

The real difference between Dictionaries and Arrays comes out when you fill them with objects and start looping.  Arrays outperform Dictionaries in those tests so much that it almost doesn’t seem real.

Of course, the real value of a Dictionary is in it’s retrieval abilities since you can retrive data using any value object as opposed to a linear position.  To do something similar using an Array would be a more expensive process.