search

ekmett / heaps

Asymptotically optimal Brodal/Okasaki heaps
http://hackage.haskell.org/package/heaps
BSD 3-Clause "New" or "Revised" License
29 stars 10 forks source link

`heaps` seems slower than `pqueue` and `psqueues` at inserting/popping #18

Open mitchellwrosen opened 3 years ago

mitchellwrosen commented 3 years ago

Hi, I just thought I'd share this small benchmark I wrote while investigating the speed of various priority queue libraries. Perhaps there's something wrong with the methodology, but if not, heaps appears to be ~1.4-1.5x slower than pqueue/psqueue at inserting 100 random elements (each with one of 10 distinct priorities), then popping them all.

Link to another issue that contains the benchmark: https://github.com/HeinrichApfelmus/reactive-banana/issues/214

treeowl commented 1 year ago

I'm working hard to expand that gap. I just found a shape invariant bug in pqueue whose fix should make it faster for such applications. And I've started the work of making the pqueue representation more compact, which should improve matters further (especially for larger queues).

treeowl commented 1 year ago

Taking a brief glance at the code, I suspect it might help to have a special representation of trees of rank 0. Currently, those take four words. That can easily be reduced to two. The Forest type can then be modified to be nonempty (either by adjoining an element in front or by turning its nil into a constructor that holds a tree; I'm not sure which is better, but my guess is the latter).