Vectors vs. Linked Lists in AS3

One of the new features in Flash Player 10 was the Vector class, essentially a typed Array. For many operations it gives a substantial performance boost compared to Array.  See Mike Chambers’ blog posts for an introduction on using Vectors and for Vector/Array Performance Comparison.  While Vector is definitely faster than Array, if you mainly need to access values in sequence you can actually get better performance using linked lists.

Consider adding two Vectors of Numbers, with the results stored in a third Vector.  This is very common in audio signal processing – it’s how you mix two signals. The code would look something like this:

const N:uint = 1000;
var xVec:Vector.<Number> = new Vector.<Number>(N);
var yVec:Vector.<Number> = new Vector.<Number>(N);
var zVec:Vector.<Number> = new Vector.<Number>(N);

// ...Stuff some values into xVec and yVec...

// Do element-by-element addition of xVec and yVec, and put
// the results into zVec.
for ( k = 0; k < N; k++ )
{
	zVec[k] = xVec[k] + yVec[k];
}

It’s simple and straightforward, and gives decent performance, especially compared to the equivalent code using Arrays.  Suppose instead we use linked lists.  Each linked list element needs to store a Number, and a link (pointer/reference) to the next element:

final class LinkedNumber
{
	public var val:Number  = 0.0;
	public var next:LinkedNumber = null;
}

Now suppose we’ve created three linked lists X, Y, and Z, with heads xHead, yHead, and zHead. To add the elements in X and Y, and put the result into Z, we would write this:

var xLink:LinkedNumber = xHead;
var yLink:LinkedNumber = yHead;
var zLink:LinkedNumber = zHead;

for ( k = 0; k < N; k++ )
{
	zLink.val = xLink.val + yLink.val;
	xLink = xLink.next;
	yLink = yLink.next;
	zLink = zLink.next;
}

I’ve written a simple test program to compare the performance of the Array, Vector and linked list approaches.  It adds up Arrays/Vectors/linked lists with 5000 elements, and repeats it 5000 times. Click “show source” to see the full code:

package
{
	import __AS3__.vec.Vector;
	import flash.display.*;
	import flash.text.*;
	import flash.utils.getTimer;

	/**
	 * A comparison of the speed of computation using Vectors,
	 * Arrays, and linked lists.
	 *
	 * @author Gerry Beauregard
	 */
	[SWF(width='400',height='70',backgroundColor='0x777777')]

	public class LinkedListSpeedTest extends Sprite
	{
		private const N:uint = 5000;		// No. of elements in vectors/arrays/linked lists
		private const LOOPS:uint = 5000;	// No. of times to repeat the calculations

		public function LinkedListSpeedTest()
		{
			var elapsedTime:int;

			// Set up a text field to show the results
			stage.align = StageAlign.TOP_LEFT;
			stage.scaleMode = StageScaleMode.NO_SCALE;

			var textField:TextField = new TextField;
			textField.autoSize = TextFieldAutoSize.LEFT;
			textField.selectable = true;
			textField.defaultTextFormat = new TextFormat( 'Verdana', 12, 0xFFFFFF );
			addChild( textField );

			textField.text = "Time (ms)\n";

			elapsedTime = arrayTest();
			textField.appendText("Array: " + elapsedTime + "\n");

			elapsedTime = vectorTest();
			textField.appendText("Vector: " + elapsedTime + "\n");

			elapsedTime = linkedListTest();
			textField.appendText("LinkedList: " + elapsedTime + "\n");
		}

		/**
		 * Add elements of one Array to elements of another
		 * Array, and put the results into a third Array.
		 */
		private function arrayTest():int
		{
			// Create vectors
			var xArr:Array = new Array;
			var yArr:Array = new Array;
			var zArr:Array = new Array;

			// Initialize them with some values
			for ( var k:uint = 0; k < N; k++ )
			{
				xArr[k] = k;
				yArr[k] = k;
				zArr[k] = 0.0;
			}

			// Add the values in the two vectors, with result
			// in a third vector.  Repeat many times.
			var startTime:int = flash.utils.getTimer();
			for ( var j:uint = 0; j < LOOPS; j++ )
			{
				for ( k = 0; k < N; k++ )
				{
					zArr[k] = xArr[k] + yArr[k];
				}
			}
			var endTime:int = flash.utils.getTimer();

			return (endTime - startTime);
		}

		/**
		 * Add elements of one Vector to elements of another
		 * Vector, and put the results into a third Vector.
		 */
		private function vectorTest():int
		{
			// Create vectors
			var xVec:Vector.<Number> = new Vector.<Number>(N);
			var yVec:Vector.<Number> = new Vector.<Number>(N);
			var zVec:Vector.<Number> = new Vector.<Number>(N);

			// Initialize them with some values
			for ( var k:uint = 0; k < N; k++ )
			{
				xVec[k] = k;
				yVec[k] = k;
				zVec[k] = 0.0;
			}

			// Add the values in the two vectors, with result
			// in a third vector.  Repeat many times.
			var startTime:int = flash.utils.getTimer();
			for ( var j:uint = 0; j < LOOPS; j++ )
			{
				for ( k = 0; k < N; k++ )
				{
					zVec[k] = xVec[k] + yVec[k];
				}
			}
			var endTime:int = flash.utils.getTimer();

			return (endTime - startTime);
		}

		/**
		 * Add elements of one linked list to elements of another
		 * linked list, and put the results into a third linked list.
		 */
		private function linkedListTest():int
		{
			// Create linked lists of Numbers
			var xHead:LinkedNumber = createLinkedNumberVec(N);
			var yHead:LinkedNumber = createLinkedNumberVec(N);
			var zHead:LinkedNumber = createLinkedNumberVec(N);

			// Initialize them with some values
			var xLink:LinkedNumber = xHead;
			var yLink:LinkedNumber = yHead;
			var zLink:LinkedNumber = zHead;
			for ( var k:uint = 0; k < N; k++ )
			{
				xLink.val = k;
				yLink.val = k;
				zLink.val = 0.0;
				xLink = xLink.next;
				yLink = yLink.next;
				zLink = zLink.next;
			}

			// Multiply the values in the two linked lists, with result
			// in a third linked list.  Repeat many times.
			var startTime:int = flash.utils.getTimer();
			for ( var j:uint = 0; j < LOOPS; j++ )
			{
				xLink = xHead;
				yLink = yHead;
				zLink = zHead;

				for ( k = 0; k < N; k++ )
				//while ( xLink )  // << Slightly faster than the for loop.
				{
					zLink.val = xLink.val + yLink.val;
					xLink = xLink.next;
					yLink = yLink.next;
					zLink = zLink.next;
				}
			}
			var endTime:int = flash.utils.getTimer();

			return (endTime - startTime);
		}

		/**
		 * Create a linked list of LinkedNumber elements
		 */
		private function createLinkedNumberVec(n:uint):LinkedNumber
		{
			var next:LinkedNumber = null;
			for ( var k:uint = 0; k < n; k++ )
			{
				var current:LinkedNumber = new LinkedNumber;
				current.next = next;
				next = current;
			}

			return current;
		}
	}
}

/**
 * Linked list element containing a Number value.
 */
final class LinkedNumber
{
	public var val:Number  = 0.0;
	public var next:LinkedNumber = null;
}

Here are typical times I get on my old MacBook Pro (2 GHz Intel Core Duo, OS 10.6.4) using a Release Build SWF (built with Flex Builder 3, and Flex SDK 3.2), and Flash Player 10.1.53.64. The times vary a bit from run to run, but not by much.

Approach	Time (ms)
Array	1292
Vector	693
Linked List	289

Using Vectors gives you a nice performance boost compared to using Arrays, but clearly linked lists blow both away.

In some ways, this is a pity. The linked list code is messier and less intuitive. What’s more, if you need fast sequential access to the elements but also sometimes need random access, you need to use a linked list but also keep the elements in a Vector. (See An even faster AS3 FFT for an example).

If Adobe wants to make AS3 be a reasonably high performance language, improving the performance of sequential access to Vector elements would be a good place to start. Perhaps this would be possible via a tweak to the compiler and/or player?

Advertisement