Queue (v9)

Revision 9 of this benchmark created on

Description

Compares the performance of different queue implementations

Setup

class ArrayQueue {

  constructor(capacity) {
    if (capacity === undefined) {
      this.array = [];
    } else {
      this.array = new Array(capacity);
    }
  }

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

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

}

class LinkedListQueue {

  constructor() {
    this.head = { previous: undefined };
    this.tail = { next: this.head };
    this.head.previous = this.tail;
  }

  push(element) {
    const newEntry = { previous: this.tail, next: this.tail.next, element: element };
    this.tail.next.previous = newEntry;
    this.tail.next = newEntry;
  }

  shift() {
    const currentHead = this.head.previous;
    if (currentHead === this.tail) {
      throw new Error('Queue is empty');
    }

    this.head.previous = currentHead.previous;
    this.head.previous.next = currentHead.next;

    return currentHead.element;
  }

}

class CircularQueue {

  headIndex = 0;
  tailIndex = 0;
  length = 0;

  constructor(capacity) {
    if (Math.log2(capacity) % 1 !== 0) {
      throw new Error('Capacity must be a power of two');
    }

    this.capacity = capacity;
    this.capacityBitmask = capacity - 1;
    this.array = new Array(capacity);
  }

  push(element) {
    if (this.length >= this.capacity) {
      throw new Error('Capacity exceeded');
    }

    this.array[this.tailIndex] = element;

    this.tailIndex = (this.tailIndex + 1) & this.capacityBitmask;
    this.length++;
  }

  shift() {
    if (this.length <= 0) {
      throw new Error('Queue is empty');
    }

    const element = this.array[this.headIndex];
    this.array[this.headIndex] = undefined;

    this.headIndex = (this.headIndex + 1) & this.capacityBitmask;
    this.length--;

    return element;
  }

}

const QUEUE_ELEMENT = new Uint8Array();

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

  const iterationCount = initialQueueSize + queueOperationCount;
  for (let i = initialQueueSize; i < iterationCount; i++) {
    queue.push(i);
    queue.shift();
  }
}

const INITIAL_QUEUE_SIZE = 127;
const QUEUE_OPERATIONS = 5000;

Test runner

Ready to run.

Testing in
TestOps/sec
ArrayQueue
testQueue(new ArrayQueue(), INITIAL_QUEUE_SIZE, QUEUE_OPERATIONS);
ready
ArrayQueue (pre-sized)
testQueue(new ArrayQueue(INITIAL_QUEUE_SIZE + 1), INITIAL_QUEUE_SIZE, QUEUE_OPERATIONS);
ready
LinkedListQueue
testQueue(new LinkedListQueue(), INITIAL_QUEUE_SIZE, QUEUE_OPERATIONS);
ready
CircularQueue
testQueue(new CircularQueue(INITIAL_QUEUE_SIZE + 1), INITIAL_QUEUE_SIZE, QUEUE_OPERATIONS);
ready

Revisions

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