Friday, March 30, 2012

javascript circular buffers

A while back I was introduced to Circular Buffers and the idea intrigued me. The simplest implementation in JavaScript would be to just push() and pop() to/from an array, but that isn't good for memory or garbage collection times. So I wrote an implementation that uses pointers and a fixed size array. It has a limited API at the moment, but works much the same as the native Array(). First the code, then I'll give some examples (it's also available on github):


function CBuffer() {
    // handle cases where "new" keyword wasn't used
    if (!(this instanceof CBuffer)) {
        if (arguments.length > 1 || typeof arguments[0] !== 'number') {
            return CBuffer.apply(new CBuffer(), arguments);
        } else {
            return new CBuffer(arguments[0]);
        }
    }
    // this is the same in either scenario
    this.size = this.start = 0;
    // build CBuffer based on passed arguments
    if (arguments.length > 1 || typeof arguments[0] !== 'number') {
        this.data = new Array(arguments.length);
        this.end = (this.length = arguments.length) - 1;
        this.push.apply(this, arguments);
    } else {
        this.data = new Array(arguments[0]);
        this.end = (this.length = arguments[0]) - 1;
    }
    return this;
}

CBuffer.prototype = {
    // push item to the end
    push : function() {
        var i = 0;
        // push items to the end, wrapping and erasing existing items
        // using arguments variable directly to reduce gc footprint
        for (; i < arguments.length; i++) {
            this.data[(this.end + i + 1) % this.length ] = arguments[i];
        }
        // recalculate size
        if (this.size < this.length) {
            if (this.size + i > this.length) this.size = this.length;
            else this.size += i;
        }
        // recalculate end
        this.end = (this.end + i) % this.length;
        // recalculate start
        this.start = this.end - this.size + 1;
        if (this.start < 0) this.start += this.length;
        // return number current number of items in CBuffer
        return this.size;
    },
    // shift first item
    shift : function() {
        var item;
        // check if there are any items in CBuff
        if (this.size === 0) return undefined;
        // store first item for return
        item = this.data[ this.start ];
        // delete first item from memory
        delete this.data[ this.start ];
        // recalculate start of CBuff
        this.start = (this.start + 1) % this.length;
        // decrement size
        this.size--;
        return item;
    },
    first : function() {
        return this.data[ this.start ];
    },
    last : function() {
        return this.data[ this.end ];
    },
    idx : function(arg) {
        return this.data[(this.start + arg) % this.length ];
    }
};

Let's start with instantiating a new CBuffer() object:


// length of 5, no items in buffer
new CBuffer(5);
// length 2, items [1, 2] are in buffer
new CBuffer(1, 2);
// length 1, item ['awesome'] is in buffer
new CBuffer('awesome');

When a new buffer has been created the length is unchangeable. While it does offer a performance improvement, the key is to minimize Garbage Collection as much as possible.

Let's create a new circular buffer and push some stuff to the end:


// length of 5, no items in buffer
var newbuff = new CBuffer(5);
newbuff.push('i', 'am', 'a', 'buffer'); // ~= ['i', 'am', 'a', 'buffer',]

If we want to just grab the first item in the buffer, use .first(). But if the item should be removed, returned and destroyed used .shift().


// length of 5, no items in buffer
newbuff.first() // returns 'i'
newbuff.shift() // returns 'i'
// newbuff: [, 'am', 'a', 'buffer',]

The start pointer has now moved forward and the original first item has been returned and destroyed. So let's continue to push stuff on:


// length of 5, no items in buffer
newbuff.push('want', 'to', 'play');
// output: ['to', 'play', 'a', 'buffer', 'want']

Say what?! Where did my stuff go? Well, it was truncated. When more items are pushed to the buffer than it has spots for it starts over. From here let's shift of the latest data:


// length of 5, no items in buffer
newbuff.shift() // returns 'a'
// newbuff: ['to', 'play', , 'buffer', 'want']

I think this shows the general idea of how to use this little library. Good luck with it.