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

What you want is something like a plain array but what you don't want is to be shifting the array contents back and forth, as those are linear operations. Just keep your own index values for the start and end of the circular buffer. — Pointy
– Pointy, Commented Nov 24, 2016 at 15:01
Careful: &(n-1) is not the same as %n unless n is a power of 2. — jmrk
– jmrk, Commented Jan 19, 2017 at 12:23

user835611 · Accepted Answer · 2016-11-24 18:57:13Z

1

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

answered Nov 24, 2016 at 18:57

user835611

2,5612 gold badges24 silver badges31 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

jmrk Over a year ago

Minor correction: Push is fast. Shift is slow. Something index-based like the suggested CBuf implementation is the way to go (but beware of overflow!).

Collectives™ on Stack Overflow

Javascript circular buffer queue implementation as a "FIFO queue"

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related