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

Niklas Hambüchen mail at nh2.me
Fri Mar 29 06:20:51 CET 2013

(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
and after looking at the 10 queue alternatives, I got to the following

* 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
  * 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


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:


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

* 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

Do you have an idea why PSQueue stack overflows?

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?


More information about the Haskell mailing list