Getting something out of a javascript hash (v4)

Revision 4 of this benchmark created on


Description

Performance of finding something in a javascript hash vs object vs array indexOf lookup

Preparation HTML

<script>
  var CappedObject;
  var __hasProp = Object.prototype.hasOwnProperty,
      __extends = function(child, parent) {
    for (var key in parent) {
     if (__hasProp.call(parent, key)) child[key] = parent[key];
    }
  
    function ctor() {
     this.constructor = child;
    }
    ctor.prototype = parent.prototype;
    child.prototype = new ctor;
    child.__super__ = parent.prototype;
    return child;
      };
  CappedObject = (function() {
   __extends(CappedObject, Array);
  
   function CappedObject(max) {
    this.max = max;
    this.Collection = {};
    this._byFIFO = [];
    this._getLast = function() {
     return this._byFIFO.pop();
    };
   }
   CappedObject.prototype.addId = function(obj) {
    var pop;
    this._byFIFO.unshift(obj);
    this.Collection[obj._id] = obj;
    if (this.max && this._byFIFO.length > this.max) {
     pop = this._getLast();
     return delete this.Collection[pop._id];
    }
   };
   CappedObject.prototype.getId = function(id) {
    return this.Collection[id];
   };
   return CappedObject;
  })();
  var CappedCollection;
  var __hasProp = Object.prototype.hasOwnProperty,
      __extends = function(child, parent) {
    for (var key in parent) {
     if (__hasProp.call(parent, key)) child[key] = parent[key];
    }
  
    function ctor() {
     this.constructor = child;
    }
    ctor.prototype = parent.prototype;
    child.prototype = new ctor;
    child.__super__ = parent.prototype;
    return child;
      },
      __bind = function(fn, me) {
    return function() {
     return fn.apply(me, arguments);
    };
      };
  CappedCollection = (function() {
   __extends(CappedCollection, Array);
  
   function CappedCollection(max, key) {
    this.max = max;
    this.key = key != null ? key : '_id';
    this.Collection = [];
    this._byFIFO = [];
    this._getLast = function() {
     return this._byFIFO.pop();
    };
    this.comparator = __bind(function(value) {
     return value._id;
    }, this);
   }
   CappedCollection.prototype.addId = function(obj) {
    var index, lastIndex;
    this._byFIFO.unshift(obj);
    index = this._sortedIndex(this.Collection, obj, this.comparator);
    this.Collection.splice(index, 0, obj);
    if (this.max && this.Collection.length > this.max) {
     lastIndex = this._sortedIndex(this.Collection, this._getLast(), this.comparator);
     return this.Collection.splice(lastIndex, 1);
    }
   };
   CappedCollection.prototype.getId = function(id) {
    var index;
    index = this._nearestObjAtIndex(this.Collection, id, this.comparator);
    if (this.Collection[index][this.key] === id) {
     return this.Collection[index];
    } else {
     return;
    }
   };
   CappedCollection.prototype._sortedIndex = function(array, obj, comparator) {
    var high, low, mid;
    comparator || (comparator = function(value) {
     return value;
    });
    low = 0;
    high = array.length;
    while (low < high) {
     mid = (low + high) >> 1;
     if (comparator(array[mid]) < comparator(obj)) {
      low = mid + 1;
     } else {
      high = mid;
     }
    }
    return low;
   };
   CappedCollection.prototype._nearestObjAtIndex = function(array, id, comparator) {
    var high, low, mid;
    comparator || (comparator = function(value) {
     return value;
    });
    low = 0;
    high = array.length;
    while (low < high) {
     mid = (low + high) >> 1;
     if (comparator(array[mid]) < id) {
      low = mid + 1;
     } else {
      high = mid;
     }
    }
    return low;
   };
   return CappedCollection;
  })();
  x = new CappedCollection()
  y = {}, z = [];
  w = [];
  v = new CappedObject()
  for (var _i = 0; _i < 1000; _i++) {
   o = new Object({
    '_id': _i
   })
   x.addId(o)
   v.addId(o)
   y[_i] = o
   z.push(_i)
   w.push(o)
  }
</script>

Test runner

Ready to run.

Testing in
TestOps/sec
Javascript Hash Collection
var r = x.getId(700)
ready
Object
var r = y['700']
ready
Array
var r = z.indexOf(700)
ready
Array of Objects
var i;
for (i = 0; i < 100; i++) {
 if (w[i]._id == 700) break;
}
r = i
ready
Javascript Collection Object
var r = v.getId(700)
ready
Object of Objects
var r, s;
for(obj in y) {
  if(y[obj]._id == 700) {
    s = y[obj];
    break;
  }
}
r = s;
ready

Revisions

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