Today’s article is in response to some interesting comments on the previous article comparing Array‘s performance to that of Vector. Today I’ll test different types of Vectors and the performance of deleting elements.

Intro

Jean-Phillipe Auclair commented that deleting elements was his problem with Array and Vector. Meanwhile, aaulia commented that the pain was in storing Objects in Arrays and Vectors. So I decided to test both of these to assess the performance and hopefully turn up a winner in these scenarios. Firstly, I decided to test deletion by traversing from back-to-front so as to not trigger any splits between Array‘s dense portion and hash table portion, which would be an unfair disadvantage when compared to Vector. Secondly, I decided to test a number of built-in types of Vectors: int, uint, Number, Boolean, String, and an empty custom type MyClass. This means that I more-or-less match the comparion aaulia linked to. While there are more built-in types, I think this is a pretty representative set for my testing purposes. So, let’s have a look at the test app:

Test App
package
{
	import flash.display.*;
	import flash.text.*;
	import flash.utils.*;
 
	public class ArrayVsVector extends Sprite
	{
		public function ArrayVsVector()
		{
			var logger:TextField = new TextField();
			logger.autoSize = TextFieldAutoSize.LEFT;
			addChild(logger);
			function log(msg:*): void { logger.appendText(msg+"\n"); }
 
			const REPS:int = 50;
			const SIZE:int = 100000;
			const VAL_INT:int = 42;
			const VAL_UINT:uint = 42;
			const VAL_NUMBER:Number = 42.0;
			const VAL_BOOLEAN:Boolean = true;
			const VAL_STRING:String = "42";
			const VAL_OBJECT:MyClass = new MyClass();
			var i:int;
			var j:int;
			var temp:*;
			var beforeTime:int;
			var afterTime:int;
 
			var array:Array = new Array(SIZE);
			var vectorInt:Vector.<int> = new Vector.<int>(SIZE, false);
			var vectorUInt:Vector.<uint> = new Vector.<uint>(SIZE, false);
			var vectorNumber:Vector.<Number> = new Vector.<Number>(SIZE, false);
			var vectorBoolean:Vector.<Boolean> = new Vector.<Boolean>(SIZE, false);
			var vectorString:Vector.<String> = new Vector.<String>(SIZE, false);
			var vectorObject:Vector.<MyClass> = new Vector.<MyClass>(SIZE, false);
			for (i = 0; i < SIZE; ++i)
			{
				array[i] = VAL_INT;
				vectorInt[i] = VAL_INT;
				vectorUInt[i] = VAL_UINT;
				vectorNumber[i] = VAL_NUMBER;
				vectorBoolean[i] = VAL_BOOLEAN;
				vectorString[i] = VAL_STRING;
				vectorObject[i] = VAL_OBJECT;
			}
 
			log("Read:");
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = 0; j < SIZE; ++j)
				{
					array[j];
				}
			}
			afterTime = getTimer();
			log("\tArray: " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = 0; j < SIZE; ++j)
				{
					vectorInt[j];
				}
			}
			afterTime = getTimer();
			log("\tVector (int): " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = 0; j < SIZE; ++j)
				{
					vectorUInt[j];
				}
			}
			afterTime = getTimer();
			log("\tVector (uint): " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = 0; j < SIZE; ++j)
				{
					vectorNumber[j];
				}
			}
			afterTime = getTimer();
			log("\tVector (Number): " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = 0; j < SIZE; ++j)
				{
					vectorBoolean[j];
				}
			}
			afterTime = getTimer();
			log("\tVector (Boolean): " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = 0; j < SIZE; ++j)
				{
					vectorString[j];
				}
			}
			afterTime = getTimer();
			log("\tVector (String): " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = 0; j < SIZE; ++j)
				{
					vectorObject[j];
				}
			}
			afterTime = getTimer();
			log("\tVector (Object): " + (afterTime-beforeTime));
 
			log("Write:");
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = 0; j < SIZE; ++j)
				{
					array[j] = VAL_INT;
				}
			}
			afterTime = getTimer();
			log("\tArray: " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = 0; j < SIZE; ++j)
				{
					vectorInt[j] = VAL_INT;
				}
			}
			afterTime = getTimer();
			log("\tVector (int): " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = 0; j < SIZE; ++j)
				{
					vectorUInt[j] = VAL_UINT;
				}
			}
			afterTime = getTimer();
			log("\tVector (uint): " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = 0; j < SIZE; ++j)
				{
					vectorNumber[j] = VAL_NUMBER;
				}
			}
			afterTime = getTimer();
			log("\tVector (Number): " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = 0; j < SIZE; ++j)
				{
					vectorBoolean[j] = VAL_BOOLEAN;
				}
			}
			afterTime = getTimer();
			log("\tVector (Boolean): " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = 0; j < SIZE; ++j)
				{
					vectorString[j] = VAL_STRING;
				}
			}
			afterTime = getTimer();
			log("\tVector (String): " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = 0; j < SIZE; ++j)
				{
					vectorObject[j] = VAL_OBJECT;
				}
			}
			afterTime = getTimer();
			log("\tVector (Object): " + (afterTime-beforeTime));
 
			log("Delete:");
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = SIZE-1; j >= 0; --j)
				{
					delete array[j];
				}
			}
			afterTime = getTimer();
			log("\tArray: " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = SIZE-1; j >= 0; --j)
				{
					delete vectorInt[j];
				}
			}
			afterTime = getTimer();
			log("\tVector (int): " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = SIZE-1; j >= 0; --j)
				{
					delete vectorUInt[j];
				}
			}
			afterTime = getTimer();
			log("\tVector (uint): " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = SIZE-1; j >= 0; --j)
				{
					delete vectorNumber[j];
				}
			}
			afterTime = getTimer();
			log("\tVector (Number): " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = SIZE-1; j >= 0; --j)
				{
					delete vectorBoolean[j];
				}
			}
			afterTime = getTimer();
			log("\tVector (Boolean): " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = SIZE-1; j >= 0; --j)
				{
					delete vectorString[j];
				}
			}
			afterTime = getTimer();
			log("\tVector (String): " + (afterTime-beforeTime));
 
			beforeTime = getTimer();
			for (i = 0; i < REPS; ++i)
			{
				for (j = SIZE-1; j >= 0; --j)
				{
					delete vectorObject[j];
				}
			}
			afterTime = getTimer();
			log("\tVector (Object): " + (afterTime-beforeTime));
		}
	}
}
class MyClass {}
Read Performance
Environment Array Vector (int) Vector (uint) Vector (Number) Vector (Boolean) Vector (String) Vector (Object)
3.0 Ghz Intel Core 2 Duo, Windows XP 38 29 (31%) 31 (23%) 30 (27%) 29 (31%) 29 (31%) 30 (27%)
2.0 Ghz Intel Core 2 Duo, Mac OS X 10.5 69 53 (30%) 53 (30%) 54 (28%) 51 (35%) 51 (35%) 51 (35%)
Write Performance
Environment Array Vector (int) Vector (uint) Vector (Number) Vector (Boolean) Vector (String) Vector (Object)
3.0 Ghz Intel Core 2 Duo, Windows XP 96 37 (259%) 37 (259%) 39 (246%) 72 (33%) 90 (7%) 131 (-36%)
2.0 Ghz Intel Core 2 Duo, Mac OS X 10.5 162 64 (253%) 63 (257%) 55 (295%) 203 (-25%) 253 (-56%) 231 (-43%)
Delete Performance
Environment Array Vector (int) Vector (uint) Vector (Number) Vector (Boolean) Vector (String) Vector (Object)
3.0 Ghz Intel Core 2 Duo, Windows XP 4544 4429 (3%) 4431 (3%) 4473 (2%) 4506 (1%) 4510 (1%) 4485 (1%)
2.0 Ghz Intel Core 2 Duo, Mac OS X 10.5 4989 4844 (3%) 4842 (3%) 4841 (3%) 4897 (2%) 4902 (2%) 5159 (-3%)
Performance Analysis

Jean-Phillipe was definitely correct about the cost of deletion. Deletion seems to be about 20 times slower than reading or writing, so you should avoid it if you can. For example, it’d be a lot cheaper to write a NaN or some other special value (null, -1, etc.) than to actually remove the element of the Array or Vector. Given the span from -1 to 3% though, it seems to make about no difference which container you delete your data from.

aaulia was also correct about writing Vectors of Objects. While reading them makes little difference compared to other types of data, writing them is about five times slower than writing other types and actually manages to make Vector slower than Array! This is sad, but it’s always good to know where you stand performance-wise when considering optimizing a chunk of code for performance.

Simply switching from Array to Vector will not always increase performance. In the case of deletion, you will not see any significant performance improvement and may see a slight performance drop on the Mac. In the case of heavy writes of Objects to the collection, switching will hurt your performance by 30-50%. While it would be very nice to flatly state “Vectors are faster than Arrays“, it seems as though that would not always be correct. We’ve just added two more reasons why that can be incorrect to the one we already knew about.