Run results for: Queue comparison

Run details:

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/146.0.0.0 Safari/537.36

Browser: Chrome 146

Operating system: Mac OS X 10.15.7

Device Platform: Desktop

Date tested: 5 months ago

Benchmark engine: Benchmark.js

array non-destructive

1.4M/s

queue

844K/s

array

601K/s

queue2

122K/s

View exact numbers

Test name	Executions per second
✓ array non-destructive	1,426,249 Ops/sec
queue	843,726 Ops/sec
array	600,876 Ops/sec
queue2	122,066 Ops/sec

Script Preparation code:

function QueueItem(value) {
  this.value = value;
  this.next  = void 0;
}

function Queue() {
  this.first = void 0;
  this.last  = void 0;
}
Queue.prototype.enqueue = function (value) {
  var wasEmpty = !this.first;
  var item = new QueueItem(value);
  if (wasEmpty) {
    this.first = item;
  } else {
    this.last.next = item;
  }
  this.last = item;
  return wasEmpty;
};
Queue.prototype.dequeue = function () {
  var first = this.first;
  if (first) {
    this.first = first.next;
  }
  if (first === this.last) {
    this.last = void 0;
  }
  return first.value;  
};
Queue.prototype.isEmpty = function () {
  return !this.first;
};

var a = [];
var q = new Queue();


class Queue2 {
  constructor() {
    this.list = new Set();
  }

  enqueue(value) {
    this.list.add({value});
  }

  dequeue() {
    for (let item of this.list) {
      this.list.delete(item);
      return item.value;
    }
  }

  isEmpty() {
    return this.list.size === 0;
  }
}

var q2 = new Queue2();

Tests:

array
for (var i = 0; i < 100; i++) { a.push(i); } while (a.length) { var x = a.shift(); }
queue
for (var i = 0; i < 100; i++) { q.enqueue(i); } while (!q.isEmpty()) { var x = q.dequeue(); }
array non-destructive
for (var i = 0; i < 100; i++) { a.push(i); } for (var i = 0, len = a.length; i < len; i++) { var x = a[i]; } a = [];
queue2
for (var i = 0; i < 100; i++) { q2.enqueue(i); } while (!q2.isEmpty()) { var x = q2.dequeue(); }