I recently received an e-mail from Dmitry Zhelnin (translation) with a test he did concerning the speed of a couple ways to get a value for a key, which I like to call a map and Wikipedia likes to call an associative array. I’d been meaning to do a similar test for a while now and, guess what, I finally have! UPDATE: fixed miss test for fixed-size Vectors.

AS3 provides many ways to map a key to a value in O(1) time. Here I’m going to test some of the most common ones (Array, Object, Dictionary, Vector, BitmapData, ByteArray) and leave out some esoteric ones that don’t have a chance at performance (XML, SharedObject, MovieClip frame labels, DisplayObject children). For those of you who laugh at some choices like BitmapData, just wait until you see the results! For now, let’s see the test:

package
{
	import flash.display.*;
	import flash.utils.*;
	import flash.text.*;
 
	/**
	*   An app to test the speed of various maps
	*   @author Jackson Dunstan
	*/
	public class MapSpeed extends Sprite
	{
		public function MapSpeed()
		{
			var logger:TextField = new TextField();
			logger.autoSize = TextFieldAutoSize.LEFT;
			addChild(logger);
			function log(msg:*): void { logger.appendText(msg + "\n"); }
 
 			var array:Array = [33];
 
 			var vectorDynamic:Vector.<int> = new Vector.<int>(1, false);
 			vectorDynamic[0] = 33;
 
 			var vectorFixed:Vector.<int> = new Vector.<int>(1, true);
 			vectorFixed[0] = 33;
 
			var object:Object = {val:33};
 
			var dictionaryStrong:Dictionary = new Dictionary(false);
			dictionaryStrong.val = 33;
 
			var dictionaryWeak:Dictionary = new Dictionary(true);
			dictionaryWeak.val = 33;
 
			var bitmapDataNoAlpha:BitmapData = new BitmapData(1, 1, false);
 
			var bitmapDataAlpha:BitmapData = new BitmapData(1, 1, true);
 
			var byteArray:ByteArray = new ByteArray();
			byteArray.writeByte(33);
 
			const NUM_ITERATIONS:int = 5000000;
			var i:int;
			var beforeTime:int;
 
			log("Hit:");
 
			beforeTime = getTimer();
			for (i = 0; i < NUM_ITERATIONS; ++i)
			{
				array[0];
			}
			log("\tArray: " + (getTimer()-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < NUM_ITERATIONS; ++i)
			{
				vectorDynamic[0];
			}
			log("\tVector Dynamic: " + (getTimer()-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < NUM_ITERATIONS; ++i)
			{
				vectorFixed[0];
			}
			log("\tVector Fixed: " + (getTimer()-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < NUM_ITERATIONS; ++i)
			{
				object.val;
			}
			log("\tObject: " + (getTimer()-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < NUM_ITERATIONS; ++i)
			{
				dictionaryStrong.val;
			}
			log("\tDictionary Strong: " + (getTimer()-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < NUM_ITERATIONS; ++i)
			{
				dictionaryWeak.val;
			}
			log("\tDictionary Weak: " + (getTimer()-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < NUM_ITERATIONS; ++i)
			{
				bitmapDataNoAlpha.getPixel(0, 0);
			}
			log("\tBitmapData no alpha, getPixel: " + (getTimer()-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < NUM_ITERATIONS; ++i)
			{
				bitmapDataNoAlpha.getPixel32(0, 0);
			}
			log("\tBitmapData no alpha, getPixel32: " + (getTimer()-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < NUM_ITERATIONS; ++i)
			{
				bitmapDataAlpha.getPixel(0, 0);
			}
			log("\tBitmapData alpha, getPixel: " + (getTimer()-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < NUM_ITERATIONS; ++i)
			{
				bitmapDataAlpha.getPixel32(0, 0);
			}
			log("\tBitmapData alpha, getPixel32: " + (getTimer()-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < NUM_ITERATIONS; ++i)
			{
				byteArray[0];
			}
			log("\tByteArray: " + (getTimer()-beforeTime));
 
			log("Miss:");
 
			beforeTime = getTimer();
			for (i = 0; i < NUM_ITERATIONS; ++i)
			{
				array[2];
			}
			log("\tArray: " + (getTimer()-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < NUM_ITERATIONS; ++i)
			{
				try
				{
					vectorDynamic[2];
				}
				catch (err:Error)
				{
				}
			}
			log("\tVector Dynamic: " + (getTimer()-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < NUM_ITERATIONS; ++i)
			{
				try
				{
					vectorFixed[2];
				}
				catch (err:Error)
				{
				}
			}
			log("\tVector Fixed: " + (getTimer()-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < NUM_ITERATIONS; ++i)
			{
				object.val2;
			}
			log("\tObject: " + (getTimer()-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < NUM_ITERATIONS; ++i)
			{
				dictionaryStrong.val2;
			}
			log("\tDictionary Strong: " + (getTimer()-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < NUM_ITERATIONS; ++i)
			{
				dictionaryWeak.val2;
			}
			log("\tDictionary Weak: " + (getTimer()-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < NUM_ITERATIONS; ++i)
			{
				bitmapDataNoAlpha.getPixel(1, 1);
			}
			log("\tBitmapData no alpha, getPixel: " + (getTimer()-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < NUM_ITERATIONS; ++i)
			{
				bitmapDataNoAlpha.getPixel32(1, 1);
			}
			log("\tBitmapData no alpha, getPixel32: " + (getTimer()-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < NUM_ITERATIONS; ++i)
			{
				bitmapDataAlpha.getPixel(1, 1);
			}
			log("\tBitmapData alpha, getPixel: " + (getTimer()-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < NUM_ITERATIONS; ++i)
			{
				bitmapDataAlpha.getPixel32(1, 1);
			}
			log("\tBitmapData alpha, getPixel32: " + (getTimer()-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < NUM_ITERATIONS; ++i)
			{
				byteArray[2];
			}
			log("\tByteArray: " + (getTimer()-beforeTime));
		}
	}
}

As you can see, I included tests for lookup misses. Here are the results for both hits and misses:

Class 3.0 Ghz Intel Core 2 Duo, 4 GB RAM, Windows XP
Array 37 hit, 194 miss
Vector Dynamic 25 hit, 12313 miss
Vector Fixed 25 hit, 12234 miss
Object 280 hit, 316 miss
Dictionary Strong 296 hit, 399 miss
Dictionary Weak 293 hit, 400 miss
BitmapData no alpha, getPixel 53 hit, 60 miss
BitmapData no alpha, getPixel32 54 hit, 61 miss
BitmapData alpha, getPixel 67 hit, 58 miss
BitmapData alpha, getPixel32 68 hit, 59 miss
ByteArray 48 hit, 44 miss

I’d be surprised if there weren’t one or two shockers in there for any AS3 programmer! The one that should leap right out at you is the huge penalty for missing on a Vector. It’s 500 times slower, likely due to the thrown error which must be allocated and dealt with. Do not ever use a Vector if you expect lookup misses!. It would be much better to accept the moderate slowdown of a plain old Array unless your misses will be fewer than 1 in every 500 lookups.

Also worth noting with regard to lookup misses is the performance of BitmapData objects with alpha. Here we see lookup misses bucking the trend set by all the other classes and actually performing better than hits! If you expect a lot of misses and are going with BitmapData to store integer-indexed values, you may well choose to enable alpha to get the speed boost. This would only happen in some very special circumstances, but it’s nice to know that the option is there.

Now on the the more commonly-desired trait of a map: raw speed under ideal circumstances. After all, if you can design around the requirement that Array, Vector, ByteArray, and BitmapData all require integer keys and arrange things carefully to avoid lookup misses, you simply want the fastest AS3 has to offer. In this case the choice is simple. You want a Vector. It’s good that the Vector class is the fastest since it was, after all, introduced in Flash Player 10 to provide better speed than Array. Unfortunately, it only seems to be about 50% faster in these lookups. If you stick with fixed-length Vectors though, you’ll also get a far superior miss time. Add to that the non-performance benefits of having a type and you’ve (usually) got a winner. If you don’t want to limit yourself to Flash 10, need dynamic sizing and expect misses, want to be able to call sortOn without losing a ton of performance, or have any other reasons to not use Vector, you have close runner-ups in the good old Array and the number-only ByteArray and BitmapData. Just steer clear of Object and Dictionary if you want speed. String and Object keys are nice and all, but they may tank your performance.

Choose wisely everyone!