Benchmark: Queue data structure

Script Preparation code:

window.TEST_ITERATIONS = 200;
window.Queue = function () {
  const storage = {};
  let front = 0;
  let size = 0;

  const enqueue = function (item) {
    storage[this.size + this.front] = item;
    this.size++;
  };

  const dequeue = function () {
    if (this.size === 0) return undefined;

    const item = storage[this.front];
    delete storage[this.front];
    this.size--;
    if (this.size === 0) this.front = 0;
    else this.front++;
    return item;
  };

  const getFront = function () {
    if (this.size === 0) return undefined;
    return storage[this.front];
  };

  const getRear = function () {
    if (this.size === 0) return undefined;
    return storage[this.size + this.front - 1];
  };

  const isEmpty = function () {
    return this.size === 0;
  };

  return { size, front, enqueue, dequeue, isEmpty, getFront, getRear };
};

Tests:

Object
const queue = Queue(); for (let i = 0; i <= TEST_ITERATIONS; i++) { queue.enqueue(Math.random()); queue.enqueue(Math.random()); queue.enqueue(Math.random()); queue.enqueue(Math.random()); queue.isEmpty(); queue.dequeue(Math.random()); queue.enqueue(Math.random()); queue.dequeue(Math.random()); queue.enqueue(Math.random()); queue.getFront(); queue.getRear(); }
Array
const queue = []; for (let i = 0; i <= TEST_ITERATIONS; i++) { queue.unshift(Math.random()); queue.unshift(Math.random()); queue.unshift(Math.random()); queue.unshift(Math.random()); void (queue.length == 0); queue.pop(Math.random()); queue.unshift(Math.random()); queue.pop(Math.random()); queue.unshift(Math.random()); void (queue[queue.length-1]); void (queue[0]); }

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Object
Array

Fastest: N/A

Slowest: N/A

Latest run results:

No previous run results

This benchmark does not have any results yet. Be the first one to run it!

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

LLMs can make mistakes. Check important info.

Let's dive into the world of JavaScript microbenchmarks and analyze the provided benchmark definition, test cases, and latest benchmark results.

**Benchmark Definition**

The benchmark is for a queue data structure implementation, which allows adding and removing elements from the end of the queue. The implementation uses a simple object with internal variables to store the front, size, and items in the queue.

**Options Compared**

In this benchmark, two options are compared:

1. **Queue as an Object**: This option uses a queue implemented as an object with methods for enqueueing, dequeueing, getting the front item, and checking if the queue is empty.
2. **Queue as an Array**: This option uses a queue implemented as an array with push, pop, unshift, and shift operations.

**Pros and Cons**

Here's a brief analysis of each option:

1. **Queue as an Object**:
	* Pros: More control over data structure implementation, easier to implement custom logic for specific use cases.
	* Cons: May have higher overhead due to object creation and method invocation.
2. **Queue as an Array**:
	* Pros: Efficient and concise implementation using built-in array methods.
	* Cons: Less control over data structure implementation, may not be suitable for custom logic.

**Library Usage**

There is no explicit library usage in the benchmark definition. However, if we consider external dependencies, the `TEST_ITERATIONS` variable is set globally, which might imply the use of a testing framework or utility library.

**Special JS Feature/Syntax**

None of the provided test cases demonstrate any special JavaScript features or syntax. The focus is on comparing different data structure implementations for the queue.

**Other Considerations**

When evaluating microbenchmarks like this one, it's essential to consider factors such as:

* Cache locality: How well do the different implementations cache their results?
* Memory allocation overhead: Does the implementation have significant memory allocation or deallocation costs?
* Data structure complexity: How does the implementation handle edge cases and errors?

**Alternatives**

If you're interested in exploring alternative queue data structures, consider the following options:

1. **Linked List**: A dynamic array of nodes that points to the next node in the sequence.
2. **Circular Buffer**: A fixed-size buffer where elements wrap around when the end is reached.
3. **Priority Queue**: A data structure that orders elements based on their priority.

Keep in mind that each implementation has its trade-offs, and the choice ultimately depends on the specific use case and requirements.

Related benchmarks:

Queue data structure (version: 0)

Comparing performance of: Object vs Array

Created: 4 years ago by: Guest

Jump to the latest result

Object

Array

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

No previous run results

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