Skip to content

Instantly share code, notes, and snippets.

@ziap

ziap/deque-benchmark.js

Last active August 16, 2023 06:36
Show Gist options
  • Save ziap/68cd6721bbc9eb58ce64ff91932df79f to your computer and use it in GitHub Desktop.
Save ziap/68cd6721bbc9eb58ce64ff91932df79f to your computer and use it in GitHub Desktop.
Download ZIP
Benchmark my own deque implementation against invertase/denque
Raw
readme.md

Deque benchmark

Simple benchmark to test my deque implementation against denque

The result are favorable for my implementation but this is my own benchmark so take it with a grain of salt.

Also denque has more features such as splice.

Run the benchmark

wget https://cdn.jsdelivr.net/gh/ziap/jsds/deque.js -O deque.js
wget https://esm.run/denque -O denque.js
deno bench deque-benchmark.js

Result

  • OS: Linux fedora 6.4.10-200.fc38.x86_64 x86_64 GNU/Linux
  • CPU: AMD Ryzen 7 5800U with Radeon Graphics
  • Runtime: deno 1.36.0 v8 11.6.189.12

ITEM = 1337 (integer)

  deque_fromarray
   1.29x slower than denque_fromarray

  deque_grow
   1.12x faster than denque_grow

  deque_clear
   1.19x faster than denque_clear

  deque_shift
   1.38x faster than denque_shift

  deque_toarray1
   1.14x faster than denque_toarray1

  deque_toarray2
   1.16x faster than denque_toarray2

  deque_toarray3
   2.38x slower than denque_toarray3

ITEM = Math.PI (floating point)

  deque_fromarray
   1.41x slower than denque_fromarray

  deque_grow
   1.36x faster than denque_grow

  deque_clear
   16.33x faster than denque_clear

  deque_shift
   6.55x faster than denque_shift

  deque_toarray1
   1.28x faster than denque_toarray1

  deque_toarray2
   1.38x faster than denque_toarray2

  deque_toarray3
   2.13x slower than denque_toarray3
Raw
deque-benchmark.js
const ITEM = Math.PI
const input = new Array(2000000).fill(ITEM)
Deno.bench({group: "grow", baseline: true}, function deque_grow(timer) {
const deque = new Deque()
for (let i = 0; i < 1000; ++i) deque.pushBack(ITEM)
timer.start()
for (let i = 0; i < 20; ++i) {
let old_len = deque.len
for (let j = 0; j < old_len / 2; ++j) deque.popFront()
for (let j = 0; j < old_len; ++j) deque.pushBack(ITEM)
}
timer.end()
})
Deno.bench({group: "grow"}, function denque_grow(timer) {
const denque = new Denque()
for (let i = 0; i < 1000; ++i) denque.push(ITEM)
timer.start()
for (let i = 0; i < 20; ++i) {
let old_len = denque.length
for (let j = 0; j < old_len / 2; ++j) denque.shift()
for (let j = 0; j < old_len; ++j) denque.push(ITEM)
}
timer.end()
})
Deno.bench({group: "clear", baseline: true}, function deque_clear(timer) {
const deque = new Deque(input)
timer.start()
while (deque.len > 0) deque.popFront()
timer.end()
})
Deno.bench({group: "clear"}, function denque_clear(timer) {
const denque = new Denque(input)
timer.start()
while (denque.length > 0) denque.shift()
timer.end()
})
Deno.bench({group: "shift", baseline: true}, function deque_shift(timer) {
const deque = new Deque(input)
timer.start()
for (let i = 0; i < 1000000; ++i) {
const a = deque.popFront()
const b = deque.popFront()
const c = deque.popFront()
deque.pushBack(a)
deque.pushBack(b)
deque.pushBack(c)
}
timer.end()
})
Deno.bench({group: "shift"}, function denque_shift(timer) {
const denque = new Denque(input)
timer.start()
for (let i = 0; i < 1000000; ++i) {
const a = denque.shift()
const b = denque.shift()
const c = denque.shift()
denque.push(a)
denque.push(b)
denque.push(c)
}
timer.end()
})
Deno.bench({group: "fromArray", baseline: true}, function deque_fromarray(timer) {
timer.start()
new Deque(input)
timer.end()
})
Deno.bench({group: "fromArray"}, function denque_fromarray(timer) {
timer.start()
new Denque(input)
timer.end()
})
Deno.bench({group: "toArray1", baseline: true}, function deque_toarray1(timer) {
const deque = new Deque(input)
timer.start()
deque.toArray()
timer.end()
})
Deno.bench({group: "toArray1"}, function denque_toarray1(timer) {
const denque = new Denque(input)
timer.start()
denque.toArray()
timer.end()
})
Deno.bench({group: "toArray2", baseline: true}, function deque_toarray2(timer) {
const deque = new Deque(input)
const power2 = 1 << (32 - Math.clz32(input.length))
const extra = power2 - input.length / 2
for (let i = 0; i < extra; ++i) deque.pushBack(ITEM)
for (let i = 0; i < extra; ++i) deque.popFront()
timer.start()
deque.toArray()
timer.end()
})
Deno.bench({group: "toArray2"}, function denque_toarray2(timer) {
const denque = new Denque(input)
const power2 = 1 << (32 - Math.clz32(input.length))
const extra = power2 - input.length / 2
for (let i = 0; i < extra; ++i) denque.push(ITEM)
for (let i = 0; i < extra; ++i) denque.shift()
timer.start()
denque.toArray()
timer.end()
})
Deno.bench({group: "toArray3", baseline: true}, function deque_toarray3(timer) {
const deque = new Deque(input)
const power2 = 1 << (32 - Math.clz32(input.length))
const extra = power2 - input.length / 2
for (let i = 0; i < extra; ++i) deque.pushBack(deque.popFront())
timer.start()
deque.toArray()
timer.end()
})
Deno.bench({group: "toArray3"}, function denque_toarray3(timer) {
const denque = new Denque(input)
const power2 = 1 << (32 - Math.clz32(input.length))
const extra = power2 - input.length / 2
for (let i = 0; i < extra; ++i) denque.push(denque.shift())
timer.start()
denque.toArray()
timer.end()
})
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment