A tale of Caches

test.js

// 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;
};



// 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;
}

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

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


LRUCacheByLinkList.prototype.detachElement = 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 --;
    return entry;

};

LRUCacheByLinkList.prototype.removeElement = function(entry){
    this.detachElement(entry);
    delete this._keyVals[entry._hash];
    return entry._datum;
};

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

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

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


LRUCacheByLinkList.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 ++;
};

LRUCacheByLinkList.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);

};

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

LRUCacheByLinkList.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;
};

// Remove the element
// and push it from the front
// so least recently used objects will end up at the end.
LRUCacheByLinkList.prototype.promote = function(el){
    // No need to promote
    if( el === this.top ){
        return;
    }

    this.detachElement(el);
    this.insertAtTop(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 LRUCacheByLinkList(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].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.reset();

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

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

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

}


FullTest();

zMy results.txt

Metarains-Mac-mini:lib abhishek$ node LRUCache.js
lets run benchmarks
Each will be spawned with 100 element cache
And exhaustive benchmarking will occur for both
======================================================
Beginning for lazy implementation
testing for just pushes
Benchmark complete it did insertions  493301  and fetched  0 in 969 ms
The length after this test is  100
testing for just fetches
Benchmark complete it did insertions  0  and fetched  500341 in 52 ms
The length after this test is  100
testing for everything
Benchmark complete it did insertions  492812  and fetched  496643 in 1019 ms
The length after this test is  100
======================================================
======================================================
Beginning for LRUCacheArray
testing for just pushes
Benchmark complete it did insertions  489142  and fetched  0 in 647 ms
The length after this test is  100
testing for just fetches
Benchmark complete it did insertions  0  and fetched  493951 in 416 ms
The length after this test is  100
testing for everything
Benchmark complete it did insertions  497652  and fetched  495526 in 926 ms
The length after this test is  100
======================================================
======================================================
Beginning for LRUCacheByLinkList
testing for just pushes
Benchmark complete it did insertions  496553  and fetched  0 in 484 ms
The length after this test is  100
testing for just fetches
Benchmark complete it did insertions  0  and fetched  494704 in 60 ms
The length after this test is  100
testing for everything
Benchmark complete it did insertions  497629  and fetched  497878 in 623 ms
The length after this test is  100
======================================================

And our winner is ... yes you guessed it right the Link List !