Javascript circular buffer queue implementation as a "FIFO queue"

Question

Is there a circular buffer version of array? Assuming number of max pushed elements at time is known, do I have to derive my own FIFO queue for performance?

Here is what I tried:

Circular implementation:

function CBuf(n)
{
    var ctrPush=0;
    var ctrPop=0;
    var ab = new ArrayBuffer(n*4);
    var buf = new Uint32Array(ab);

    this.push = function (v) {
        buf[ctrPush%n] = v;
        ctrPush++;
    };


    this.empty = function () {
         return (ctrPush == ctrPop);
    }


    this.pop = function () {
        var tmp = buf[ctrPop%n];
        ctrPop++;
        return tmp;
    };
}

Benchmark simple array:

{
    var t1 = new Date();
    var arr = [];

    for (var j = 0; j < 1000; j++) {
        for (var i = 0; i < 10000; i++) {
            arr.push(i); 
        }
        for (var i = 0; i < 10000; i++) {
            arr.shift();
        }
    }
    var t2 = new Date();

    console.log("array time=" + (t2 - t1));
}

Benchmark circular buffer:

{
    var t1 = new Date();
    var arr = new CBuf(10000);

    for (var j = 0; j < 1000; j++) {
        for (var i = 0; i < 10000; i++) {
            arr.push(i);
        }
        for (var i = 0; i < 10000; i++) {
            if(!arr.empty())
                arr.pop();
        }
    }
    var t2 = new Date();

    console.log("cbuf time="+(t2 - t1));
}

Result:

array time=2749 ms
cbuf time=552 ms (230 if using &(n-1) instead of %n)

For max 70k elements:

array time=19456 ms
cbuf time=3872 ms (1700 if using &(n-1) instead of %n)

they seem to have similar time complexity but array shift is slower in Nodejs. Maybe it check many things like bounds checking and resizing constantly? I need something like a SIMD variable but with n length.

I'm planning on using this on a nodejs inter-server work scheduler queue.

Edit:

Here you can test:

https://jsperf.com/fifo-array-vs-circular-buffer-preallocated

Answer 1

Push and shift are slow. Just use an array index.