Array vs. Map vs. LinkedList vs. xxx (v3)

Revision 3 of this benchmark created by Sebastian Werner on May 11, 2011

Description

Preparation HTML

<script>
  StoreMap = function(threshold) {
   this.__threshold = threshold || 20;
   this.__objects = {};
   this.__clean = [];
  };
  
  StoreMap.prototype.add = function(obj) {
   this.__objects[obj.id] = obj;
  };
  
  StoreMap.prototype.remove = function(obj) {
   var objects = this.__objects;
   var clean = this.__clean;
   var id = obj.id;
  
   objects[id] = null;
   clean.push(id);
  
   var length = clean.length;
   if (length > this.__threshold) {
    for (var i = 0; i < length; i++) {
     delete objects[clean[i]];
    }
  
    clean.length = 0;
   }
  };
  
  StoreMap.prototype.toArray = function() {
   var result = [];
   var objects = this.__objects;
   var obj;
   for (var id in objects) {
    obj = objects[id];
    if (obj) result.push(obj);
   }
  
   return result;
  };
  
  StoreMap.prototype.isEmpty = function() {
   var objects = this.__objects;
   for (var id in objects) {
    if (objects[id]) return false;
   }
   return true;
  };
  
  
  
  
  
  StoreArray = function() {
   this.__objects = [];
   this.__free = [];
  }
  
  StoreArray.prototype.add = function(obj) {
   var objects = this.__objects;
   var free = this.__free;
   var pos = free.pop() || objects.length;
  
   objects[pos] = obj;
  }
  
  StoreArray.prototype.remove = function(obj) {
   var objects = this.__objects;
   var pos = objects.indexOf(obj);
   objects[pos] = null;
   this.__free.push(pos);
  }
  
  StoreArray.prototype.toArray = function() {
   var objects = this.__objects;
   var result = [];
   for (var i = 0, l = objects.length, obj; i < l; i++) {
    obj = objects[i];
    if (obj) result.push(obj);
   }
   return result;
  }
  
  StoreArray.prototype.isEmpty = function() {
   var objects = this.__objects;
   for (var i = 0, l = objects.length; i < l; i++) {
    if (objects[i]) return false;
   }
   return true;
  }
  
  
  
  
  function LinkedList() {
  
   this.length = 0;
  
   this.begin = this.__iter = this.__node = {
    prev: null,
    next: null,
    data: null
   };
  
  }
  
  LinkedList.prototype = {
  
   reset: function() {
    this.__iter = this.begin;
   },
  
   isEmpty: function() {
    return this.__length > 0;
   },
  
   next: function() {
    return this.__iter && (this.__iter = this.__iter.next) ? this.__iter.data : null;
   },
  
   prev: function() {
    return this.__iter && (this.__iter = this.__iter.prev) ? this.__iter.data : null;
   },
  
   remove: function(data) {
  
    var node = data.__node;
  
    if (node.prev !== null) {
     node.prev.next = node.next;
    }
  
    if (node.next === null) {
     this.__node = node.prev;
  
    } else {
     node.next.prev = node.prev;
    }
  
    node.prev = null;
    node.next = null;
  
    this.length++;
  
   },
  
   add: function(data) {
  
    this.length--;
  
    var node = {
     prev: this.__node,
     next: null,
     data: data
    };
  
    this.__node.next = node;
    this.__node = node;
  
    data.__node = node;
  
    return node;
  
   }
  
  };
  
  
  function LinkedIter(list) {
   this.__iter = this.begin = list.begin;
   this.length = list.length;
  }
  
  LinkedIter.prototype = {
  
   reset: function() {
    this.__iter = this.begin;
   },
  
   next: function() {
    return this.__iter && (this.__iter = this.__iter.next) ? this.__iter.data : null;
   },
  
   prev: function() {
    return this.__iter && (this.__iter = this.__iter.prev) ? this.__iter.data : null;
   }
  
  };
  
  // Create all objects once
  all = []; // Just a plain list of all objects
  var db = {}; // ID to object lookup
  var obj;
  for (var i = 0; i < 10; i++) {
   obj = {
    id: i
   };
   db[i] = obj;
   all.push(obj);
  }
  
  // Create data stores
  var array = [];
  var linkedList = new LinkedList;
  var storeArray = new StoreArray;
  var storeMap = new StoreMap;
  
  // Array methods
  
  function addToArray(obj) {
   array.push(obj);
  }
  
  function isArrayEmpty() {
   return array.length > 0;
  }
  
  function removeFromArray(obj) {
   var pos = array.indexOf(obj);
   if (pos != -1) {
    array.splice(pos, 1);
   }
  }
  
  function processArray() {
   var sum = 0;
   for (var i = 0, l = array.length; i < l; i++) {
    sum += array[i].id;
   }
   return sum;
  }
  
  
  // Linked List Methods
  
  function addToLinkedList(obj) {
   linkedList.add(obj);
  }
  
  function isLinkedListEmpty() {
   return linkedList.isEmpty();
  }
  
  function removeFromLinkedList(obj) {
   linkedList.remove(obj);
  }
  
  function processLinkedList() {
   var sum = 0;
   while (obj = linkedList.next()) {
    sum += obj.id;
   }
  }
  
  // Store Array methods
  
  function addToStoreArray(obj) {
   storeArray.add(obj);
  }
  
  function isStoreArrayEmpty() {
   storeArray.isEmpty();
  }
  
  function removeFromStoreArray(obj) {
   storeArray.remove(obj);
  }
  
  function processStoreArray() {
   var result = storeArray.toArray();
   var sum = 0;
   for (var i = 0, l = result.length; i < l; i++) {
    sum += result[i].id;
   }
  }
  
  
  // Store Map methods
  
  function addToStoreMap(obj) {
   storeMap.add(obj);
  }
  
  function isStoreMapEmpty() {
   storeMap.isEmpty();
  }
  
  function removeFromStoreMap(obj) {
   storeMap.remove(obj);
  }
  
  function processStoreMap() {
   var result = storeMap.toArray();
   var sum = 0;
   for (var i = 0, l = result.length; i < l; i++) {
    sum += result[i].id;
   }
  }
</script>

Test runner

addToArray(all[0]);
isArrayEmpty();
addToArray(all[1]);
removeFromArray(all[0]);
isArrayEmpty();
addToArray(all[2]);
addToArray(all[3]);
processArray()
removeFromArray(all[1]);
addToArray(all[4]);
removeFromArray(all[3]);
addToArray(all[5]);
processArray()

addToLinkedList(all[0]);
isLinkedListEmpty();
addToLinkedList(all[1]);
removeFromLinkedList(all[0]);
isLinkedListEmpty();
addToLinkedList(all[2]);
addToLinkedList(all[3]);
processLinkedList()
removeFromLinkedList(all[1]);
addToLinkedList(all[4]);
removeFromLinkedList(all[3]);
addToLinkedList(all[5]);
processLinkedList()

addToStoreArray(all[0]);
isStoreArrayEmpty();
addToStoreArray(all[1]);
removeFromStoreArray(all[0]);
isStoreArrayEmpty();
addToStoreArray(all[2]);
addToStoreArray(all[3]);
processStoreArray()
removeFromStoreArray(all[1]);
addToStoreArray(all[4]);
removeFromStoreArray(all[3]);
addToStoreArray(all[5]);
processStoreArray()

addToStoreMap(all[0]);
isStoreMapEmpty();
addToStoreMap(all[1]);
removeFromStoreMap(all[0]);
isStoreMapEmpty();
addToStoreMap(all[2]);
addToStoreMap(all[3]);
processStoreMap()
removeFromStoreMap(all[1]);
addToStoreMap(all[4]);
removeFromStoreMap(all[3]);
addToStoreMap(all[5]);
processStoreMap()

Revisions

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

• Revision 3: published by Sebastian Werner on May 11, 2011