Migrate deque from denque to Js-sdsl Deque

[ZLY201]

Hey! I'm the developer of Js-sdsl. Official website: https://js-sdsl.github.io/.

Now, we published the version 4.1.4.

I see you are using denque.

In benchmark, we have confirmed that Js-sdsl is several times faster than denque and nearly equal to Array.push in the case of push elements.

We would like to invite you to migrate deque related functions to Js-sdsl v4.1.4 and I am willing to submit a pull request for this change.

Looking forward to your reply! :D

[rusher]

Thanks for indicating that, but in our specific use-case, our benchmark performs better using denque: most of our use is push and shift and even if js-sdsl is faster in other things, denque performs better in this use-case tested with :

const Benchmark = require('benchmark');
const { LinkList, Queue } = require('js-sdsl');
const QueueDenque = require('denque');

const t1 = new LinkList();
const t2 = new QueueDenque();
const t3 = new Queue(new Array(2000));

for (let i = 0; i < 600; i++) {
  t1.pushBack('elm');
  t2.push('elm');
  t3.push('elm');
}

var suite = new Benchmark.Suite();

// add tests
suite
  .add('LinkList with 1000 element push and shift', function () {
    t1.pushBack('elm');
    return t1.popFront();
  })
  .add('denque with 1000 element push and shift', function () {
    t2.push('elm');
    return t2.shift();
  })
  .add('Queue with 1000 element push and shift', function () {
    t3.push('elm');
    return t3.pop();
  })
  // add listeners
  .on('cycle', function (event) {
    console.log(String(event.target));
  })
  // run async
  .run({ async: true });

resulting in

LinkList with 1000 element push and front x 10,151,006 ops/sec ±3.79% (68 runs sampled)
denque with 1000 element push and shift x 171,003,836 ops/sec ±0.56% (94 runs sampled)
Queue with 1000 element push and shift x 19,941,066 ops/sec ±1.07% (95 runs sampled)

[ZLY201]

Thanks for your reply!

But I think this test cannot reflect the real performance difference between the two structures. The reasons as follow:

1. You should use Deque but not Queue in js-sdsl. Queue is a little slow than Deque.
2. The performance bottleneck of the data structure named double-ended-queue are reflected in capacity expansion. I submitted https://github.com/invertase/denque/issues/49 but no reply.
3. This test method is just a simple simulation and does not really reflect its performance in the database connection. I am looking for a way to test it more realistically. https://github.com/js-sdsl/js-sdsl/issues/124

In summary, I think it is unreasonable to think that the performance of js-sdsl is worse then denque.

[rusher]

I didn't know about queue beeing slower than deque, i would have think the opposite.

In fact, I've done this benchmark because i've first made the change to js-sdsl in development, and run the db benchmarks, resulting in worst performance. After analysis, this was due to this scenario "push and shift" that is slower in js-sdsl.

I'll have to redo my bench with deque in place of Queue :)

[ZLY201]

Sorry, I found the reason for its slowness. This was caused by an PR which want to fixes elements not being empty.

I'll fix it later.

[ZLY201]

The version 4.3.0 has been published. You can try it again. @rusher

[rusher]

I've tryed again, and even if 4.3.0 perform better, denque still fit better in connector use (in fact implementation fit exactly to use, it will be hard to replace). So i'm closing this issue