Continuing in the series on linked lists that started with parts one and two, today I’ll make the first serious optimization pass on the LinkedList implementation. Read on for how successful this is.

Firstly, while I claimed last time that the API was complete, I changed it slightly this time. I realized that the two Array constructors (size and arguments) were actually one constructor. This allowed me to eliminate the fromValues static function and merge it into the LinkedList constructor. Other than this, the API remains stable. I also added some safety to the join function by handling the empty list case. Now, let’s look function-by-function at this round of optimization:

Function Optimization
Constructor/fromValues

Inlined and specialized push calls.
elementAt Used an approach similar to Duff’s Device to minimize iteration and checking with if.
concat Inlined and specialized push calls.
filter Inlined and specialized push calls.
join Handled empty list case (a minor performance decrease).
map Inlined and specialized push calls.
push Reorganized around a temporary newNode variable.
slice Inlined and specialized push calls.
splice Inlined and specialized push calls.
toString Inlined join.
toLocaleString Inlined join.
unshift Reorganized around a temporary newNode variable.
toArray Pre-allocated array. Inlined and specialized push calls.
fromArray Inlined and specialized push calls.

As you can see from the table, most of the work involved inlining calls to push Function calls are quite slow in AS3 and var args functions like push are especially slow. So eliminating them became a natural first step in the optimization effort. It also allows some specialization of the function to the unique circumstances in which it’s being used. For example, there’s no need for the var args loop anymore since we are always pushing a single value. This eliminates another slow item: array access. The join method was also inlined in toString and toLocaleString, but I haven’t even been testing those methods as they (unlike join) are not frequently used in performance-critical areas. In unshift and push I created a newNode temporary variable outside of the loop and used it to get around a lot of field access. While field access is usually a minor concern, it’s still more expensive than accessing the local newNode temporary variable.

Definitely the most obscure optimization here is in elementAt. We saw last time that indexOf was taking a horrendous amount of time compared to its Array equivalent: the lowly [] operator. This slowness is fundamental to linked lists because of the need to “walk” the list while counting until the index is reached. If you need to do lots of random access (ie. elementAt/[]), you should probably not be using a linked list in the first place. However, we should still try to minimize the pain for those cases where usage is light and a linked list is still desirable due to its benefits in other areas. The really expensive part of the old elementAt implementation was the if check at every single iteration. I recalled reading about Duff’s Device before and, while it seems truly strange, figured that a similar approach could be used here. The idea is to check a several of the upcoming elements every iteration rather than just the current one. A switch is handy here and can be expanded by simple copy/paste to increase or decrease the lookahead range; I settled on 10 elements as diminishing returns set in.

So, let’s have a look at the new code:

LinkedListNode

No changes.

package
{
	/**
	*   A node in a linked list. Its purpose is to hold the data in the
	*   node as well as links to the previous and next nodes.
	*   @author Jackson Dunstan
	*/
	public class LinkedListNode
	{
		public var next:LinkedListNode;
		public var prev:LinkedListNode;
		public var data:*;
		public function LinkedListNode(data:*=undefined)
		{
			this.data = data;
		}
	}
}
LinkedList

Optimizations, an API change, and a bug fix as mentioned above.

package
{
	/**
	*   A linked list, which is a single-dimensional chain of objects called
	*   nodes. This implementation is doubly-linked, so each node has a link
	*   to the next and previous node. It's API is designed to mimic that of
	*   the top-level Array class.
	*   @author Jackson Dunstan
	*/
	public class LinkedList
	{
		public var head:LinkedListNode;
		public var tail:LinkedListNode;
		public var length:int;
 
		public function LinkedList(...values)
		{
			var len:int = this.length = values.length;
			var head:LinkedListNode = null;
			var newNode:LinkedListNode;
			var i:int;
 
			// Equivalent to Array(len)
			if (len == 1)
			{
				len = values[0];
				head = this.tail = newNode = new LinkedListNode();
				for (i = 1; i < len; ++i)
				{
					newNode = new LinkedListNode();
					newNode.next = head;
					head.prev = newNode;
					head = newNode;
				}
			}
			// Equivalent to Array(value0, value1, ..., valueN)
			else if (len > 1)
			{
				i = len-1;
				head = this.tail = newNode = new LinkedListNode(values[i--]);
				for (; i >= 0; --i)
				{
					newNode = new LinkedListNode(values[i]);
					newNode.next = head;
					head.prev = newNode;
					head = newNode;
				}
			}
			this.head = head;
		}
 
		/**
		*   Equivalent to the Array [] operator
		*   @param index Index of the element to get
		*   @return The element at the given index
		*/
		public function elementAt(index:int): *
		{
			if (index < 0)
			{
				throw new TypeError("Error #2007");
			}
			else if (index >= this.length)
			{
				return undefined;
			}
			else
			{
				var halfLength:int = this.length >> 1;
				var cur:LinkedListNode;
				var i:int;
				// Element is in the first half, start at beginning
				if (index < halfLength)
				{
					i = 0;
					cur = this.head;
					while (true)
					{
						switch (index-i)
						{
							case 0:
								return cur.data;
							case 1:
								return cur.next.data;
							case 2:
								return cur.next.next.data;
							case 3:
								return cur.next.next.next.data;
							case 4:
								return cur.next.next.next.next.data;
							case 5:
								return cur.next.next.next.next.next.data;
							case 6:
								return cur.next.next.next.next.next.next.data;
							case 7:
								return cur.next.next.next.next.next.next.next.data;
							case 8:
								return cur.next.next.next.next.next.next.next.next.data;
							case 9:
								return cur.next.next.next.next.next.next.next.next.next.data;
							case 10:
								return cur.next.next.next.next.next.next.next.next.next.next.data;
 
						}
						cur = cur.next.next.next.next.next.next.next.next.next.next.next;
						i += 11;
					}
				}
				// Element is in the second half, start at the end
				else
				{
					i = this.length-1;
					cur = this.tail;
					while (true)
					{
						switch (i-index)
						{
							case 0:
								return cur.data;
							case 1:
								return cur.prev.data;
							case 2:
								return cur.prev.prev.data;
							case 3:
								return cur.prev.prev.prev.data;
							case 4:
								return cur.prev.prev.prev.prev.data;
							case 5:
								return cur.prev.prev.prev.prev.prev.data;
							case 6:
								return cur.prev.prev.prev.prev.prev.prev.data;
							case 7:
								return cur.prev.prev.prev.prev.prev.prev.prev.data;
							case 8:
								return cur.prev.prev.prev.prev.prev.prev.prev.prev.data;
							case 9:
								return cur.prev.prev.prev.prev.prev.prev.prev.prev.prev.data;
							case 10:
								return cur.prev.prev.prev.prev.prev.prev.prev.prev.prev.prev.data;
						}
						cur = cur.prev.prev.prev.prev.prev.prev.prev.prev.prev.prev.prev;
						i -= 11;
					}
				}
			}
		}
 
		public function concat(...args): LinkedList
		{
			var ret:LinkedList = new LinkedList();
			var newNode:LinkedListNode;
 
			// Add everything from this list
			for (var cur:LinkedListNode = this.head; cur; cur = cur.next)
			{
				newNode = new LinkedListNode(cur.data);
				newNode.prev = ret.tail;
				if (ret.tail)
				{
					ret.tail.next = newNode;
				}
				else
				{
					ret.head = newNode;
				}
				ret.tail = newNode;
			}
 
			// Add everything from args
			var list:LinkedList;
			for each (var arg:* in args)
			{
				// Lists get flattened
				if (arg is LinkedList)
				{
					list = arg;
					for (cur = list.head; cur; cur = cur.next)
					{
						newNode = new LinkedListNode(cur.data);
						newNode.prev = ret.tail;
						if (ret.tail)
						{
							ret.tail.next = newNode;
						}
						else
						{
							ret.head = newNode;
						}
						ret.tail = newNode;
					}
				}
				// No flattening for any other type, even Array
				else
				{
					newNode = new LinkedListNode(arg);
					newNode.prev = ret.tail;
					if (ret.tail)
					{
						ret.tail.next = newNode;
					}
					else
					{
						ret.head = newNode;
					}
					ret.tail = newNode;
				}
			}
			return ret;
		}
 
		public function every(callback:Function, thisObject:*=null): Boolean
		{
			var index:int = 0;
			for (var cur:LinkedListNode = this.head; cur; cur = cur.next)
			{
				if (!callback.call(thisObject, cur.data, index, this))
				{
					return false;
				}
				index++;
			}
			return true;
		}
 
		public function filter(callback:Function, thisObject:*=null): LinkedList
		{
			var ret:LinkedList = new LinkedList();
			var index:int = 0;
			var newNode:LinkedListNode;
			for (var cur:LinkedListNode = this.head; cur; cur = cur.next)
			{
				if (callback.call(thisObject, cur.data, index, this))
				{
					newNode = new LinkedListNode(cur.data);
					newNode.prev = ret.tail;
					if (ret.tail)
					{
						ret.tail.next = newNode;
					}
					else
					{
						ret.head = newNode;
					}
					ret.tail = newNode;
				}
				index++;
			}
			return ret;
		}
 
		public function forEach(callback:Function, thisObject:*=null): void
		{
			var index:int = 0;
			for (var cur:LinkedListNode = this.head; cur; cur = cur.next)
			{
				callback.call(thisObject, cur.data, index, this);
				index++;
			}
		}
 
		public function indexOf(searchElement:*, fromIndex:int=0): int
		{
			var index:int = 0;
			for (var cur:LinkedListNode = this.head; cur && index < fromIndex; cur = cur.next)
			{
				index++;
			}
			for (; cur; cur = cur.next)
			{
				if (cur.data == searchElement)
				{
					return index;
				}
			}
			return -1;
		}
 
		public function join(sep:*=","): String
		{
			if (!this.head)
			{
				return "";
			}
 
			var ret:String = "";
			for (var curNode:LinkedListNode = this.head; curNode; curNode = curNode.next)
			{
				ret += curNode.data + sep;
			}
			return ret.substr(0, ret.length-sep.length);
		}
 
		public function lastIndexOf(searchElement:*, fromIndex:int=0x7fffffff): int
		{
			var index:int = this.length-1;
			for (var cur:LinkedListNode = this.tail; cur && index > fromIndex; cur = cur.prev)
			{
				index--;
			}
			for (; cur; cur = cur.prev)
			{
				if (cur.data == searchElement)
				{
					return index;
				}
				index--;
			}
			return -1;
		}
 
		public function map(callback:Function, thisObject:*=null): LinkedList
		{
			var ret:LinkedList = new LinkedList();
			var index:int = 0;
			var newNode:LinkedListNode;
			for (var cur:LinkedListNode = this.head; cur; cur = cur.next)
			{
				newNode = new LinkedListNode(callback.call(thisObject, cur.data, index, this));
				newNode.prev = ret.tail;
				if (ret.tail)
				{
					ret.tail.next = newNode;
				}
				else
				{
					ret.head = newNode;
				}
				ret.tail = newNode;
				index++;
			}
			return ret;
		}
 
		public function pop(): *
		{
			if (this.tail)
			{
				var ret:* = this.tail.data;
				this.tail = this.tail.prev;
				this.length--;
				return ret;
			}
			else
			{
				return undefined;
			}
		}
 
		public function push(...args): void
		{
			var numArgs:int = args.length;
			var arg:*;
			var newNode:LinkedListNode;
 
			for (var i:int = 0; i < numArgs; ++i)
			{
				arg = args[i];
				newNode = new LinkedListNode(arg);
				newNode.prev = this.tail;
				if (this.tail)
				{
					this.tail.next = newNode;
				}
				else
				{
					this.head = newNode;
				}
				this.tail = newNode;
			}
			this.length += numArgs;
		}
 
		public function reverse(): LinkedList
		{
			var front:LinkedListNode = this.head;
			var back:LinkedListNode = this.tail;
			var temp:*;
			while (front != back && back.prev != front)
			{
				temp = front.data;
				front.data = back.data;
				back.data = temp;
 
				front = front.next;
				back = back.prev;
			}
 
			return this;
		}
 
		public function shift(): *
		{
			if (this.head)
			{
				var ret:* = this.head.data;
				this.head = this.head.next;
				this.length--;
				return ret;
			}
			else
			{
				return undefined;
			}
		}
 
		public function slice(startIndex:int=0, endIndex:int=16777215): LinkedList
		{
			var ret:LinkedList = new LinkedList();
			if (startIndex >= this.length || endIndex <= startIndex)
			{
				return ret;
			}
 
			var cur:LinkedListNode = this.head;
			var i:int;
			var newNode:LinkedListNode;
			for (i = 0; i < startIndex && cur; ++i)
			{
				cur = cur.next;
			}
			for (; i < endIndex && cur; ++i)
			{
				newNode = new LinkedListNode(cur.data);
				newNode.prev = ret.tail;
				if (ret.tail)
				{
					ret.tail.next = newNode;
				}
				else
				{
					ret.head = newNode;
				}
				ret.tail = newNode;
				cur = cur.next;
			}
			return ret;
		}
 
		public function some(callback:Function, thisObject:*=null): Boolean
		{
			var index:int = 0;
			for (var cur:LinkedListNode = this.head; cur; cur = cur.next)
			{
				if (callback.call(thisObject, cur.data, index, this))
				{
					return true;
				}
				index++;
			}
			return false;
		}
 
		public function sort(...args): LinkedList
		{
			var arr:Array = toArray();
			return fromArray(arr.sort.apply(arr, args));
		}
 
		public function sortOn(fieldName:Object, options:Object=null): LinkedList
		{
			var arr:Array = toArray();
			return fromArray(arr.sortOn.call(arr, fieldName, options));
		}
 
		public function splice(startIndex:int, deleteCount:int, ...values): LinkedList
		{
			var ret:LinkedList = new LinkedList();
			var cur:LinkedListNode = this.head;
			var endIndex:int = startIndex + deleteCount;
			var i:int;
			var newNode:LinkedListNode;
			for (i = 0; i < startIndex && cur; ++i)
			{
				cur = cur.next;
			}
			for (; i < endIndex && cur; ++i)
			{
				// Push current node to spliced list
				newNode = new LinkedListNode(cur.data);
				newNode.prev = ret.tail;
				if (ret.tail)
				{
					ret.tail.next = newNode;
				}
				else
				{
					ret.head = newNode;
				}
				ret.tail = newNode;
 
				// Unlink current node and move on
				cur.next = cur.next.next;
				cur.next.prev = cur;
				cur = cur.next;
			}
			this.length -= deleteCount;
			return ret;
		}
 
		public function toString(): String
		{
			if (!this.head)
			{
				return "";
			}
 
			var ret:String = "";
			for (var curNode:LinkedListNode = this.head; curNode; curNode = curNode.next)
			{
				ret += curNode.data + ",";
			}
			return ret.substr(0, ret.length-1);
		}
 
		public function toLocaleString(): String
		{
			if (!this.head)
			{
				return "";
			}
 
			var ret:String = "";
			for (var curNode:LinkedListNode = this.head; curNode; curNode = curNode.next)
			{
				ret += curNode.data + ",";
			}
			return ret.substr(0, ret.length-1);
		}
 
		public function unshift(...args): void
		{
			var numArgs:int = args.length;
			var arg:*;
			var newNode:LinkedListNode;
			for (var i:int = 0; i < numArgs; ++i)
			{
				arg = args[i];
				newNode = new LinkedListNode(arg);
				newNode.next = this.head;
				if (this.head)
				{
					this.head.prev = newNode;
				}
				else
				{
					this.tail = newNode;
				}
				this.head = newNode;
			}
			this.length += numArgs;
		}
 
		private function toArray(): Array
		{
			var ret:Array = new Array(this.length);
			var i:int = 0;
			for (var cur:LinkedListNode = this.head; cur; cur = cur.next)
			{
				ret[i] = cur.data;
				i++;
			}
			return ret;
		}
 
		private function fromArray(arr:Array): LinkedList
		{
			var ret:LinkedList = new LinkedList();
			var newNode:LinkedListNode;
			for each (var val:* in arr)
			{
				newNode = new LinkedListNode(val);
				newNode.prev = ret.tail;
				if (ret.tail)
				{
					ret.tail.next = newNode;
				}
				else
				{
					ret.head = newNode;
				}
				ret.tail = newNode;
			}
			return ret;
		}
	}
}
LinkedListPerformance

No changes, even to the numbers of iterations.

package
{
	import flash.display.*;
	import flash.events.*;
	import flash.text.*;
	import flash.utils.*;
 
	/**
	*   An app to test linked list performance
	*   @author Jackson Dunstan
	*/
	public class LinkedListPerformance extends Sprite
	{
		public function LinkedListPerformance()
		{
			// Setup logger
			var logger:TextField = new TextField();
			logger.autoSize = TextFieldAutoSize.LEFT;
			addChild(logger);
			function log(msg:*): void { logger.appendText(msg); }
 
			// Properties
			const VALUE:Object = {val:33};
			const ALTERNATE_VALUE:Object = {val:44};
			const SIZE:int = 10000;
			const SORT_ON_PROP_NAME:String = "val";
			const ELEMENTATINDEX:int = SIZE >> 1;
			const SPLICE_START:int = 0;
			const SLICE_START:int = 00;
			const SLICE_END:int = SIZE;
 
			// Iterations
			const TRAVERSES:int = 100;
			const ELEMENTATS:int = 100000;
			const CONCATS:int = 10;
			const EVERYS:int = 10;
			const FILTERS:int = 10;
			const FOREACHS:int = 10;
			const INDEXOFS:int = 100;
			const JOINS:int = 1;
			const MAPS:int = 1;
			const PUSHPOPS:int = 100000;
			const REVERSES:int = 100;
			const SLICES:int = 100;
			const SOMES:int = 1;
			const SORTS:int = 1;
			const SORTONS:int = 1;
			const SPLICES:int = 10000;
			const UNSHIFTSHIFTS:int = 10000;
 
			// Test variables
			var array:Array;
			var list:LinkedList;
			var beforeTime:int;
			var curNode:LinkedListNode;
			var i:int;
			var j:int;
 
			// Populate the array
			array = [];
			for (i = 0; i < SIZE; ++i)
			{
				array[i] = VALUE;
			}
 
			// Populate the list
			list = new LinkedList();
			for (i = 0; i < SIZE; ++i)
			{
				list.push(VALUE);
			}
 
			log("traverse (" + TRAVERSES + " operations): ");
 
			beforeTime = getTimer();
			for (j = 0; j < TRAVERSES; ++j)
			{
				for (i = 0; i < SIZE; ++i)
				{
					array[i];
				}
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (j = 0; j < TRAVERSES; ++j)
			{
				for (curNode = list.head; curNode; curNode = curNode.next)
				{
					curNode.data;
				}
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("elementAt/[] (" + ELEMENTATS + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < ELEMENTATS; ++i)
			{
				array[ELEMENTATINDEX];
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < ELEMENTATS; ++i)
			{
				list.elementAt(ELEMENTATINDEX);
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("concat (" + CONCATS + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < CONCATS; ++i)
			{
				array.concat(array);
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < CONCATS; ++i)
			{
				list.concat(list);
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("every (" + EVERYS + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < EVERYS; ++i)
			{
				array.every(arrayCallbackTrue);
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < EVERYS; ++i)
			{
				list.every(listCallbackTrue);
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("filter (" + FILTERS + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < FILTERS; ++i)
			{
				array.filter(arrayCallbackTrue);
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < FILTERS; ++i)
			{
				list.filter(listCallbackTrue);
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("forEach (" + FOREACHS + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < FOREACHS; ++i)
			{
				array.forEach(arrayCallbackTrue);
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < FOREACHS; ++i)
			{
				list.forEach(listCallbackTrue);
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("indexOf (" + INDEXOFS + " operations): ");
 
			array[SIZE-1] = ALTERNATE_VALUE;
			beforeTime = getTimer();
			for (i = 0; i < INDEXOFS; ++i)
			{
				array.indexOf(ALTERNATE_VALUE);
			}
			log((getTimer()-beforeTime) + " array/");
			array[SIZE-1] = VALUE;
 
			list.tail.data = ALTERNATE_VALUE;
			beforeTime = getTimer();
			for (i = 0; i < INDEXOFS; ++i)
			{
				list.indexOf(ALTERNATE_VALUE);
			}
			log((getTimer()-beforeTime) + " list\n");
			list.tail.data = VALUE;
 
			log("join (" + JOINS + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < JOINS; ++i)
			{
				array.join();
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < JOINS; ++i)
			{
				list.join();
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("lastIndexOf (" + INDEXOFS + " operations): ");
 
			array[0] = ALTERNATE_VALUE;
			beforeTime = getTimer();
			for (i = 0; i < INDEXOFS; ++i)
			{
				array.lastIndexOf(ALTERNATE_VALUE);
			}
			log((getTimer()-beforeTime) + " array/");
			array[0] = VALUE;
 
			list.head.data = ALTERNATE_VALUE;
			beforeTime = getTimer();
			for (i = 0; i < INDEXOFS; ++i)
			{
				list.lastIndexOf(ALTERNATE_VALUE);
			}
			log((getTimer()-beforeTime) + " list\n");
			list.head.data = VALUE;
 
			log("map (" + MAPS + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < MAPS; ++i)
			{
				array.map(arrayCallbackTrue);
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < MAPS; ++i)
			{
				list.map(listCallbackTrue);
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("pop (" + PUSHPOPS + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < PUSHPOPS; ++i)
			{
				array.pop();
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < PUSHPOPS; ++i)
			{
				list.pop();
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("push (" + PUSHPOPS + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < PUSHPOPS; ++i)
			{
				array.push(VALUE);
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < PUSHPOPS; ++i)
			{
				list.push(VALUE);
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("reverse (" + REVERSES + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < REVERSES; ++i)
			{
				array.reverse();
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < REVERSES; ++i)
			{
				list.reverse();
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("shift (" + UNSHIFTSHIFTS + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < UNSHIFTSHIFTS; ++i)
			{
				array.shift();
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < UNSHIFTSHIFTS; ++i)
			{
				list.shift();
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("slice (" + SLICES + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < SLICES; ++i)
			{
				array.slice(SLICE_START, SLICE_END);
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < SLICES; ++i)
			{
				list.slice(SLICE_START, SLICE_END);
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("some (" + SOMES + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < SOMES; ++i)
			{
				array.some(arrayCallbackFalse);
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < SOMES; ++i)
			{
				list.some(listCallbackFalse);
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("sort (" + SORTS + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < SORTS; ++i)
			{
				array.sort();
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < SORTS; ++i)
			{
				list.sort();
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("sortOn (" + SORTONS + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < SORTONS; ++i)
			{
				array.sortOn(SORT_ON_PROP_NAME);
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < SORTONS; ++i)
			{
				list.sortOn(SORT_ON_PROP_NAME);
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("splice (" + SPLICES + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < SPLICES; ++i)
			{
				array.splice(SPLICE_START, 5, VALUE, VALUE, VALUE, VALUE, VALUE);
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < SPLICES; ++i)
			{
				list.splice(SPLICE_START, 5, VALUE, VALUE, VALUE, VALUE, VALUE);
			}
			log((getTimer()-beforeTime) + " list\n");
 
			log("unshift (" + UNSHIFTSHIFTS + " operations): ");
 
			beforeTime = getTimer();
			for (i = 0; i < UNSHIFTSHIFTS; ++i)
			{
				array.unshift(VALUE);
			}
			log((getTimer()-beforeTime) + " array/");
 
			beforeTime = getTimer();
			for (i = 0; i < UNSHIFTSHIFTS; ++i)
			{
				list.unshift(VALUE);
			}
			log((getTimer()-beforeTime) + " list\n");
		}
 
		private function arrayCallbackTrue(cur:*, index:int, list:Array): Boolean
		{
			return true;
		}
 
		private function listCallbackTrue(cur:*, index:int, list:LinkedList): Boolean
		{
			return true;
		}
 
		private function arrayCallbackFalse(cur:*, index:int, list:Array): Boolean
		{
			return false;
		}
 
		private function listCallbackFalse(cur:*, index:int, list:LinkedList): Boolean
		{
			return false;
		}
	}
}
Results
Function Operations 2.2 Ghz Intel Core 2 Duo, 2 GB RAM, Mac OS X 10.6 Speedup
traverse 100 12 array/14 linked list 0.86
elementAt/[] 100000 1 array/1567 linked list 0.00
concat 10 4 array/64 linked list 0.06
every 10 12 array/15 linked list 0.8
filter 10 16 array/47 linked list 0.34
forEach 10 12 array/14 linked list 0.86
indexOf 100 15 array/22 linked list 0.68
join 1 23 array/27 linked list 0.85
lastIndexOf 100 15 array/21 linked list 0.71
map 1 2 array/4 linked list 0.5
pop 100000 1 array/5 linked list 0.2
push 100000 7 array/86 linked list 0.08
reverse 100 21 array/141 linked list 0.15
shift 10000 332 array/0 linked list 332+
slice 100 43 array/313 linked list 0.14
some 1 10 array/14 linked list 0.71
sort 1 788 array/750 linked list 1.05
sortOn 1 171 array/203 linked list 0.84
splice 10000 20 array/40 linked list 0.5
unshift 10000 767 array/16 linked list 47.94

It sure looks like a lot of the optimizations were successful. To be sure, let’s compare with the results from the initial implementation and compute some speedups:

Function Initial Implementation First Optimizatioon Pass Speedup Factor
traverse 13 14 0.93
elementAt/[] 2614 1567 1.67
concat 176 64 2.75
every 15 15 1
filter 104 47 2.21
forEach 14 14 1
indexOf 21 22 0.95
join 27 27 1
lastIndexOf 21 21 1
map 12 4 3
pop 5 5 1
push 85 86 0.99
reverse 140 141 0.99
shift 1 0 n/a
slice 908 313 2.9
some 14 14 1
sort 848 750 1.13
sortOn 254 203 1.25
splice 63 40 1.58
unshift 15 16 0.94
Average — — 1.41

There is clearly some statistical variance in the above numbers, which account for some inexplicable slowdowns. Variance leading to speedups should hopefully counter for this. After all, empirical testing like this is never an exact science. Speaking of inexactness, shift took 0 milliseconds due to getTimer()‘s millisecond granularity. I would normally increase the number of iterations to avoid such a scenario, but keeping the number of iterations constant across tests was key here. So there is some good speedup in the shift function, but I’m not measuring it. For the average, I have counted the shift speedup factor as simply 1 (unchanged) leading to a conservative average of 41%

Please let me know in the comments if you find any bugs or have any suggestions, especially for optimizations.