Vector vs. LinkedList

From ActionScript Performance Wiki

Jump to: navigation, search

Contents

Purpose

Test if it is faster to loop through a Vector or a custom linked list.

Code

package  
{
	import flash.display.Sprite;
 
	public class Test extends Sprite 
	{
		private const AMOUNT:int = 1000;
		private var vector:Vector.<ValueObject>; 
		private var linkedList:LinkedValueObject;
		private var text:String;
 
 
		public function Test()
		{
			var i:int;
 
			// create Vector
			i = AMOUNT;
			vector = new Vector.<ValueObject>();
			while (i--) 
			{
				vector.push(new ValueObject("text" + i));
			}
 
			// create linked list
			i = AMOUNT -1;
			linkedList = new LinkedValueObject("text" + i);
			var n:LinkedValueObject = linkedList;
			while (i--) 
			{
				n.link = new LinkedValueObject("text" + i);
				n = n.link;
			}
 
			trace(new PerformanceComparison(AMOUNT, test1, test2, test3).start());
		}
 
		protected function test1():void 
		{
			var vo:ValueObject;
			for each (vo in vector) {
				text = vo.text;
			}
		}
 
		protected function test2():void 
		{
			var i:int;
			for (i = 0; i < AMOUNT; i++) {
				text = vector[i].text; 
			}
		}
 
		protected function test3():void 
		{
			var vo:LinkedValueObject = linkedList;
			while (vo != null) 
			{
				text = vo.text;
				vo = vo.link;
			}
		}
	}
}
 
internal class ValueObject
{
	public var text:String;
 
	function ValueObject(text:String) 
	{
		this.text = text;
	}
}
 
internal class LinkedValueObject
{
	public var text:String;
	public var link:LinkedValueObject;
 
	function LinkedValueObject(text:String) 
	{
		this.text = text;
	}	
}

Results

Compiler version: 3.3.0.485, Player version: MAC 10.0.2.54, Operating System: Mac OS 10.5.8

Test 1
156 ms, best
Test 2
193 ms, 24% slower
Test 3
162 ms, 04% slower

Compiler version: 3.3.04852, Player version: WIN 10.0.45.2, Operating System: Windows XP

Test 1
126 ms, 05% slower
Test 2
151 ms, 26% slower
Test 3
120 ms, best

Conclusion

Retrieving text while looping through a linked list is marginally slower than looping through a vector.

Polygonal has a made a detailed test where the linked list is always the fastest.