Revisit performance testing

[Restuta]

My benchmark on merging K number of sorted arrays yields slightly different result and qheap is faster. Let's maybe construct a set of meaningful tests in a separate repo so we can re-produce results and lock down versions of the libraries?

What library version did you use in your tests?

I noticed that you use different comparator functions, is there reason for it? Like for other libs you use a - b comparators and subtraction can be significantly slower than a < bthat you use for others. E.g. qheap supports this by default with comparBefore, but who knows maybe it's not a default for other libs. (e.g. js-priority-queue uses 3 way comparator and it seem to be the only option)

Also it seems https://github.com/andrasq/node-qheap has a reference to this very repo https://github.com/andrasq/node-qheap that shows that it's the fastest and claims it used to show it. What is going on? =)

When I updated comparators to be the same one, my local test also yielded similar result:

❯ node test.js
Platform: darwin 15.3.0 x64
Intel(R) Core(TM) i7-4850HQ CPU @ 2.30GHz
Node version 7.3.0, v8 version 5.4.500.45

Comparing against:
js-priority-queue: https://github.com/adamhooper/js-priority-queue
heap.js: https://github.com/qiao/heap.js
binaryheapx: https://github.com/xudafeng/BinaryHeap
priority_queue: https://github.com/agnat/js_priority_queue
js-heap: https://github.com/thauburger/js-heap
queue-priority: https://github.com/augustohp/Priority-Queue-NodeJS
priorityqueuejs: https://github.com/janogonzalez/priorityqueuejs
qheap: https://github.com/andrasq/node-qheap
yabh: https://github.com/jmdobry/yabh

starting dynamic queue/enqueue benchmark
FastPriorityQueue x 25,991 ops/sec ±1.90% (82 runs sampled)
js-priority-queue x 6,891 ops/sec ±1.50% (84 runs sampled)
heap.js x 2,428 ops/sec ±1.15% (86 runs sampled)
binaryheapx x 3,592 ops/sec ±1.04% (85 runs sampled)
priority_queue x 3,181 ops/sec ±1.37% (85 runs sampled)
js-heap x 236 ops/sec ±1.38% (78 runs sampled)
queue-priority x 366 ops/sec ±1.24% (84 runs sampled)
priorityqueuejs x 5,880 ops/sec ±0.93% (66 runs sampled)
qheap x 31,253 ops/sec ±1.23% (87 runs sampled)
yabh x 3,658 ops/sec ±1.14% (89 runs sampled)
Fastest is qheap

(btw another issue that test fails saying "pluck" doesn't exist, this is used to output last line)

[lemire]

Let's maybe construct a set of meaningful tests in a separate repo so we can re-produce results and lock down versions of the libraries?

That's a good idea.

Like for other libs you use a - b comparators and subtraction can be significantly slower than a < b that you use for others.

I am following the documentation of the various libraries. If I made a mistake, please point it out so I can fix it.

In principle, checking that a - b < 0 should not be faster than checking that a < b. If I recall, Java defaults on 3-way comparators and there is no performance penalty that I know of. Of course, we may be hitting limits in how well the JavaScript engine can optimize code.

Also it seems https://github.com/andrasq/node-qheap has a reference to this very repo https://github.com/andrasq/node-qheap that shows that it's the fastest and claims it used to show it. What is going on? =)

Just a theory: maybe someone noticed that I was getting faster results and they updated their library?

I strongly suspect that this is what happened here. If it did, great. We are moving forward.

[lemire]

It seems that pluck was removed from the benchmark library but it is not clear what replaces it (map supposedly, but it fails with an error on my system). So I have removed the line that indicates the winner.

[Restuta]

in principle, checking that a - b < 0 should not be faster than checking that a < b.

@lemire yes, it's vise-versa, also consistent with my tests. (with your tests run by me)

[Restuta]

I strongly suspect that this is what happened here. If it did, great. We are moving forward.

I guess, so we can lock down versions and update results and also it's a challenge now to make this lib even faster =).

What do you think are good next actionable steps?

[lemire]

@Restuta

What do you think are good next actionable steps?

If you do have time, it would be useful for you to create your own independent benchmark.

[Restuta]

@lemire unfortunately I don't have that much time, but I can send a PR improving yours

[lemire]

Sure, please issue a PR at your earliest convenience.