Object VS Array VS "Native Linked List"

JavaScript performance comparison

Revision 5 of this test case created by citykid

Info

More details at my blog : http://pic-o.com/blog/2011/11/native-linked-list-hack-vs-array

Obj VS Arr VS LinkList

Javascript lacked native linkedlist support, and for an interpretive language, rebuilding the engine, is a costly alternative, marginalizing the benefits.

Or so we thought... hidden within the DOM specification, are linked lists. The ability to rapidly manipulate nested children of DOM structures in the modern browsers, is in part attributed to linked lists. Hence why not exploit it for data instead of dom objects. or perhaps both?

Test Notes

  1. All tests runs atleast an int++ / -- operation, for consistency between the various tests. [hence its faster then its reported]
  2. Setup calls are not timed;
  3. populate sets the limit / range for pre-filled content test
  4. As much as possible, we try to ensure equal, variable calls / read / writes in similar test. To provide more consistent reasults
  5. A random sample of the test is intentionally leaked to global testDump variable space, to prevent JIT optimization.

Preparation code

<script src="//pic-o.com/blog/wp-content/uploads/2011/12/jsCompatible.js">
</script>
<script src="//pic-o.com/blog/wp-content/uploads/2011/12/jsClass.js">
</script>
<script src="//pic-o.com/blog/wp-content/uploads/2011/12/divLinkedList.js">
</script>
<script>
Benchmark.prototype.setup = function() {
    //Base variable creation testing
    var read;
   
    var zero = 0;
    var blankObj = {};
    var blankArr = [];
    var blankDLL = new(divLinkedList)();
   
    //Population limit for pre generated content
    var populateLimit = 50;
    var populateMid = populateLimit / 2;
    var populateNext = populateLimit + 1;
   
    var count = 0;
    var countMid = populateMid;
    var countNext = populateNext;
   
    var objPopLimit = 'p' + populateLimit;
    var objPopMid = 'p' + populateMid;
    var objPopNext = 'p' + populateNext;
    var objPopZero = 'p' + zero;
   
    //Premade content testing
    var testObj = {};
    for (var a = 0; a <= populateLimit; a++) {
      testObj['p' + a] = a;
    }
    var testArr = [];
    for (var a = 0; a <= populateLimit; a++) {
      testArr[a] = ('p' + a);
    }
    var testDLL = new(divLinkedList)();
    for (var a = 0; a <= populateLimit; a++) {
      testDLL.push('p' + a);
    }
};

Benchmark.prototype.teardown = function() {
    if( !window.testDump ) {
    window.testDump = [];
    }
   
    if( Math.random() >= 0.9999 ) {
    window.testDump.push( [
        blankObj['p'+Math.round(Math.random()*1000)],
        (blankArr.length > 0)?( blankArr[ Math.round(Math.random()*( blankArr.length-1 )) ] ) : 0,
        (blankDLL.length > 0)?( blankDLL.gets( Math.round(Math.random()*( blankArr.length-1 )) ) ) : 0,
        testObj['p'+Math.round(Math.random()*1000)],
        (testArr.length > 0)?( testArr[ Math.round(Math.random()*( testArr.length-1 )) ] ) : 0,
        (testDLL.length > 0)?( testDLL.gets( Math.round(Math.random()*( testDLL.length-1 )) ) ) : 0
    ] );
    }
};
</script>

Preparation code output

Test runner

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

Java applet disabled.

Testing in unknown unknown
Test Ops/sec
Obj Creates
read = {};
count++;
pending…
Obj (blank) Property Adds
blankObj['p' + count] = count;
count++;
pending…
Obj (filled) Property Adds
testObj['p' + countNext] = countNext;
countNext++;
pending…
Obj Delete Starts
delete testObj['p' + count];
count++;
pending…
Obj Null Starts
testObj['p' + count] = null;
count++;
pending…
Obj Delete Mids
delete testObj['p' + countMid];
countMid++;
pending…
Obj Null Mids
testObj['p' + countMid] = null;
countMid++;
pending…
Obj Delete Ends
countNext--;
delete testObj['p' + countNext];
pending…
Obj Null Ends
countNext--;
testObj['p' + countNext] = null;
pending…
Obj Read start
read = testObj[objPopZero];
count++;
pending…
Obj Read Mid
read = testObj[objPopMid];
count++;
pending…
Obj Read End
read = testObj[objPopLimit];
count++;
pending…
Obj Write Start
testObj[objPopZero] = count;
count++;
pending…
Obj Write Mid
testObj[objPopMid] = count;
count++;
pending…
Obj Write End
testObj[objPopLimit] = count;
count++;
pending…
Array Create
read = [];
count++;
pending…
Array (blank) Property Add
blankArr[count] = ('p' + count);
count++;
pending…
Array (filled) Property Add
testArr[countNext] = ('p' + countNext);
countNext++;
pending…
Array (blank) .push
blankArr.push(count);
count++;
pending…
Array (filled) .push
testArr.push(count);
count++;
pending…
Array (filled) .pop
testArr.pop();
count++;
pending…
Array (filled) .shift
testArr.shift();
count++;
pending…
Array (filled) .unshift
testArr.unshift(count);
count++;
pending…
Array (blank) .unshift
testArr.unshift(count);
count++;
pending…
Array (filled) .slice(start, mid)
read = testArr.slice(zero, populateMid);
count++;
pending…
Array (filled) .slice(mid, [end])
read = testArr.slice(populateMid);
count++;
pending…
Array (filled) .slice(mid, end)
read = testArr.slice(populateMid, populateNext);
count++;
pending…
Array (filled) .slice(mid, end)
read = testArr.slice(populateMid, populateLimit);
count++;
pending…
Array Delete Start
delete testArr[count];
count++;
pending…
Array Null Start
testArr[count] = null;
count++;
pending…
Array Delete Mid
delete testArr[countMid];
countMid++;
pending…
Array Null Mid
testArr[countMid] = null;
countMid++;
pending…
Array Delete End
countNext--;
delete testArr[countNext];
pending…
Array Null End
countNext--;
testArr[countNext] = null;
pending…
Array Read Start
read = testArr[zero];
count++;
pending…
Array Read Mid
read = testArr[populateMid];
count++;
pending…
Array Read End
read = testArr[populateLimit];
count++;
pending…
Array Write Start
testArr[zero] = count;
count++;
pending…
Array Write Mid
testArr[populateMid] = count;
count++;
pending…
Array Write End
testArr[populateLimit] = count;
count++;
pending…
Array Splice Mid Insert
testArr.splice(populateMid, 0, count);
count++;
pending…
Array Splice Mid Remove
//I have no idea how to fix this, to prevent out of bound
testArr.splice(populateMid, 1);
count++;
pending…
divLinkedList Create
read = new(divLinkedList)();
count++;
pending…
divLinkedList Adding (blank) .sets(0, data)
blankDLL.sets(count, count);
count++;
pending…
divLinkedList Adding (filled) .sets(populateNext, data)
blankDLL.sets(countNext, countNext);
countNext++;
pending…
divLinkedList (blank).push
blankDLL.push(count);
count++;
pending…
divLinkedList (filled).push
testDLL.push(count);
count++;
pending…
divLinkedList (filled).pop
testDLL.pop();
count++;
pending…
divLinkedList (filled).shift
testDLL.shift();
count++;
pending…
divLinkedList (filled).unshift
testDLL.unshift(count);
count++;
pending…
divLinkedList (blank).unshift
blankDLL.unshift(count);
count++;
pending…
divLinkedList Null Start
testDLL.sets(0, null);
count++;
pending…
divLinkedList Null Mid
testDLL.sets(populateMid, null);
count++;
pending…
divLinkedList Null End
testDLL.sets(populateLimit, null);
count++;
pending…
divLinkedList Null post-start
testDLL.sets(zero + 1, null);
count++;
pending…
divLinkedList Null pre-End
testDLL.sets(populateLimit - 1, null);
count++;
pending…
divLinkedList Read Start
read = testDLL.gets(zero);
count++;
pending…
divLinkedList Read Mid
read = testDLL.gets(populateMid);
count++;
pending…
divLinkedList Read End
read = testDLL.gets(populateLimit);
count++;
pending…
divLinkedList Read post-Start
read = testDLL.gets(zero + 1);
count++;
pending…
divLinkedList Read pre-End
read = testDLL.gets(populateLimit - 1);
count++;
pending…
divLinkedList Null Mid
testDLL.sets(populateMid, null);
count++;
pending…
divLinkedList Write Mid
testDLL.sets(populateMid, count);
count++;
pending…
divLinkedList Splice Mid Insert
testDLL.splice(populateMid, 0, count);
count++;
pending…
divLinkedList Splice Mid Remove
//testDLL.splice(populateMid, 1); //I have no idea how to fix this, it just ran too fast (the link list tends to runs out) and break
testDLL.splice(populateMid, 1, count);
count++;
pending…
Array splice removal
//I have no idea how to fix this, to prevent out of bound
testArr.splice(populateMid, 1);
count++;
pending…
Array splice removal add
//I have no idea how to fix this, to prevent out of bound
testArr.splice(populateMid, 1, count);
count++;
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. Here’s a list of current revisions for this page:

0 comments

Add a comment