Benchmark: Linked List Queue vs Double Array Queue vs Queue with Map v2

Script Preparation code:

function createLinkedListQueue() {
	let length = 0
	let head = undefined
	let tail = undefined
	return {
		enqueue(value) {
			enqueueNode(value)
		},
		dequeue() {
			return dequeueNode()
		},
		size() {
			return length
		},
		head() {
			return head
		},
		tail() {
			return tail
		}
	}
	function enqueueNode(value) {
		const node = {
			value,
			next: undefined 
		}
		if(!head) {
			head = node
			tail = node
		}
		else {
			tail.next = node
			tail = node
		}
		length += 1	
	}
	function dequeueNode() {
		if(head) {
			const value = head.value
			head = head.next
			length -= 1
			return value
		}
		tail = undefined
		return undefined
	}
}

function createDoubleArrayQueue() {
	return {
		input: [],
		output: [],
		enqueue(element) {
			this.input.push(element)
		},
		dequeue() {
			if(this.output.length === 0) {
				this.pivot()
			}
			return this.output.pop()
		},
		pivot() {
			this.output = this.input.reverse()
			this.input = []
		},
		isEmpty() {
			return this.input.length === 0 && this.output.length === 0
		}
	}
}

class Queue {
    #queue = new Map()
    #head = 0
    #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
    }

    size() {
        return this.#tail - this.#head
    }
}

var doubleQ = createDoubleArrayQueue()
var linkedListQ = createLinkedListQueue()
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++) { linkedListQ.dequeue() }
LinkedList deque
for(let i = 0; i < queueSize; i++) { linkedListQ.dequeue() }
Queue deque
for(let i = 0; i < queueSize; i++) { queue.dequeue() }

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

Fastest: N/A

Slowest: N/A

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

LLMs can make mistakes. Check important info.

**Overview of the Benchmark**

The provided JSON represents a JavaScript benchmarking test, specifically designed to compare the performance of three different queue data structures:

1. Linked List Queue
2. Double Array Queue
3. Queue with Map (using the built-in `Map` object in JavaScript)

The test consists of six individual test cases, each measuring the execution time for a specific operation:

* Enqueuing an element into the queue
* Dequeuing an element from the queue

**What is being tested?**

In essence, this benchmark is testing the performance of different data structures for inserting and removing elements. The results will provide insight into which data structure is most efficient in terms of execution time.

**The Data Structures**

1. **Linked List Queue**: A simple queue implemented using a linked list.
2. **Double Array Queue**: A queue implemented using an array, with each element being wrapped in an object to avoid indexing issues.
3. **Queue with Map**: A queue implemented using the built-in `Map` object in JavaScript, which provides efficient insertion and deletion operations.

**The Test Cases**

Each test case consists of a single operation:

* Enqueuing an element into the queue
* Dequeuing an element from the queue

The results are reported in terms of **ExecutionsPerSecond**, which represents the number of executions per second for each test case.

**Interpretation of Results**

By comparing the execution times across different data structures, we can infer:

* Which data structure is most efficient in terms of execution time.
* Whether the use of a built-in data structure (e.g., `Map`) provides significant performance benefits over custom implementations.

In this specific benchmark, the results suggest that the **Queue with Map** implementation is the fastest for both enqueuing and dequeuing operations. The Linked List Queue and Double Array Queue implementations are significantly slower.

Latest run results:

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

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/117.0.0.0 Safari/537.36

Browser/OS: Chrome 117 on Mac OS X 10.15.7

View result in a separate tab

Test name	Executions per second
Double Array enque	123.3 Ops/sec
Linked List enque	63.7 Ops/sec
Queue enqeue	25.1 Ops/sec
Array deque	84.2 Ops/sec
LinkedList deque	43.4 Ops/sec
Queue deque	31.8 Ops/sec

Related benchmarks:

Linked List Queue vs Double Array Queue vs Queue with Map v2 (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

Created: one year ago by: Guest

Jump to the latest result

Double Array enque

Linked List enque

Queue enqeue

Array deque

LinkedList deque

Queue deque

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

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