[Haskell-cafe] ANN: psqueue-benchmarks - benchmarks of priority queue implementations

[Niklas Hambüchen]

(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-implementations-in-haskell
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/master/report.html


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