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)

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

Jump 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

Test name	Executions per second
Double Array enque	231.4 Ops/sec
Linked List enque	74.5 Ops/sec
Queue enqeue	22.1 Ops/sec
Array deque	434.9 Ops/sec
LinkedList deque	545.7 Ops/sec
Queue deque	41.4 Ops/sec
Array deque from Tails	309.6 Ops/sec
Linked from Tail	685.6 Ops/sec
Queue from tail	705.5 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.

Related benchmarks: