Queue (v4)

Revision 4 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 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;
  }

}

class CircularQueue {

  constructor(capacity, preSized = false) {
    this.capacity = capacity;
    this.headIndex = 0;
    this.tailIndex = 0;
    this.length = 0;

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

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

    this.array[this.tailIndex] = element;

    this.tailIndex = (this.tailIndex + 1) % this.capacity;
    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.capacity;
    this.length--;

    return element;
  }

}

const QUEUE_ELEMENT = new Uint8Array();

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

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

const INITIAL_QUEUE_SIZE = 4999;
const QUEUE_OPERATIONS = 1000;

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
CircularQueue (pre-sized)
testQueue(new CircularQueue(INITIAL_QUEUE_SIZE + 1, true), 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.