LRU tests

/**
 * A doubly linked list-based Least Recently Used (LRU) cache. Will keep most
 * recently used items while discarding least recently used items when its limit
 * is reached.
 *
 * Licensed under MIT. Copyright (c) 2010 Rasmus Andersson <http://hunch.se/>
 * See README.md for details.
 *
 * Illustration of the design:
 *
 *       entry             entry             entry             entry
 *       ______            ______            ______            ______
 *      | head |.newer => |      |.newer => |      |.newer => | tail |
 *      |  A   |          |  B   |          |  C   |          |  D   |
 *      |______| <= older.|______| <= older.|______| <= older.|______|
 *
 *  removed  <--  <--  <--  <--  <--  <--  <--  <--  <--  <--  <--  added
 */
function LRUCache (limit) {
  // Current size of the cache. (Read-only).
  this.size = 0;
  // Maximum number of items this cache can hold.
  this.limit = limit;
  this._keymap = {};
}

/**
 * Put <value> into the cache associated with <key>. Returns the entry which was
 * removed to make room for the new entry. Otherwise undefined is returned
 * (i.e. if there was enough room already).
 */
LRUCache.prototype.put = function(key, value) {
  var entry = {key:key, value:value};
  // Note: No protection agains replacing, and thus orphan entries. By design.
  this._keymap[key] = entry;
  if (this.tail) {
    // link previous tail to the new tail (entry)
    this.tail.newer = entry;
    entry.older = this.tail;
  } else {
    // we're first in -- yay
    this.head = entry;
  }
  // add new entry to the end of the linked list -- it's now the freshest entry.
  this.tail = entry;
  if (this.size === this.limit) {
    // we hit the limit -- remove the head
    return this.shift();
  } else {
    // increase the size counter
    this.size++;
  }
};

/**
 * Purge the least recently used (oldest) entry from the cache. Returns the
 * removed entry or undefined if the cache was empty.
 *
 * If you need to perform any form of finalization of purged items, this is a
 * good place to do it. Simply override/replace this function:
 *
 *   var c = new LRUCache(123);
 *   c.shift = function() {
 *     var entry = LRUCache.prototype.shift.call(this);
 *     doSomethingWith(entry);
 *     return entry;
 *   }
 */
LRUCache.prototype.shift = function() {
  // todo: handle special case when limit == 1
  var entry = this.head;
  if (entry) {
    if (this.head.newer) {
      this.head = this.head.newer;
      this.head.older = undefined;
    } else {
      this.head = undefined;
    }
    // Remove last strong reference to <entry> and remove links from the purged
    // entry being returned:
    entry.newer = entry.older = undefined;
    // delete is slow, but we need to do this to avoid uncontrollable growth:
    delete this._keymap[entry.key];
  }
  return entry;
};

/**
 * Get and register recent use of <key>. Returns the value associated with <key>
 * or undefined if not in cache.
 */
LRUCache.prototype.get = function(key, returnEntry) {
  // First, find our cache entry
  var entry = this._keymap[key];
  if (entry === undefined) return; // Not cached. Sorry.
  // As <key> was found in the cache, register it as being requested recently
  if (entry === this.tail) {
    // Already the most recenlty used entry, so no need to update the list
    return returnEntry ? entry : entry.value;
  }
  // HEAD--------------TAIL
  //   <.older   .newer>
  //  <--- add direction --
  //   A  B  C  <D>  E
  if (entry.newer) {
    if (entry === this.head)
      this.head = entry.newer;
    entry.newer.older = entry.older; // C <-- E.
  }
  if (entry.older)
    entry.older.newer = entry.newer; // C. --> E
  entry.newer = undefined; // D --x
  entry.older = this.tail; // D. --> E
  if (this.tail)
    this.tail.newer = entry; // E. <-- D
  this.tail = entry;
  return returnEntry ? entry : entry.value;
};

// ----------------------------------------------------------------------------
// Following code is optional and can be removed without breaking the core
// functionality.

/**
 * Check if <key> is in the cache without registering recent use. Feasible if
 * you do not want to chage the state of the cache, but only "peek" at it.
 * Returns the entry associated with <key> if found, or undefined if not found.
 */
LRUCache.prototype.find = function(key) {
  return this._keymap[key];
};

/**
 * Update the value of entry with <key>. Returns the old value, or undefined if
 * entry was not in the cache.
 */
LRUCache.prototype.set = function(key, value) {
  var oldvalue, entry = this.get(key, true);
  if (entry) {
    oldvalue = entry.value;
    entry.value = value;
  } else {
    oldvalue = this.put(key, value);
    if (oldvalue) oldvalue = oldvalue.value;
  }
  return oldvalue;
};

/**
 * Remove entry <key> from cache and return its value. Returns undefined if not
 * found.
 */
LRUCache.prototype.remove = function(key) {
  var entry = this._keymap[key];
  if (!entry) return;
  delete this._keymap[entry.key]; // need to do delete unfortunately
  if (entry.newer && entry.older) {
    // relink the older entry with the newer entry
    entry.older.newer = entry.newer;
    entry.newer.older = entry.older;
  } else if (entry.newer) {
    // remove the link to us
    entry.newer.older = undefined;
    // link the newer entry to head
    this.head = entry.newer;
  } else if (entry.older) {
    // remove the link to us
    entry.older.newer = undefined;
    // link the newer entry to head
    this.tail = entry.older;
  } else {// if(entry.older === undefined && entry.newer === undefined) {
    this.head = this.tail = undefined;
  }

  this.size--;
  return entry.value;
};

/** Removes all entries */
LRUCache.prototype.removeAll = function() {
  // This should be safe, as we never expose strong refrences to the outside
  this.head = this.tail = undefined;
  this.size = 0;
  this._keymap = {};
};

/**
 * Return an array containing all keys of entries stored in the cache object, in
 * arbitrary order.
 */
if (typeof Object.keys === 'function') {
  LRUCache.prototype.keys = function() { return Object.keys(this._keymap); };
} else {
  LRUCache.prototype.keys = function() {
    var keys = [];
    for (var k in this._keymap) keys.push(k);
    return keys;
  };
}

/**
 * Call `fun` for each entry. Starting with the newest entry if `desc` is a true
 * value, otherwise starts with the oldest (head) enrty and moves towards the
 * tail.
 *
 * `fun` is called with 3 arguments in the context `context`:
 *   `fun.call(context, Object key, Object value, LRUCache self)`
 */
LRUCache.prototype.forEach = function(fun, context, desc) {
  var entry;
  if (context === true) { desc = true; context = undefined; }
  else if (typeof context !== 'object') context = this;
  if (desc) {
    entry = this.tail;
    while (entry) {
      fun.call(context, entry.key, entry.value, this);
      entry = entry.older;
    }
  } else {
    entry = this.head;
    while (entry) {
      fun.call(context, entry.key, entry.value, this);
      entry = entry.newer;
    }
  }
};

/** Returns a JSON (array) representation */
LRUCache.prototype.toJSON = function() {
  var s = [], entry = this.head;
  while (entry) {
    s.push({key:entry.key.toJSON(), value:entry.value.toJSON()});
    entry = entry.newer;
  }
  return s;
};

/** Returns a String representation */
LRUCache.prototype.toString = function() {
  var s = '', entry = this.head;
  while (entry) {
    s += String(entry.key)+':'+entry.value;
    entry = entry.newer;
    if (entry)
      s += ' < ';
  }
  return s;
};

// Export ourselves
if (typeof this === 'object') this.LRUCache = LRUCache;

// Lazy instance pool uncle.

var _instancePool = {
  length: 0,
  maxLength: 100,
  // Keep all the nodes in memory.
  elements: {

  },
  reset: function(){
    this.elements =  {};
    this.length = 0;
  },
  // Push with 0 frequency
  set: function (hash, data) {

    if( this.length >= 100){
        this.popLeastUsed();
    }

    this.length++;
    this.elements[hash] = {
      hash: hash, // Helps identifying
      freq: 0,
      data: data
    };
  },

  get: function (path) {
    var element = this.elements[path];

    if( element ){
      element.freq++;
      return element.data;
    }

    return null;
  },

  // used to explicitely remove the path
  removeElement: function (path) {
    // Now almighty GC can claim this soul
    var element = this.elements[path];
    delete this.elements[path];
    this.length--;
    return element;
  },

  _reduceLeastUsed: function (least, currentHash) {
    var current = _instancePool.elements[currentHash];

    if( least.freq > current.freq ){
      return current;
    }

    return least;
  },

  popLeastUsed: function () {
    var reducer = _instancePool._reduceLeastUsed;
    var minUsed = Object.keys(this.elements).reduce(reducer, { freq: Infinity });

    if( minUsed.hash ){
      return this.removeElement(minUsed.hash);
    }

    return null;
  }
};


// Book-keeping through array.
function LRUCacheArray(maxLength){
    // Smart and simple LRU cache with ... yes memory penaalty
    this.maxLength = maxLength || 300;
    this.reset();
}

LRUCacheArray.prototype.reset = function() {
    // The cachee
    this._cache = {};
    // Array of hashes;
    this._usageList = [];
    this.length = 0;
};

LRUCacheArray.prototype.get = function(key){
    var el = this._cache[key];
    var keyIndex = -1;
    if( el !== undefined ){
        keyIndex = this._usageList.indexOf(key);
        this._usageList.splice(keyIndex, 1);
        this._usageList.push(key);
        return el;
    }
};

LRUCacheArray.prototype.set = function(key, value){
    if( this.length === this.maxLength ){
        var top = this._usageList[0];
        this._usageList = this._usageList.slice(1);
        this.removeElement(top);
    }

    this._cache[key] = value;
    this._usageList.push(key);
    this.length ++;
};

LRUCacheArray.prototype.removeElement = function(key){
    var el = this._cache[key];
    delete this._cache[key];
    this.length --;
    return el;
};

// My favorite so far.
function LRULinkListTrue(length){
    this.maxLength = length;
    this.reset();
}

LRULinkListTrue.prototype.reset = function(){
    this.length = 0;
    this._top = null;
    this._bottom = null;
    this._keyVals = {};
};


LRULinkListTrue.prototype.removeElement = function(entry){
    var prev = entry._prev;
    var next = entry._next;

    if( prev !== null ){
        prev._next = next;
    }

    if( next !== null ){
        next._prev = prev;
    }

    if( entry === this._top ){
        this._top = next;
    }

    if( entry === this._bottom ){
        this._bottom = prev;
    }

    this.length --;
    delete this._keyVals[entry._hash];
    return entry._datum;
};

LRULinkListTrue.prototype.insertAtTop = function(value){
    if( this._top !== null ){
        this._top._prev = value;
        value._next = this._top;
    }

    if( this._bottom === null ){
        this._bottom = value;
    }

    this._top = value;
    this.length++;
};


LRULinkListTrue.prototype.insertAtBottom = function(value){
    if( this._bottom !== null ){
        this._bottom._next = value;
        value._prev = this._bottom;
    }

    if( this._top === null ){
        this._top = value;
    }

    this._bottom = value;
    this.length ++;
};

LRULinkListTrue.prototype.set = function(key, value){
    var existinEl = this._keyVals[key];

    // Handling for dups
    if( existinEl ){

        if( existinEl._datum === value ){
            // Don't change anything
            return;
        }

        // hardest part of code.
        this.removeElement(existinEl);

    }

    value = new LRULinkListEntry(key,value);
    this._keyVals[key] = value;

    // Most likely it will only be equal
    // to purge the least used


    if( this.length >= this.maxLength ){
        this.removeLeastUsed();
    }

    this.insertAtTop(value);

};

LRULinkListTrue.prototype.removeLeastUsed = function(){
    // Buhahah this is easy.
    return this.removeElement(this._bottom);
};

LRULinkListTrue.prototype.get = function(key){
    var value = this._keyVals[key];

    if( value !== undefined ){
        // Promote this as it got used
        this.promote(value);
        return value._datum;
    }

    return null;
};

// Why not plain js objects ?
// because v8 will sniff this
// and predict this.

function LRULinkListEntry(hash, obj){
   this._hash = hash;
   this._datum = obj;
   this._prev = null;
   this._next = null;
}

// Remove the element
// and push it from the front
// so least recently used objects will end up at the end.
LRULinkListTrue.prototype.promote = function(el){
    this.removeElement(el);
    this.insertAtTop(el);
};


// My favorite so far.
// Slightly more optimized for our case
// in ourcase the first come objects
// will most likely be bottom layers
// and these usual cases don't need to be re-drawn
// (Assumption)
// plus we also have an api for explicit removal
// so this should be the best way for us

function LRULinkList(length){
    this.maxLength = length;
    this.reset();
}

LRULinkList.prototype.reset = function(){
    this.length = 0;
    this._top = null;
    this._bottom = null;
    this._keyVals = {};
};


LRULinkList.prototype.removeElement = function(entry){
    var prev = entry._prev;
    var next = entry._next;

    if( prev !== null ){
        prev._next = next;
    }

    if( next !== null ){
        next._prev = prev;
    }

    if( entry === this._top ){
        this._top = next;
    }

    if( entry === this._bottom ){
        this._bottom = prev;
    }

    this.length --;
    delete this._keyVals[entry._hash];
    return entry._datum;
};

LRULinkList.prototype.set = function(key, value){
    var existinEl = this._keyVals[key];

    // Handling for dups
    if( existinEl ){

        if( existinEl._datum === value ){
            // Don't change anything
            return;
        }

        // hardest part of code.
        this.removeElement(existinEl);

    }

    value = new LRULinkListEntry(key,value);
    this._keyVals[key] = value;

    // Most likely it will only be equal
    // to purge the least used


    if( this.length >= this.maxLength ){
        this.removeLeastUsed();
    }

    if( this._bottom !== null ){
        this._bottom._next = value;
        value._prev = this._bottom;
    }

    if( this._top === null ){
        this._top = value;
    }

    this._bottom = value;
    this.length ++;
};

LRULinkList.prototype.removeLeastUsed = function(){
    // Buhahah this is easy.
    return this.removeElement(this._bottom);
};

LRULinkList.prototype.get = function(key){
    var value = this._keyVals[key];

    if( value !== undefined ){
        // Promote this as it got used
        this.promote(value);
        return value._datum;
    }

    return null;
};

// Why not plain js objects ?
// because v8 will sniff this
// and predict this.
function LRULinkListEntry(hash, obj){
   this._hash = hash;
   this._datum = obj;
   this._prev = null;
   this._next = null;
}

LRULinkList.prototype.promote = function(el){
    var temp = el._prev;
    // If no _.prev we are either on top
    // or we aren't a member itself
    if( temp === null ){
        return;
    }


    //                     ->     ->
    // Swap references for [A] -> [B]
    //                     <-     <-
    // such that there may be a pre-a and a pre-b;

    // if temp has a ._prev
    // Move el one forward
    if( temp._prev !== null ){
        temp._prev._next = el;
    }

    // if el has a ._next
    // move temp as ._prev for ._next
    if( el._next !== null ){
        el._next._prev = temp;
    }

    temp._next = el._next;
    el._prev = temp._prev;
    el._next = temp;
    temp._prev = el;

    // if el was the last element
    // set temp as the new last
    if(el === this._bottom){
        this._bottom = temp;
    }

    // If temp is the top of the
    // linkedlist set el as top
    if( temp === this._top ){
        this._top = el;
    }
};


console.log("lets run benchmarks");
console.log("Each will be spawned with 100 element cache");
console.log("And exhaustive benchmarking will occur for both");

var lrull = new LRULinkList(100);
var lrulltrue = new LRULinkListTrue(100);
var lruarr = new LRUCacheArray(100);
var lruc = new LRUCache(100); 


function Bench(impl, testFetches, testPushes){
    var randomInsertions = 0,
        randomFetches = 0;
    var totalInsertions = 0;
    var totalFetches = 0;
    var randomNumber = 0;
    var j, k;

    // Fill the data so that no
    // null is returned
    // Preparing time will not be counted.
    // to keep the benchmark sane.

    randomInsertions = 100;
    for( j = 0; j < randomInsertions; j++ ){
        randomNumber = j;
        impl.set("hello"+randomNumber, "world"+randomNumber);
    }

    // reset the iterator name we-abuse-reused
    randomInsertions = 0;

    var start = Date.now();

    for( var i = 0; i < 10000; i++ ){

        if( testPushes ){

            randomInsertions = ~~(Math.random() * 100);

            for( j = 0; j < randomInsertions; j++ ){
                randomNumber = ~~(Math.random() * 100);
                impl.set("hello"+randomNumber, "world" + Math.random() * Date.now());
            }

        }

        if( testFetches ){
            randomFetches = ~~(Math.random() * 100);

            for( k = 0; k < randomFetches; k++ ){
                randomNumber = ~~(Math.random() * 100);
                impl.get("hello"+ randomNumber);
            }
        }

        totalInsertions += randomInsertions;
        totalFetches += randomFetches;
    }

    var ender = Date.now();

    console.log("Benchmark complete it did insertions ", totalInsertions, " and fetched ", totalFetches, "in" , ender - start, "ms");
}


function FullTest(){



    [_instancePool, lruarr, lrulltrue, lrull, lruc].map(function(impl){

        // Though a simple array with indexes would do here
        // but you know we javascript laz grammers don't like that stuff
        console.log('======================================================');

        if( impl.__proto__.constructor.name !== 'Object' ){
            console.log("Beginning for", impl.__proto__.constructor.name);
        }else{
            console.log("Beginning for lazy implementation");
        }
 		console.log("testing for just pushes");
        Bench(impl, false, true);
        console.log("The length after this test is ", impl.length || impl.size);
        (impl.reset || impl.removeAll)();

        console.log("testing for just fetches");
        Bench(impl, true, false);
        console.log("The length after this test is ", impl.length || impl.size);
        (impl.reset || impl.removeAll)();

        console.log("testing for everything");
        Bench(impl, true, true);
        console.log("The length after this test is ", impl.length || impl.size);


        console.log('======================================================');
    });

}


FullTest();