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

ⓘ Get performance results from real users on your website with Request Metrics.

Website Performance Monitoring by Request Metrics

Latest run results:

Run details: (Test run date: 10 months ago)

User agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/114.0.0.0 Safari/537.36

Browser/OS: Chrome 114 on Windows

View result in a separate tab

Test name	Executions per second
Array	12.0 Ops/sec
Queue with 2 Stacks	383.9 Ops/sec
Ring Buffer	455.9 Ops/sec
Ring Buffer (Int32Array)	504.9 Ops/sec
(FYI) Rust + wasm	1996.2 Ops/sec

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: 4 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>

Experimental features:

Fastest: N/A

Slowest: N/A