Comparison of queue implementations
JavaScript performance comparison
Revision 3 of this test case created
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… |
Compare results of other browsers
0 comments