Add benchmark with Js-sdsl

[ZLY201]

Hey! I'm the developer of Js-sdsl.

Official website: https://js-sdsl.github.io/

I made a simple comparison between denque and Deque in Js-sdsl. See https://js-sdsl.github.io/#/test/benchmark-result?id=deque.

I think persistent inserts and random access should be included in benchmarks for deque.

Because the most important performance bottleneck of deque should be the growth time during continuous insertion.

Emptying after inserting a small amount of data in your test cannot fully express the performance of deque. We all now in the single insert, time will be O(1).

I hope to improve your benchmark and compare with Js-sdsl

Looking forward to receiving your reply :D.

[vanodevium]

import {bench, group, run} from "mitata";
import DenQueue from "denque";
import {Deque} from '@js-sdsl/deque'
import {Queue} from '@js-sdsl/queue'

const iterations = 3_000_000;

group("Queue tests", () => {
  bench("simple array", () => {
    const q = [];
    for (let i = iterations; i > 0; i--) {
      q.push(i);
    }
  });
  bench("DenQueue", () => {
    const q = new DenQueue();
    for (let i = iterations; i > 0; i--) {
      q.push(i);
    }
  })
  bench("Deque", () => {
    const q = new Deque();
    for (let i = iterations; i > 0; i--) {
      q.pushBack(i);
    }
  })
  bench("Queue", () => {
    const q = new Queue();
    for (let i = iterations; i > 0; i--) {
      q.push(i);
    }
  });
});

await run();

Node 20 runtime

cpu: Intel(R) Core(TM) i7-8565U CPU @ 1.80GHz
runtime: node v20.0.0 (x64-linux)

benchmark         time (avg)             (min … max)       p75       p99      p995
---------------------------------------------------- -----------------------------
• Queue tests
---------------------------------------------------- -----------------------------
simple array   60.27 ms/iter    (49.9 ms … 70.44 ms)  66.25 ms  70.44 ms  70.44 ms
DenQueue       44.81 ms/iter   (39.41 ms … 47.47 ms)  44.99 ms  47.47 ms  47.47 ms
Deque           50.3 ms/iter   (44.92 ms … 56.11 ms)   52.2 ms  56.11 ms  56.11 ms
Queue          64.54 ms/iter   (55.66 ms … 75.92 ms)  67.61 ms  75.92 ms  75.92 ms

summary for Queue tests
  DenQueue
   1.12x faster than Deque
   1.35x faster than simple array
   1.44x faster than Queue

Bun runtime

cpu: Intel(R) Core(TM) i7-8565U CPU @ 1.80GHz
runtime: bun 0.5.9 (x64-linux)

benchmark         time (avg)             (min … max)       p75       p99      p995
---------------------------------------------------- -----------------------------
• Queue tests
---------------------------------------------------- -----------------------------
simple array   19.48 ms/iter   (18.85 ms … 21.33 ms)  19.61 ms  21.33 ms  21.33 ms
DenQueue       33.55 ms/iter   (32.03 ms … 43.74 ms)  33.32 ms  43.74 ms  43.74 ms
Deque          44.32 ms/iter   (43.43 ms … 46.72 ms)   44.7 ms  46.72 ms  46.72 ms
Queue          37.01 ms/iter   (34.22 ms … 45.92 ms)  36.23 ms  45.92 ms  45.92 ms

summary for Queue tests
  simple array
   1.72x faster than DenQueue
   1.9x faster than Queue
   2.28x faster than Deque