lemire
Revisit performance testing
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)
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.
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.
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)
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?
@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.
@lemire unfortunately I don't have that much time, but I can send a PR improving yours