Object VS Array VS "Native Linked List" (v2)

Revision 2 of this benchmark created by Christopher Jacobs on

Description

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 HTML

<script src="//pic-o.com/wp-content/uploads/2011/12/jsCompatible.js">
</script>
<script src="//pic-o.com/wp-content/uploads/2011/12/jsClass.js">
</script>
<script src="//pic-o.com/wp-content/uploads/2011/12/divLinkedList.js">
</script>

Setup

//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 = 1000;
    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);
    }

Teardown


    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
    ] );
    }
 

Test runner

Ready to run.

Testing in
TestOps/sec
Obj Create
read = {};
count++;
ready
Obj (blank) Property Adds
blankObj['p' + count] = count;
count++;
ready
Obj (filled) Property Adds
testObj['p' + countNext] = countNext;
countNext++;
ready
Obj Delete Starts
delete testObj['p' + count];
count++;
ready
Obj Null Starts
testObj['p' + count] = null;
count++;
ready
Obj Delete Mids
delete testObj['p' + countMid];
countMid++;
ready
Obj Null Mids
testObj['p' + countMid] = null;
countMid++;
ready
Obj Delete Ends
countNext--;
delete testObj['p' + countNext];
ready
Obj Null Ends
countNext--;
testObj['p' + countNext] = null;
ready
Obj Read start
read = testObj[objPopZero];
count++;
ready
Obj Read Mid
read = testObj[objPopMid];
count++;
ready
Obj Read End
read = testObj[objPopLimit];
count++;
ready
Obj Write Start
testObj[objPopZero] = count;
count++;
ready
Obj Write Mid
testObj[objPopMid] = count;
count++;
ready
Obj Write End
testObj[objPopLimit] = count;
count++;
ready
Array Create
read = [];
count++;
ready
Array (blank) Property Add
blankArr[count] = ('p' + count);
count++;
ready
Array (filled) Property Add
testArr[countNext] = ('p' + countNext);
countNext++;
ready
Array (blank) .push
blankArr.push(count);
count++;
ready
Array (filled) .push
testArr.push(count);
count++;
ready
Array (filled) .pop
testArr.pop();
count++;
ready
Array (filled) .shift
testArr.shift();
count++;
ready
Array (filled) .unshift
testArr.unshift(count);
count++;
ready
Array (blank) .unshift
testArr.unshift(count);
count++;
ready
Array (filled) .slice(start, mid)
read = testArr.slice(zero, populateMid);
count++;
ready
Array (filled) .slice(mid, [end])
read = testArr.slice(populateMid);
count++;
ready
Array (filled) .slice(mid, end)
read = testArr.slice(populateMid, populateNext);
count++;
ready
Array (filled) .slice(mid, end)
read = testArr.slice(populateMid, populateLimit);
count++;
ready
Array Delete Start
delete testArr[count];
count++;
ready
Array Null Start
testArr[count] = null;
count++;
ready
Array Delete Mid
delete testArr[countMid];
countMid++;
ready
Array Null Mid
testArr[countMid] = null;
countMid++;
ready
Array Delete End
countNext--;
delete testArr[countNext];
ready
Array Null End
countNext--;
testArr[countNext] = null;
ready
Array Read Start
read = testArr[zero];
count++;
ready
Array Read Mid
read = testArr[populateMid];
count++;
ready
Array Read End
read = testArr[populateLimit];
count++;
ready
Array Write Start
testArr[zero] = count;
count++;
ready
Array Write Mid
testArr[populateMid] = count;
count++;
ready
Array Write End
testArr[populateLimit] = count;
count++;
ready
Array Splice Mid Insert
testArr.splice(populateMid, 0, count);
count++;
ready
Array Splice Mid Remove
//I have no idea how to fix this, to prevent out of bound
testArr.splice(populateMid, 1);
count++;
ready
divLinkedList Create
read = new(divLinkedList)();
count++;
ready
divLinkedList Adding (blank) .sets(0, data)
blankDLL.sets(count, count);
count++;
ready
divLinkedList Adding (filled) .sets(populateNext, data)
blankDLL.sets(countNext, countNext);
countNext++;
ready
divLinkedList (blank).push
blankDLL.push(count);
count++;
ready
divLinkedList (filled).push
testDLL.push(count);
count++;
ready
divLinkedList (filled).pop
testDLL.pop();
count++;
ready
divLinkedList (filled).shift
testDLL.shift();
count++;
ready
divLinkedList (filled).unshift
testDLL.unshift(count);
count++;
ready
divLinkedList (blank).unshift
blankDLL.unshift(count);
count++;
ready
divLinkedList Null Start
testDLL.sets(0, null);
count++;
ready
divLinkedList Null Mid
testDLL.sets(populateMid, null);
count++;
ready
divLinkedList Null End
testDLL.sets(populateLimit, null);
count++;
ready
divLinkedList Null post-start
testDLL.sets(zero + 1, null);
count++;
ready
divLinkedList Null pre-End
testDLL.sets(populateLimit - 1, null);
count++;
ready
divLinkedList Read Start
read = testDLL.gets(zero);
count++;
ready
divLinkedList Read Mid
read = testDLL.gets(populateMid);
count++;
ready
divLinkedList Read End
read = testDLL.gets(populateLimit);
count++;
ready
divLinkedList Read post-Start
read = testDLL.gets(zero + 1);
count++;
ready
divLinkedList Read pre-End
read = testDLL.gets(populateLimit - 1);
count++;
ready
divLinkedList Null Mid
testDLL.sets(populateMid, null);
count++;
ready
divLinkedList Write Mid
testDLL.sets(populateMid, count);
count++;
ready
divLinkedList Splice Mid Insert
testDLL.splice(populateMid, 0, count);
count++;
ready
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++;
ready
Array splice removal
//I have no idea how to fix this, to prevent out of bound
testArr.splice(populateMid, 1);
count++;
ready
Array splice removal add
//I have no idea how to fix this, to prevent out of bound
testArr.splice(populateMid, 1, count);
count++;
ready
Array splice beginning
testArr.splice(0, 1);
count++;
ready

Revisions

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