When you construct an Array or a Vector, you can specify an initial size. Why would you do this?There are various reasons you may want to reserve initially-unused slots for logic reasons, but are there any performance gains to be had by pre-allocating this space for an Array or Vector you intend to completely fill right away? Today I’ll take a look to see just how much performance can be gained by pre-allocating Arrays and Vectors.

An Array or Vector can be created with no elements like so:

// Array
a = new Array();
a = [];
 
// Vector
v = new Vector.<int>();
v = new <int>[]; // Flex 4 required

You then add elements to the end of the Array or Vector like so:

// Array
a.push(123);
a[LEN] = 123; // where LEN == a.length
 
// Vector
v.push(123);
v[LEN] = 123; // where LEN == v.length

As you do this, the Flash Player does not allocate just enough room in the Array or Vector for the element you pushed, but allocates more in anticipation of future pushes. This extra allocation saves the Flash Player from the need to continually request more and more memory from the OS, which is expensive. The strategy used to determine how much extra memory should be allocated differs between Array and Vector as this test app shows:

package
{
	import flash.display.*;
	import flash.sampler.*;
	import flash.utils.*;
	import flash.text.*;
 
	public class ArrayVectorSizes extends Sprite
	{
		public function ArrayVectorSizes()
		{
			var logger:TextField = new TextField();
			logger.autoSize = TextFieldAutoSize.LEFT;
			addChild(logger);
 
			const MAX_SIZE:int = 1000;
			var i:int;
 
			logger.appendText("--Vector--\n");
 
			logger.appendText("Number of Elements,Size (bytes)\n");
 
			var v:Vector.<int> = new Vector.<int>();
			for (i = 0; i < MAX_SIZE; ++i)
			{
				v.push(i);
				logger.appendText(i + "," + getSize(v) + "\n");
			}
 
			logger.appendText("--Array--\n");
 
			logger.appendText("Number of Elements,Size (bytes)\n");
 
			var a:Array = new Array();
			for (i = 0; i < MAX_SIZE; ++i)
			{
				a.push(i);
				logger.appendText(i + "," + getSize(a) + "\n");
			}
		}
	}
}

The results, which much be fetched with a debug player as flash.sampler.getSize always returns 0 in release players, are as follows:

Array Sizes

Vector Sizes

In short, Array increases in size exponentially and Vector increases in size linearly. Array has the potential to waste much more memory than Vector, but also triggers far fewer memory allocations from the OS, which should increase speed. To test that speed, let’s look at a test app that compares filling an unallocated Array or Vector via both methods shown above and filling a pre-allocated Array or Vector by indexing:

package
{
	import flash.display.*;
	import flash.sampler.*;
	import flash.utils.*;
	import flash.text.*;
 
	public class ImportanceOfPreallocation extends Sprite
	{
		public function ImportanceOfPreallocation()
		{
			var logger:TextField = new TextField();
			logger.autoSize = TextFieldAutoSize.LEFT;
			addChild(logger);
 
			var beforeTime:int;
			var afterTime:int;
			const MAX_SIZE:int = 1000000;
			var i:int;
			var v:Vector.<int>;
			var a:Array;
 
			logger.text = "Container,push,index (empty), index(pre-allocated)\n";
 
			logger.appendText("Vector,");
 
			beforeTime = getTimer();
			v = new Vector.<int>();
			for (i = 0; i < MAX_SIZE; ++i)
			{
				v.push(i);
			}
			afterTime = getTimer();
			logger.appendText((afterTime-beforeTime) + ",");
 
			beforeTime = getTimer();
			v = new Vector.<int>();
			for (i = 0; i < MAX_SIZE; ++i)
			{
				v[i] = i;
			}
			afterTime = getTimer();
			logger.appendText((afterTime-beforeTime) + ",");
 
			beforeTime = getTimer();
			v = new Vector.<int>(MAX_SIZE);
			for (i = 0; i < MAX_SIZE; ++i)
			{
				v[i] = i;
			}
			afterTime = getTimer();
			logger.appendText((afterTime-beforeTime) + "\n");
 
			logger.appendText("Array,");
 
			beforeTime = getTimer();
			a = new Array();
			for (i = 0; i < MAX_SIZE; ++i)
			{
				a.push(i);
			}
			afterTime = getTimer();
			logger.appendText((afterTime-beforeTime) + ",");
 
			beforeTime = getTimer();
			a = new Array();
			for (i = 0; i < MAX_SIZE; ++i)
			{
				a[i] = i;
			}
			afterTime = getTimer();
			logger.appendText((afterTime-beforeTime) + ",");
 
			beforeTime = getTimer();
			a = new Array(MAX_SIZE);
			for (i = 0; i < MAX_SIZE; ++i)
			{
				a[i] = i;
			}
			afterTime = getTimer();
			logger.appendText((afterTime-beforeTime) + "\n");
		}
	}
}

I ran this test app in this environment:

  • Flex SDK (MXMLC) 4.1.0.16076, compiling in release mode (no debugging or verbose stack traces)
  • Release version of Flash Player 10.2.154.25
  • 2.4 Ghz Intel Core i5
  • Mac OS X 10.6.7

And here are the test results I got:

Container push index (empty) index(pre-allocated)
Vector 76 40 12
Array 66 53 52

Performance

As we can guess from the allocation strategies above, Array does so few memory allocations that it doesn’t benefit much from pre-allocation. In fact, you get a much larger performance increase from just not using push to fill the Array.

As for Vector, there is also a sizable performance increase from not using push. However, unlike Array, Vector benefits hugely from pre-allocation as its allocation strategy involves only incremental increases in memory and consequently many more memory allocations from the OS.

In conclusion, pre-allocation is always a good idea. You may not save much with Array, but you’re probably not using it anyhow if you are concerned with performance. The big win is with Vector: a 4-5x speedup! Also, try not to use the push function. Function calls are always expensive and it’s much quicker to rely on the built-in index operator to populate your Array and Vector objects.

Happy pre-allocating!