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

[Louis Wasserman]

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 at gmail.com
http://profiles.google.com/wasserman.louis


On Thu, Mar 28, 2013 at 10:20 PM, Niklas Hambüchen <mail at 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-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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell/attachments/20130329/941946e6/attachment.htm>