usage of linked list vs array (v24)

Revision 24 of this benchmark created by raphier on

Description

Minimalistic implementation of a linked list, used to compare the performance of population and iteration a linked list implementation and a standard Array.

Preparation HTML

<script>
  Node = function(data) {
   this.data = data;
   this.next = null;
  };

 function Job(){
   return {
       head: null,
       tail: null
   };
 }

 var manager = function Manager(){
     var bundle = Job();
     
     this.set = function manager_set(value){
            bundle = {
                 head: value,
                 tail: bundle
            };
     }

    this.get = function manager_get(){
       for(var node = bundle;node.tail;node = node.tail){
          doSomething(node.head);
      }
    }


 }
  
  LinkedList = function() {
   this.head = this.tail = new Node;
  };
  
  LinkedList.prototype.add = function(data) {
   var node = new Node(data);
   this.tail.next = node;
   this.tail = node;
  }
  
  LinkedList.prototype.each = function(fn) {
   for (var node = this.head.next; node; node = node.next) {
    fn(node.data);
   }
  }

  LinkedList.prototype.eachWhile = function(fn){
     var node = this.head.next;
     while(node.next){
        fn(node.data); node = node.next;
     }
 }

  
  LinkedList.prototype.eachRecur = function(fn) {
    (function recur(it, no) {
      if (no) { it(no.data); recur(it, no.next); }
    })(fn, this.head);
  }


 function populateWorker(amount){
       ar = new manager();
       for(i=0,ii=amount;i<ii;i++){
           ar.set('hello' + i);
        }
      return ar;
 }
  
  function populateArray(amount) {
   ar = new Array();
   ar.length = amount;
   for (i = 0; i < amount; i++) {
    ar[i] = "hello " + i;
   }
   return ar;
  }
  
  function populateLinkedList(amount) {
   ll = new LinkedList();
   for (i = 0; i < amount; i++) {
    ll.add("hello " + i);
   }
   return ll;
  }
  
  function doSomething(value) {
   return value + "string concatination";
  }

  function iterateWorker(bundle){
      for(var node = bundle;node.tail;node = node.tail){
          doSomething(node.head);
      }
  }
  function iterateArray(array) {
 var i = 0;
 var l = array.length;
   for (i = 0; i < l; ++i) {
    doSomething(array[i]);
   }
  }
  
  function iterateLinkedList(list) {
   for (var node = list.head.next; node; node = list.next) {
    doSomething(node.data);
   }
  }
  
 function iterateLinkedListWhile(list){
   var node = list.head.next;
     while(node.next){
        doSomething(node.data); node = node.next;
     }
 }
  function iterateLinkedListRecur(list) {
   list.eachRecur(doSomething);
  }
  
  worker25 = populateWorker(25);
  worker100 = populateWorker(100);
  array25 = populateArray(25);
  array100 = populateArray(100);
  ll25 = populateLinkedList(25);
  ll100 = populateLinkedList(100);

</script>

Test runner

Ready to run.

Testing in
TestOps/sec
array insertion x 25
populateArray(25);
ready
linked list insertion x 25
populateLinkedList(25);
ready
array insertion x 100
populateArray(100);
ready
linked list insertion x 100
populateLinkedList(100);
ready
iterate array 25
iterateArray(array25);
ready
iterate linked list 25
iterateLinkedList(ll25);
ready
iterate array 100
iterateArray(array100);
ready
iterate linked list 100
iterateLinkedList(ll100);
ready
iterate linked list 100 recursive
iterateLinkedListRecur(ll100);
ready
populate worker 25
populateWorker(25);
ready
populate worker 100
populateWorker(100);
ready
iterate worker 25
worker25.get();
ready
iterate worker 100
worker100.get();
ready

Revisions

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