Open ZLY201 opened 2 years ago
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();
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
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
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.