Benchmark: Queue Implement by 2 Stacks

HTML Preparation code:

<script>
    (async () => {
        const importObject = { imports: { } };
        const ex = 'https://unpkg.com/@wass80/wasm-queue@0.2.2/wasm_queue_bg.wasm';
        const wasm_obj = await WebAssembly.instantiateStreaming(fetch(ex), importObject);
        const wasm = wasm_obj.instance.exports;

        window.wasm_zigzag = wasm.zigzag
    })();
</script>

Script Preparation code:

window.zigzag = (n, init, shift, push)=>{
  let seed = 12345;
  let size = 0;
  let last = -1;

  for (let i = 0; i < n; i++) {
    if (size > 0 && (seed & 20480) == 0) { // 2^12+2^14=20480
      last = shift(init);
      size--;
    } else {
      push(init,seed);
      size++;
    }
    seed = (seed * 1664525 + 1013904223) & 2147483647;
  }
  if (last !== 1508974062) alert("Assertion Failed!");
}

// 2 Stack
window.stack_shift = x=>{
  if (x[0].length == 0){
    x[0] = x[1];
    x[1] = [];
    x[0].reverse();
  }
  return x[0].pop();
}

window.stack_push = (x,v)=>{
  x[1].push(v);
}

// Ring Buffer
window.ring_shift = (a) => {
    const res = a.data[a.head];
    a.head = (a.head + 1) % a.data.length;
    return res;
}


window.ring_push = (a,v)=>{
  a.data[a.tail] = v;
  a.tail = (a.tail + 1) % a.data.length;
}

window.ring_init = (r) => {return {data: new Array(r), head:0, tail: 0}};

window.int32array_init = (r) => {return {data: new Int32Array(r), head:0, tail: 0}};


window.n = 100000;

Tests:

Array
zigzag(n, [], a=>a.shift(), (a,v)=>a.push(v))
Queue with 2 Stacks
zigzag(n, [[],[]], stack_shift, stack_push)
Ring Buffer
zigzag(n, ring_init(n), ring_shift, ring_push)
Ring Buffer (Int32Array)
zigzag(n, int32array_init(n), ring_shift, ring_push)
(FYI) Rust + wasm
last = window.wasm_zigzag(n); if (last !== 1508974062) alert("Assertion Failed!");

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Array
Queue with 2 Stacks
Ring Buffer
Ring Buffer (Int32Array)
(FYI) Rust + wasm

Fastest: N/A

Slowest: N/A

Latest run results:

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

User agent: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/120.0.0.0 Whale/3.5.4.2 Safari/537.36

Browser/OS: Chrome 120 on Linux

View result in a separate tab

Test name	Executions per second
Array	5.1 Ops/sec
Queue with 2 Stacks	232.0 Ops/sec
Ring Buffer	310.9 Ops/sec
Ring Buffer (Int32Array)	416.9 Ops/sec
(FYI) Rust + wasm	1590.5 Ops/sec

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

LLMs can make mistakes. Check important info.

Measuring performance is essential in software development, and MeasureThat.net provides a valuable tool for doing so.

**Benchmark Overview**

The provided benchmark is designed to test the performance of different data structures (Queues) implemented using two stacks. The goal is to compare the execution speed of these different approaches.

**Data Structures Compared**

There are four data structures compared:

1. **Queue with 2 Stacks**: This approach uses two stacks to implement a queue. The `stack_push` function is used to add elements to the queue, while the `stack_shift` function is used to remove elements from the front of the queue.
2. **Ring Buffer**: This approach uses a ring buffer data structure, which is a circular buffer that stores data in a single array. The `ring_shift` function is used to remove elements from the front of the queue, while the `ring_push` function is used to add elements to the end of the queue.
3. **Ring Buffer with Int32Array**: This approach uses a ring buffer data structure implemented using an `Int32Array`. It's similar to the previous implementation but uses an array of 32-bit integers instead of JavaScript objects.
4. **Native Rust + WebAssembly (FYI)**: This is a reference implementation that uses native Rust and WebAssembly to implement the queue. It serves as a baseline for comparison.

**Options Compared**

The options compared are:

* `stack_push` vs. `ring_push`: These functions are used to add elements to the queue.
* `stack_shift` vs. `ring_shift`: These functions are used to remove elements from the front of the queue.
* Two stack implementation vs. ring buffer implementation: The two approaches have different performance characteristics.

**Pros and Cons**

Here's a summary of the pros and cons of each approach:

1. **Queue with 2 Stacks**
	* Pros:
		+ Easy to implement
		+ Good cache locality (elements are stored in adjacent memory locations)
	* Cons:
		+ Can be slower than ring buffer implementation due to the overhead of stack operations
2. **Ring Buffer**
	* Pros:
		+ Fast and efficient
		+ Good cache locality
	* Cons:
		+ Requires careful management of indices (head, tail, etc.)
3. **Ring Buffer with Int32Array**
	* Pros:
		+ Similar performance to the ring buffer implementation
		+ No additional overhead from JavaScript objects
	* Cons:
		+ Limited flexibility compared to the ring buffer implementation
4. **Native Rust + WebAssembly (FYI)**
	* Pros:
		+ Fast and efficient
		+ Good cache locality
	* Cons:
		+ Requires native compilation and linking

**Performance Results**

The provided results show that the ring buffer implementation outperforms the queue with two stacks approach. The native Rust + WebAssembly implementation is also relatively fast, but it serves as a baseline for comparison.

In summary, this benchmark provides valuable insights into the performance characteristics of different data structures implemented using JavaScript. By comparing these approaches, developers can choose the best approach for their specific use case and optimize their code accordingly.

Related benchmarks:

Queue Implement by 2 Stacks (version: 7)

Comparing performance of: Array vs Queue with 2 Stacks vs Ring Buffer vs Ring Buffer (Int32Array) vs (FYI) Rust + wasm

Created: 6 years ago by: Registered User

Jump to the latest result

Array

Queue with 2 Stacks

Ring Buffer

Ring Buffer (Int32Array)

(FYI) Rust + wasm

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

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