ANN: psqueue-benchmarks - benchmarks of priority queue implementations
(This is a slightly detailed email. If you are the maintainer of one of the packages benchmarked here, you might want to read it though.) Today I was looking for a Priority Queue that also allows a delete operation (some call this a "Priority Search Queue"). I found http://stackoverflow.com/questions/6976559/comparison-of-priority-queue-impl... and after looking at the 10 queue alternatives, I got to the following conclusions: * Only 3 of them allow to delete entries (are p*s*queues) * Most of them are outdated or at least unmaintained for the last 3-5 years * There was an effort to get a priority queue into containers (see the stackoverflow link), but it was not agreed on * Those efforts were driven by Louis Wasserman, who wrote one of the 3 psqueues (queuelike), but now only maintains a non-ps-queue (pqueue) that seems to be the most popular priority queue implementation PSQueue implementations ----------------------- The three packages that are psqueues are: - PSQueue (http://hackage.haskell.org/package/PSQueue-1.1) * original implementation from paper of Ralf Hinze * last upload 2008 * no test suite (but small commented out QC properties), no benchmarks * no code repository - fingertree-psqueue (http://hackage.haskell.org/package/fingertree-psqueue-0.3) * last upload 2011 * no tests, no benchmarks * no code repository - queuelike (http://hackage.haskell.org/package/queuelike-1.0.9) * last upload 2009 * no tests, no benchmarks * no code repository Benchmarks ---------- Unfortunately, none of them had tests, code in repositories or any indication about their real-world performance, so I made some criterion benchmarks. You can find them here: https://github.com/nh2/psqueue-benchmarks Graphs: http://htmlpreview.github.com/?https://raw.github.com/nh2/psqueue-benchmarks... Benchmark results ----------------- * PSQueue throws a stack space overflow if you try to put in 100000 Ints * PSQueue suffers from some significant worst case in terms of queue creation, sometimes creating a queue from random numbers just takes 5 times longer (1st graph). This only happens sometimes (despite Criterion) * queuelike creation is instant - it seems to work around my benchmark somehow * converting a queuelike queue to a list surprisingly takes 10 times longer than with the other packages * in terms of average performance, the three are quite close to each other (apart from the point above). queuelike seems fastest, fingertree-psqueue is second and PSQueue slowest, with a difference of +30% to the next one My questions to the maintainers ------------------------------- @Scott: Do you have an idea why PSQueue stack overflows? @Louis: Why did you switch from queuelike to pqueue? Could you put the code up somewhere manageable (repo)? Is it possible to make pqueue a full pSqueue implementation? Niklas
Bearing in mind that I haven't looked at this in several years...
Why did you switch from queuelike to pqueue?
Because I liked the API better?
Could you put the code up somewhere manageable (repo)?
I had it up on darcs, but since that's not there any more, I don't have any more source history than you do.
Is it possible to make pqueue a full pSqueue implementation? Not without rewriting the API and data structure...or, equivalently, just starting from scratch.
Louis Wasserman wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis On Thu, Mar 28, 2013 at 10:20 PM, Niklas Hambüchen <mail@nh2.me> wrote:
(This is a slightly detailed email. If you are the maintainer of one of the packages benchmarked here, you might want to read it though.)
Today I was looking for a Priority Queue that also allows a delete operation (some call this a "Priority Search Queue").
I found
http://stackoverflow.com/questions/6976559/comparison-of-priority-queue-impl... and after looking at the 10 queue alternatives, I got to the following conclusions:
* Only 3 of them allow to delete entries (are p*s*queues) * Most of them are outdated or at least unmaintained for the last 3-5 years * There was an effort to get a priority queue into containers (see the stackoverflow link), but it was not agreed on * Those efforts were driven by Louis Wasserman, who wrote one of the 3 psqueues (queuelike), but now only maintains a non-ps-queue (pqueue) that seems to be the most popular priority queue implementation
PSQueue implementations -----------------------
The three packages that are psqueues are:
- PSQueue (http://hackage.haskell.org/package/PSQueue-1.1) * original implementation from paper of Ralf Hinze * last upload 2008 * no test suite (but small commented out QC properties), no benchmarks * no code repository
- fingertree-psqueue (http://hackage.haskell.org/package/fingertree-psqueue-0.3) * last upload 2011 * no tests, no benchmarks * no code repository
- queuelike (http://hackage.haskell.org/package/queuelike-1.0.9) * last upload 2009 * no tests, no benchmarks * no code repository
Benchmarks ----------
Unfortunately, none of them had tests, code in repositories or any indication about their real-world performance, so I made some criterion benchmarks. You can find them here:
https://github.com/nh2/psqueue-benchmarks Graphs:
http://htmlpreview.github.com/?https://raw.github.com/nh2/psqueue-benchmarks...
Benchmark results -----------------
* PSQueue throws a stack space overflow if you try to put in 100000 Ints
* PSQueue suffers from some significant worst case in terms of queue creation, sometimes creating a queue from random numbers just takes 5 times longer (1st graph). This only happens sometimes (despite Criterion)
* queuelike creation is instant - it seems to work around my benchmark somehow
* converting a queuelike queue to a list surprisingly takes 10 times longer than with the other packages
* in terms of average performance, the three are quite close to each other (apart from the point above). queuelike seems fastest, fingertree-psqueue is second and PSQueue slowest, with a difference of +30% to the next one
My questions to the maintainers -------------------------------
@Scott: Do you have an idea why PSQueue stack overflows?
@Louis: Why did you switch from queuelike to pqueue? Could you put the code up somewhere manageable (repo)? Is it possible to make pqueue a full pSqueue implementation?
Niklas
Hey Louis, I think that queuelike is still a nice psqueue implementation (and I personally don't dislike the api), so may I ask two more questions: * Do you have any clue why toList is 10 times slower than in the other implementation? It is based on extract, and queuelike's extract is very fast compared to the others ... that is weird. * What could I do such that queuelike creation is not measured as instant? Using whnf does not seem to be enough. Thank you Niklas
I don't remember the answer to either of your questions, I'm afraid -- queuelike was last updated in 2009 (!), and that's really the last time I looked at it. That said, I'm not sure I follow how queuelike is a psqueue at all as opposed to a pqueue? Louis Wasserman wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis On Fri, Mar 29, 2013 at 3:17 PM, Niklas Hambüchen <mail@nh2.me> wrote:
Hey Louis,
I think that queuelike is still a nice psqueue implementation (and I personally don't dislike the api), so may I ask two more questions:
* Do you have any clue why toList is 10 times slower than in the other implementation? It is based on extract, and queuelike's extract is very fast compared to the others ... that is weird.
* What could I do such that queuelike creation is not measured as instant? Using whnf does not seem to be enough.
Thank you Niklas
On 30/03/13 06:44, Louis Wasserman wrote:
That said, I'm not sure I follow how queuelike is a psqueue at all as opposed to a pqueue?
Louis, you are actually right. I was tricked by the delete function, which takes only the queue, not the key, so it simply pops the top - queuelike is not a psqueue.
participants (2)
-
Louis Wasserman -
Niklas Hambüchen