Comparison of queue implementations

JavaScript performance comparison

Revision 4 of this test case created by Nebojsa Sabovic

Info

Comparison of a few ways to implement a buffer (FIFO queue).

http://safalra.com/web-design/javascript/queues/Queue.js Vs Array push/shift Vs two arrays Vs linked list

Preparation code

<script src="http://safalra.com/web-design/javascript/queues/Queue.js">
</script>
<script>
  Benchmark.prototype.setup = function() {
    var workingSize = 10;
    var iterations = 100000;
  };
</script>

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in unknown unknown
Test Ops/sec
Array
 
var i;
var a = [];

for (i = 0; i <= workingSize; i++) {
  a.push(i);
}

for (i = 0; i <= iterations; i++) {
  a.shift();
  a.push(i);
}
 pending…
Queue
 
var i;
var q = new Queue();

for (i = 0; i < workingSize; i++) {
  q.enqueue(i);
}

for (i = 0; i < iterations; i++) {
  q.dequeue();
  q.enqueue(i);
}
 pending…
Two Arrays
 
var i;
var inbox = [];
var outbox = [];

function enq(i) {
  inbox.push(i);
}

function deq() {
  if (outbox.length === 0) {
    while (inbox.length !== 0) {
      outbox.push(inbox.pop());
    }
  }
  return outbox.pop();
}

for (i = 0; i < workingSize; i++) {
  enq(i);
}

for (i = 0; i < iterations; i++) {
  deq();
  enq(i);
}
 pending…
Linked list
 
var head;
var tail;

function enq(i) {
  tail = tail ? tail.next = {value: i} : head = {value: i};
}

function deq() {
  var value = head ? head.value : undefined;
  head = head == tail ? (tail = undefined) : head.next;
  return undefined;
}

for (i = 0; i < workingSize; i++) {
  enq(i);
}

for (i = 0; i < iterations; i++) {
  deq();
  enq(i);
}
 pending…
Two arrays, tweaked
 
var i;
var inbox = [];
var outbox = [];

function enq(i) {
  inbox.push(i);
}

function deq() {
  if (outbox.length === 0) {
   var t = outbox;
   outbox = inbox.reverse();
   inbox = t;
  }
  return outbox.pop();
}

for (i = 0; i < workingSize; i++) {
  enq(i);
}

for (i = 0; i < iterations; i++) {
  deq();
  enq(i);
}
 pending…
Two arrays, no swap
 
var i;
var inbox = [];
var outbox = [];

function enq(i) {
  inbox.push(i);
}

function deq() {
  if (outbox.length === 0) {
   outbox = inbox.reverse();
   inbox = [];
  }
  return outbox.pop();
}

for (i = 0; i < workingSize; i++) {
  enq(i);
}

for (i = 0; i < iterations; i++) {
  deq();
  enq(i);
}
 pending…
fasterQueue
 
function fastQueue(){
  this.tail = [];
  this.head = Array.prototype.slice.call(arguments);
  this.offset = 0;
};

fastQueue.prototype.shift = function shift() {
  if (this.offset === this.head.length) {
    var tmp = this.head;
    tmp.length = 0;
    this.head = this.tail;
    this.tail = tmp;
    this.offset = 0;
    if (this.head.length === 0) return;
  }
  return this.head[this.offset++];
};

fastQueue.prototype.push = function push(item) {
  var ret = this.tail.push(item);
  var self = this;
  
  return ret;
};

var i;
var q = new fastQueue();

for (i = 0; i < workingSize; i++) {
  q.push(i);
}

for (i = 0; i < iterations; i++) {
  q.shift();
  q.push(i);
}
 pending…
queue with index
 
var list = [];
var idx = 0;
var MIN = 100;

function enq(e) {
  list.push(e);
}

function deq() {
  var val = list[idx];
  var len = list.length / 2;
  if (idx > len && idx > MIN) {
    idx -= len;
    list.splice(0, len);
  }
  return val;
}

for (i = 0; i < workingSize; i++) {
  enq(i);
}

for (i = 0; i < iterations; i++) {
  deq();
  enq(i);
}
 pending…

Compare results of other browsers

Revisions

You can edit these tests or add even more tests to this page by appending /edit to the URL. Here’s a list of current revisions for this page:

0 comments

Add a comment