lemire / FastPriorityQueue.js

a fast heap-based priority queue in JavaScript
Apache License 2.0
357 stars 57 forks source link

Optimize baseline and special case performance for kSmallest #37

Closed Barbarrosa closed 1 year ago

Barbarrosa commented 1 year ago

Improve the baseline and special case performance of kSmallest.

Before:

starting dynamic queue/enqueue benchmark
FastPriorityQueue--queue-and-kSmallest x 26.71 ops/sec ±1.26% (48 runs sampled)

starting dynamic queue/enqueue benchmark
FastPriorityQueue--queue-and-kSmallest x 2.75 ops/sec ±1.76% (11 runs sampled)

After:

starting dynamic queue/enqueue benchmark
FastPriorityQueue--queue-and-kSmallest x 36.96 ops/sec ±1.03% (64 runs sampled)

starting dynamic queue/enqueue benchmark
FastPriorityQueue--queue-and-kSmallest x 3.66 ops/sec ±1.26% (14 runs sampled)
lemire commented 1 year ago

@Barbarrosa This is very good. Please consider my comments.

Barbarrosa commented 1 year ago

@lemire I updated the branch based on your comments. Here is the updated performance based on my testing today.

Before (slow)

starting dynamic queue/enqueue benchmark
FastPriorityQueue--queue-and-kSmallest x 25.80 ops/sec ±0.42% (46 runs sampled)

starting dynamic queue/enqueue benchmark
FastPriorityQueue--queue-and-kSmallest x 2.70 ops/sec ±1.92% (11 runs sampled)

Original PR (faster)

starting dynamic queue/enqueue benchmark
FastPriorityQueue--queue-and-kSmallest x 39.60 ops/sec ±0.95% (52 runs sampled)

starting dynamic queue/enqueue benchmark
FastPriorityQueue--queue-and-kSmallest x 4.06 ops/sec ±0.80% (15 runs sampled)

PR after changes (similar to Original PR)

starting dynamic queue/enqueue benchmark
FastPriorityQueue--queue-and-kSmallest x 39.81 ops/sec ±0.67% (53 runs sampled)

starting dynamic queue/enqueue benchmark
FastPriorityQueue--queue-and-kSmallest x 4.03 ops/sec ±1.56% (15 runs sampled)
lemire commented 1 year ago

Great. Merging.

staltz commented 1 year ago

Just a heads up (I don't have more information at the moment), this PR broke a corner case in jitdb, something about calling kSmallest and it returning undefined. I'll try to work on finding a simple reproduction and submit a test to FastPriorityQueue.

cc @arj03

Barbarrosa commented 1 year ago

@staltz I identified the issue, it's an overflow when requesting larger numbers of records. I'll open a PR to fix it.

Barbarrosa commented 1 year ago

@staltz @lemire I opened https://github.com/lemire/FastPriorityQueue.js/pull/38 to address the issue.