Linked List vs. Array

JavaScript performance comparison

Revision 2 of this test case created by Ryan Lynd

Preparation code

<script>
/**
 * Simple (generic) entity class
 */
var Entity = function( ) {
	var _self = this;

	this.pos = { x:0, y:0 };

	this.update = function() {
		// bad heavy arithmetic for the sake of testing
		_self.pos.x = Math.round( Math.sin( Math.random() * 100 % 23 + 14 / 32 | 0 ) );
		_self.pos.y = Math.round( Math.sin( Math.random() * 100 % 42 - 67 / 98 | 0 ) );
	};

	this.draw = function() {
		//console.log(42);
	}
}

/**
 * Turns any class into a simple Linked-List and returns the list.
 * @param  {Object} Clazz Target Class
 * @return {LinkedList}       instance of the list
 */
LinkedList = function( Clazz ) {
	// add linked list assoc. properties to class
	Clazz.prototype.__next__ = null;

	this.head = this.tail = new Clazz();
};

LinkedList.prototype.add = function( Clazz ) {
	var node = new Clazz();
	this.tail.__next__ = node;
	this.tail = node;
}

LinkedList.prototype.each = function( callback ) {
	var node = this.head.__next__;
	while ( node !== null ) {
		//callback( node );
		node.update();
		node.draw();
		node = node.__next__;
	}
}

// testing functions

// iterate through the list and call update() + draw() on each node
function iterateLinkedList( list ) {

	var updateNode = function( node ){
		node.update();
	}

	var drawNode = function( node ){
		node.draw();
	}

	list.each( updateNode );

	list.each( drawNode );
}


// iterate through the array and call update() + draw() on each object
function iterateArray( arr ) {
	var i, len = arr.length;

	i = len;
	while(i--){
		arr[i].update();
	}

	i = len;
	while(i--){
		arr[i].draw();
	}

}


function populateArray(amount) {
	ar = new Array();
	for (i = 0; i < amount; i++) {
		ar.push( new Entity() );
	}
	return ar;
}

function populateLinkedList(amount) {
	ll = new LinkedList( Entity );
	for (i = 0; i < amount; i++) {
		ll.add( Entity );
	}
	return ll;
}


array100 = populateArray( 100 );
list100 = populateLinkedList( 100 );
</script>
    

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in CCBot 2.0.0 / Other 0.0.0
Test Ops/sec
update/draw objcts in Array
iterateArray( array100 );
pending…
update/draw objects in Linked List
iterateLinkedList( list100 );
pending…
add 100 objects to Array
populateArray( 100 );
pending…
add 100 objects to Linked List
populateLinkedList( 100 );
pending…

Compare results of other browsers

Revisions

You can edit these tests or add even more tests to this page by appending /edit to the URL.

0 Comments