Benchmark: Linked List Queue vs Double Array Queue vs Queue with Map enqueue/dequeue/dequeueTail

Linked List Queue vs Double Array Queue vs Queue with Map enqueue/dequeue/dequeueTail (version: 0) Benchmark.js

Testing a linked list queue vs a double list queue vs Queue with Map for different performance scenarios.

Comparing performance of: `Double Array enque vs Linked List enque vs Queue enqeue vs Array deque vs LinkedList deque vs Queue deque vs Array deque from Tails vs Linked from Tail vs Queue from tail`

Created: 2 years ago by: Guest

Go to the latest result

Script Preparation code:

class LinkedListQueue {
  constructor() {
    this.length = 0;
    this.head = undefined;
    this.tail = undefined;
  }

  enqueue(value) {
    this.enqueueNode(value);
  }

  dequeue() {
    return this.dequeueNode();
  }

  dequeueFromTail() {
    return this.dequeueNodeFromTail();
  }

  size() {
    return this.length;
  }

  getHead() {
    return this.head;
  }

  getTail() {
    return this.tail;
  }

  enqueueNode(value) {
    const node = {
      value,
      next: undefined,
      prev: this.tail
    };

    if (!this.head) {
      this.head = node;
      this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
    }

    this.length += 1;
  }

  dequeueNode() {
    if (this.head) {
      const value = this.head.value;
      this.head = this.head.next;

      if (this.head) {
        this.head.prev = undefined;
      } else {
        this.tail = undefined;
      }

      this.length -= 1;
      return value;
    }

    return undefined;
  }

  dequeueNodeFromTail() {
    if (this.tail) {
      const value = this.tail.value;
      this.tail = this.tail.prev;

      if (this.tail) {
        this.tail.next = undefined;
      } else {
        this.head = undefined;
      }

      this.length -= 1;
      return value;
    }

    return undefined;
  }
}


class DoubleArrayQueue {
  constructor() {
    this.input = [];
    this.output = [];
  }

  enqueue(element) {
    this.input.push(element);
  }

  dequeue() {
    if (this.output.length === 0) {
      this.pivot();
    }
    return this.output.pop();
  }

  dequeueFromTail() {
    if (this.input.length === 0) {
      this.pivot();
    }
    return this.input.pop();
  }

  pivot() {
    this.output = this.input.reverse();
    this.input = [];
  }

  isEmpty() {
    return this.input.length === 0 && this.output.length === 0;
  }
}


class Queue {
    constructor() {
        this.queue = new Map();
        this.head = 0;
        this.tail = 0;
    }

    enqueue(item) {
        this.queue.set(this.tail, item);
        this.tail++;
    }

    dequeue() {
        if (this.head === this.tail) return;

        const value = this.queue.get(this.head);
        this.queue.delete(this.tail);
        this.head++;

        return value;
    }
            
    dequeueFromTail() {
        if (this.head === this.tail) return;
        this.tail--;
        const value = this.queue.get(this.tail);
        this.queue.delete(this.tail);
        return value;
    }

    size() {
        return this.tail - this.head;
    }
}

var doubleQ = new DoubleArrayQueue()
var linkedListQ = new LinkedListQueue()
var queue = new Queue()
var queueSize = 100000

Tests:

Double Array enque
for(let i = 0; i < queueSize; i++) { doubleQ.enqueue(i) }
Linked List enque
for(let i = 0; i < queueSize; i++) { linkedListQ.enqueue(i) }
Queue enqeue
for(let i = 0; i < queueSize; i++) { queue.enqueue(i) }
Array deque
for(let i = 0; i < queueSize; i++) { doubleQ.dequeue() }
LinkedList deque
for(let i = 0; i < queueSize; i++) { linkedListQ.dequeue() }
Queue deque
for(let i = 0; i < queueSize; i++) { queue.dequeue() }
Array deque from Tails
for(let i = 0; i < queueSize; i++) { doubleQ.dequeueFromTail() }
Linked from Tail
for(let i = 0; i < queueSize; i++) { linkedListQ.dequeueFromTail() }
Queue from tail
for(let i = 0; i < queueSize; i++) { queue.dequeueFromTail() }

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Double Array enque
Linked List enque
Queue enqeue
Array deque
LinkedList deque
Queue deque
Array deque from Tails
Linked from Tail
Queue from tail

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: one year ago)

User agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:136.0) Gecko/20100101 Firefox/136.0

Browser/OS: Firefox 136 on Windows

View result in a separate tab

Queue from tail

706/s

Linked from Tail

686/s

LinkedList deque

546/s

Array deque

435/s

Array deque from Tails

310/s

Double Array enque

231/s

Linked List enque

74/s

Queue deque

41/s

Queue enqeue

22/s

View exact numbers

Test name	Executions per second
✓ Queue from tail	706 Ops/sec
Linked from Tail	686 Ops/sec
LinkedList deque	546 Ops/sec
Array deque	435 Ops/sec
Array deque from Tails	310 Ops/sec
Double Array enque	231 Ops/sec
Linked List enque	74 Ops/sec
Queue deque	41 Ops/sec
Queue enqeue	22 Ops/sec

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):

LLMs can make mistakes. Check important info.

Here is the parsed data from the JSON-like string:

```json
[
    {
        "Browser": "Yandex Browser 23",
        "DevicePlatform": "Desktop",
        "OperatingSystem": "Mac OS X 10.13.6",
        "ExecutionsPerSecond": 66.1090087890625,
        "TestName": "Array deque"
    },
    {
        "Browser": "Yandex Browser 23",
        "DevicePlatform": "Desktop",
        "OperatingSystem": "Mac OS X 10.13.6",
        "ExecutionsPerSecond": 64.6464614868164,
        "TestName": "Double Array enque"
    },
    {
        "Browser": "Yandex Browser 23",
        "DevicePlatform": "Desktop",
        "OperatingSystem": "Mac OS X 10.13.6",
        "ExecutionsPerSecond": 60.64847183227539,
        "TestName": "Array deque from Tails"
    },
    {
        "Browser": "Yandex Browser 23",
        "DevicePlatform": "Desktop",
        "OperatingSystem": "Mac OS X 10.13.6",
        "ExecutionsPerSecond": 34.849952697753906,
        "TestName": "Queue deque"
    },
    {
        "Browser": "Yandex Browser 23",
        "DevicePlatform": "Desktop",
        "OperatingSystem": "Mac OS X 10.13.6",
        "ExecutionsPerSecond": 31.778057098388672,
        "TestName": "Linked from Tail"
    },
    {
        "Browser": "Yandex Browser 23",
        "DevicePlatform": "Desktop",
        "OperatingSystem": "Mac OS X 10.13.6",
        "ExecutionsPerSecond": 30.303030014038086,
        "TestName": "LinkedList deque"
    },
    {
        "Browser": "Yandex Browser 23",
        "DevicePlatform": "Desktop",
        "OperatingSystem": "Mac OS X 10.13.6",
        "ExecutionsPerSecond": 28.18597984313965,
        "TestName": "Linked List enque"
    },
    {
        "Browser": "Yandex Browser 23",
        "DevicePlatform": "Desktop",
        "OperatingSystem": "Mac OS X 10.13.6",
        "ExecutionsPerSecond": 20.00459861755371,
        "TestName": "Queue enqeue"
    }
]
```

This data appears to be a list of test results from various browsers running on a Mac OS X system, with each test result containing information about the browser used, device platform, operating system, execution frequency per second, and test name.