Linked List Performance Test

I was thinking about not creating linked lists for every data type I use but using one abstract data structure containing my specific data types.

So I wrote this short performance check:

package de.superclass 
{
	import flash.display.Sprite;
	import flash.events.Event;
	import flash.events.TimerEvent;
	import flash.utils.Timer;
	import flash.utils.getTimer;
 
	public final class LinkedListTest extends Sprite 
	{
		private var _abstractItemLinkedList : AbstractItem;
		private var _dataItemLinkedList : DataItem;
		private var _vector : Vector.<DataItem>;
 
		public function LinkedListTest()
		{
			loaderInfo.addEventListener( Event.COMPLETE, onLoaderInfoComplete );
		}
 
		private function onLoaderInfoComplete( event : Event ) : void 
		{
			createData( );
 
			var timer : Timer = new Timer( 3000, 1 );
				timer.addEventListener( TimerEvent.TIMER_COMPLETE, onTimerComplete );
				timer.start();
		}
 
		private function onTimerComplete(event : TimerEvent) : void 
		{
			runTest( );
		}
 
		private function createData() : void 
		{
			var vector : Vector.<DataItem> = _vector = new Vector.<DataItem>();
			for ( var i : int = 0; i < 5000000; i++ )
			{
				var dataItem : DataItem = new DataItem();
					dataItem.index = i;
 
				vector.push( dataItem );
 
				var abstractItem : AbstractItem = new AbstractItem();
					abstractItem.data = dataItem;
 
				if ( i == 0 )
				{
					_dataItemLinkedList = dataItem;
					_abstractItemLinkedList = abstractItem;
				}
				else
				{
					previousDataItem.next = dataItem;
					previousAbstractItem.next = abstractItem;
				}
 
				var previousDataItem : DataItem = dataItem;
				var previousAbstractItem : AbstractItem = abstractItem;
			}
		}
 
		private function runTest() : void 
		{
			var dataItem : DataItem;
			var startTime : int;
 
			var vector : Vector.<DataItem> = _vector;
			var c : int = vector.length;
 
			startTime = getTimer();
			for ( var i : int = 0; i < c; i++ )
			{
				dataItem = vector[ i ];
				dataItem.index = dataItem.index;
			}
 
			var durationVector : int = getTimer() - startTime;
 
			startTime = getTimer();
			dataItem = _dataItemLinkedList;
			while ( dataItem )
			{
				dataItem.index = dataItem.index;
				dataItem = dataItem.next;
			}
 
			var durationDataItemLinkedList : int = getTimer() - startTime;
 
			startTime = getTimer( );
			var abstractItem : AbstractItem = _abstractItemLinkedList;
			while ( abstractItem )
			{
				dataItem = abstractItem.data;
				dataItem.index = dataItem.index;
				abstractItem = abstractItem.next;
			}
 
			var durationAbstractItemLinkedList : int = getTimer() - startTime;
 
			startTime = getTimer( );
			abstractItem = _abstractItemLinkedList;
			while ( abstractItem )
			{
				dataItem = DataItem( abstractItem.data );
				dataItem.index = dataItem.index;
				abstractItem = abstractItem.next;
			}
 
			var durationAbstractItemLinkedListWithCast : int = getTimer() - startTime;
 
			startTime = getTimer( );
			abstractItem = _abstractItemLinkedList;
			while ( abstractItem )
			{
				dataItem = abstractItem.data as DataItem;
				dataItem.index = dataItem.index;
				abstractItem = abstractItem.next;
			}
 
			var durationAbstractItemLinkedListWithAs : int = getTimer() - startTime;
 
			trace( "Durations:" );
			trace( "Vector", durationVector );
			trace( "DataItem LinkedList", durationDataItemLinkedList );
			trace( "AbstractItem LinkedList", durationAbstractItemLinkedList );
			trace( "AbstractItemLinkedList Using Cast", durationAbstractItemLinkedListWithCast );
			trace( "AbstractItemLinkedList Using As", durationAbstractItemLinkedListWithAs );
		}
	}
 
}
 
class AbstractItem
{
	public var data : *;
	public var next : AbstractItem;
}
 
class DataItem
{
	public var index : int;
	public var next : DataItem;
}

Results on my MacBook Pro i7:

Durations:
Vector 91
DataItem LinkedList 53
AbstractItem LinkedList 76
AbstractItemLinkedList Using Cast 108
AbstractItemLinkedList Using As 121

Alsways use explicit implemented linked lists!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.