Queue

Benchmark created on

Description

Compares the performance of different queue implementations

Setup

class ArrayQueue {

  constructor() {
    this.array = [];
  }

  push(element) {
    this.array.push(element);
  }

  shift() {
    return this.array.shift();
  }

}

class LinkedListQueueNode {

  constructor(next, element) {
    this.previous = null;
    this.next = next;
    this.element = element;
  }

}

class LinkedListQueue {

  constructor() {
    this.head = null;
    this.tail = null;
  }

  push(element) {
    const currentTail = this.tail;

    this.tail = new LinkedListQueueNode(currentTail, element);

    if (currentTail !== null) {
      currentTail.previous = this.tail;
    }

    if (this.head === null) {
      this.head = this.tail;
    }
  }

  shift() {
    const currentHead = this.head;

    this.head = this.head.previous;

    if (this.head !== null) {
      this.head.next = null;
    }

    return currentHead.element;
  }

}

function testQueue(queue, initialQueueSize, queueOperationCount) {
  for (let i = 0; i < initialQueueSize; i++) {
    queue.push(new Uint8Array());
  }

  for (let i = 0; i < queueOperationCount; i++) {
    queue.push(new Uint8Array());
    queue.shift();
  }
}

Test runner

Ready to run.

Testing in
TestOps/sec
ArrayQueue [Initial: 0][Ops: 1000]
testQueue(new ArrayQueue(), 0, 1000);
ready
LinkedListQueue [Initial: 0][Ops: 1000]
testQueue(new LinkedListQueue(), 0, 1000);
ready
ArrayQueue [Initial: 0][Ops: 10000]
testQueue(new ArrayQueue(), 0, 10000);
ready
LinkedListQueue [Initial: 0][Ops: 10000]
testQueue(new LinkedListQueue(), 0, 10000);
ready
ArrayQueue [Initial: 0][Ops: 100000]
testQueue(new ArrayQueue(), 0, 100000);
ready
LinkedListQueue [Initial: 0][Ops: 100000]
testQueue(new LinkedListQueue(), 0, 100000);
ready
ArrayQueue [Initial: 1000][Ops: 1000]
testQueue(new ArrayQueue(), 1000, 1000);
ready
LinkedListQueue [Initial: 1000][Ops: 1000]
testQueue(new LinkedListQueue(), 1000, 1000);
ready
ArrayQueue [Initial: 1000][Ops: 10000]
testQueue(new ArrayQueue(), 1000, 10000);
ready
LinkedListQueue [Initial: 1000][Ops: 10000]
testQueue(new LinkedListQueue(), 1000, 10000);
ready
ArrayQueue [Initial: 1000][Ops: 100000]
testQueue(new ArrayQueue(), 1000, 100000);
ready
LinkedListQueue [Initial: 1000][Ops: 100000]
testQueue(new LinkedListQueue(), 1000, 100000);
ready
ArrayQueue [Initial: 10000][Ops: 1000]
testQueue(new ArrayQueue(), 10000, 1000);
ready
LinkedListQueue [Initial: 10000][Ops: 1000]
testQueue(new LinkedListQueue(), 10000, 1000);
ready
ArrayQueue [Initial: 10000][Ops: 10000]
testQueue(new ArrayQueue(), 10000, 10000);
ready
LinkedListQueue [Initial: 10000][Ops: 10000]
testQueue(new LinkedListQueue(), 10000, 10000);
ready
ArrayQueue [Initial: 10000][Ops: 100000]
testQueue(new ArrayQueue(), 10000, 100000);
ready
LinkedListQueue [Initial: 10000][Ops: 100000]
testQueue(new LinkedListQueue(), 10000, 100000);
ready
ArrayQueue [Initial: 100000][Ops: 1000]
testQueue(new ArrayQueue(), 100000, 1000);
ready
LinkedListQueue [Initial: 100000][Ops: 1000]
testQueue(new LinkedListQueue(), 100000, 1000);
ready
ArrayQueue [Initial: 100000][Ops: 10000]
testQueue(new ArrayQueue(), 100000, 10000);
ready
LinkedListQueue [Initial: 100000][Ops: 10000]
testQueue(new LinkedListQueue(), 100000, 10000);
ready
ArrayQueue [Initial: 100000][Ops: 100000]
testQueue(new ArrayQueue(), 100000, 100000);
ready
LinkedListQueue [Initial: 100000][Ops: 100000]
testQueue(new LinkedListQueue(), 100000, 100000);
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.