Benchmark: single v double array queue

Script Preparation code:

function createSingleListQueue() {
	return {
		queue: [],
		enqueue(element) {
			this.queue.push(element)
		},
		dequeue() {
			return this.queue.shift()
		},
		isEmpty() {
			return this.queue.length === 0
		}
	}
}

function createDoubleListQueue() {
	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
		}
	}
}

var singleQ = createSingleListQueue()
var doubleQ = createDoubleListQueue()
var queueSize = 100000

for(let i = 0; i < queueSize; i++) {
  singleQ.enqueue('testString' + i)
  doubleQ.enqueue('testString' + i)
}

Tests:

single
for(let i = 0; i < 100000; i++) { singleQ.dequeue() }
double
for(let i = 0; i < 100000; i++) { doubleQ.dequeue() }

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
single
double

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: 18 days ago)

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

Browser/OS: Chrome 147 on Mac OS X 10.15.7

View result in a separate tab

Test name	Executions per second
single	1269.7 Ops/sec
double	466.1 Ops/sec

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

LLMs can make mistakes. Check important info.

I'll break down the provided JSON benchmark definition and explanation for you.

**Benchmark Definition**

The benchmark is designed to measure the performance of two different queue implementations: single-linked list (single) and double-linked list (double). The queues are created using JavaScript classes, where `singleQ` represents a simple single-linked list, and `doubleQ` represents a more complex double-linked list with additional functionality.

**Script Preparation Code**

The script preparation code defines the two queue classes:

*   `createSingleListQueue`: Creates a single-linked list queue with basic enqueue, dequeue, and isEmpty methods.
*   `createDoubleListQueue`: Creates a double-linked list queue with additional functionality for managing input and output buffers. This class also includes a pivot method that reverses the input buffer when the output buffer is empty.

**Html Preparation Code**

The HTML preparation code is not provided in this example.

**Individual Test Cases**

There are two test cases:

1.  `single`: Measures the execution time of dequeuing from the single-linked list queue 100,000 times.
2.  `double`: Measures the execution time of dequeuing from the double-linked list queue 100,000 times.

**Comparison Options**

The benchmark compares the performance of two different queue implementations:

*   **Single Linked List (single)**: A simple implementation using a single-linked list with basic enqueue and dequeue operations.
*   **Double Linked List (double)**: A more complex implementation using a double-linked list with additional functionality for managing input and output buffers.

**Pros and Cons**

Here are some pros and cons of each approach:

**Single Linked List (single):**

Pros:

*   Simpler to implement
*   Lower memory overhead

Cons:

*   More expensive operations due to the need to traverse the linked list during dequeue
*   May not be suitable for scenarios with high enqueue rates or large input buffers

**Double Linked List (double):**

Pros:

*   Faster operations due to the ability to access adjacent nodes in O(1) time
*   Suitable for scenarios with high enqueue rates or large input buffers

Cons:

*   More complex implementation
*   Higher memory overhead due to the additional buffer management

**Other Considerations**

*   **Cache Locality**: The double-linked list implementation may exhibit better cache locality, which can lead to faster performance.
*   **Parallelization**: Both implementations can be parallelized using multi-threading or concurrent execution, but this would require modifications to the benchmark code.

**Library and Features**

The `Pivot` method in the double-linked list implementation uses a simple buffer management technique. No external libraries are used in this example.

I hope this explanation helps you understand the provided benchmark definition! Let me know if you have any further questions or need additional clarification.

Related benchmarks:

single v double array queue (version: 0)

Comparing performance of: single vs double

Created: 9 years ago by: Guest

Jump to the latest result

single

double

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

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