Benchmark: Circular Queue vs Linked List Queue v2

Script Preparation code:

var CircularQueue = class CircularQueue {
  constructor(growth) {
    this.growth = growth
    this.data = new Array(4);

    // 항상 꺼낼 원소를 가리켜야 함
    this.head = 0;

    // 항상 새로운 원소를 넣을 공간을 가리켜야 함
    this.tail = 0;
    this.size = 0;
  }

  grow() {
    const length = this.data.length;
    this.data = this.data
      .slice(this.head, length)
      .concat(this.data.slice(0, this.head))
      .concat(new Array(Math.max(1, Math.ceil(length * this.growth))));
    this.head = 0;
    this.tail = length;
  }

  push(el) {
    this.data[this.tail] = el;
    this.tail = (this.tail + 1) % this.data.length;
    if (this.tail === this.head) {
      this.grow();
    }
    this.size += 1;
  }

  pop() {
    if (this.size <= 0) return undefined;
    const result = this.data[this.head];
    this.head = (this.head + 1) % this.data.length;
    this.size -= 1;
    return result;
  }

  front() {
    if (this.size <= 0) return undefined;
    return this.data[this.head];
  }
}

var LinkedListQueue = class LinkedListQueue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  push(el) {
    const newNode = {
      next: null,
      value: el
    };
    if (this.tail) {
      this.tail.next = newNode;
    } else {
      this.head = newNode;
    }
    this.tail = newNode;
    this.size += 1;
  }

  pop() {
    const result = this.head?.value;
    this.head = this.head?.next;
    if (!this.head) {
      this.tail = null;
    }
    this.size = Math.max(0, this.size - 1);
    return result;
  }

  front() {
    return this.head?.value;
  }

  debug() {
    const arr = [];
    let node = this.head;
    while (node) {
      arr.push(node.value);
      node = node.next;
    }
    console.log(arr.join(", "));
  }
}

const N = 1000000
const operations = new Array(N)
for (let n = 0; n < N; ++n) {
  operations[n] = (n ** 2 + 3 * n) % 2
}

function test(q) {
  for (const op of operations) {
    if (op) {
      q.push(Math.random())
    } else {
      q.pop()
    }
  }
}

Tests:

CircularQueue (rate = 1)
test(new CircularQueue(1))
LinkedListQueue
test(new LinkedListQueue())
CircularQueue (rate = 0.5)
test(new CircularQueue(0.5))
CircularQueue (rate = 0.25)
test(new CircularQueue(0.25))

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
CircularQueue (rate = 1)
LinkedListQueue
CircularQueue (rate = 0.5)
CircularQueue (rate = 0.25)

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) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/128.0.0.0 Safari/537.36

Browser/OS: Chrome 128 on Windows

View result in a separate tab

Test name	Executions per second
CircularQueue (rate = 1)	13.7 Ops/sec
LinkedListQueue	13.7 Ops/sec
CircularQueue (rate = 0.5)	13.7 Ops/sec
CircularQueue (rate = 0.25)	13.7 Ops/sec

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

LLMs can make mistakes. Check important info.

I'd be happy to explain the benchmark and its options.

**Benchmark Definition**

The benchmark compares two data structures: Circular Queue and Linked List Queue (also known as Doubly Linked List). The goal is to measure their performance in terms of execution rate when inserting and removing elements at different rates.

**Circular Queue vs Linked List Queue v2**

A Circular Queue is a type of queue where the last element is connected back to the first element, forming a circle. This allows for efficient insertion and removal of elements from both ends.

A Linked List Queue (Doubly Linked List) is a data structure that consists of nodes with references to each other. Each node has two pointers: one pointing to the next node in the list, and another pointing to the previous node. This allows for efficient insertion and removal of elements at any position in the list.

**Options Compared**

The benchmark compares the performance of Circular Queue and Linked List Queue (Doubly Linked List) under different insertion and removal rates:

1. **Rate = 1**: Elements are inserted and removed at a rate of one per unit time.
2. **Rate = 0.5**: Elements are inserted and removed at a rate half that of the previous option.
3. **Rate = 0.25**: Elements are inserted and removed at a rate quarter that of the previous option.

**Pros and Cons**

* **Circular Queue**:
	+ Pros: Efficient insertion and removal of elements from both ends, reduced memory usage due to circular structure.
	+ Cons: Can lead to caching issues if not implemented carefully, may experience slower performance due to overhead of circularization.
* **Linked List Queue (Doubly Linked List)**:
	+ Pros: Allows for efficient insertion and removal of elements at any position in the list, can handle varying rates of insertion and removal.
	+ Cons: Requires more memory than Circular Queue due to node allocation, can lead to slower performance due to pointer manipulation.

**Library Used**

In this benchmark, both queues use JavaScript classes implemented by the test users. The `CircularQueue` class uses a circular array to store elements, while the `LinkedListQueue` class uses a doubly linked list implementation. No external libraries are used for the implementation of these data structures.

**Browser and Device Information**

The benchmark was run on Chrome 128 browser on Windows Desktop with a specific User Agent String (`Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/128.0.0.0 Safari/537.36`). The Device Platform is set to Desktop, and the Operating System is Windows.

**Execution Rates**

The benchmark provides execution rates for each test case in terms of executions per second (`ExecutionsPerSecond`). These values indicate how many elements can be inserted or removed by the queue in a single second.

Related benchmarks:

Circular Queue vs Linked List Queue v2 (version: 1)

Comparing performance of: CircularQueue (rate = 1) vs LinkedListQueue vs CircularQueue (rate = 0.5) vs CircularQueue (rate = 0.25)

Created: 4 years ago by: Registered User

Jump to the latest result

CircularQueue (rate = 1)

LinkedListQueue

CircularQueue (rate = 0.5)

CircularQueue (rate = 0.25)

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

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