<div dir="ltr">Bearing in mind that I haven&#39;t looked at this in several years...<div><br></div><div>&gt; <span style="font-family:arial,sans-serif;font-size:13px">Why did you switch from queuelike to pqueue?</span></div>

<div><span style="font-family:arial,sans-serif;font-size:13px"><br></span></div><div style><span style="font-family:arial,sans-serif;font-size:13px">Because I liked the API better?</span></div><div style><span style="font-family:arial,sans-serif;font-size:13px"><br>

</span></div><div style><span style="font-family:arial,sans-serif;font-size:13px">&gt; </span><span style="font-family:arial,sans-serif;font-size:13px">Could you put the code up somewhere manageable (repo)?</span></div><div style>

<span style="font-family:arial,sans-serif;font-size:13px"><br></span></div><div style><font face="arial, sans-serif">I had it up on darcs, but since that&#39;s not there any more, I don&#39;t have any more source history than you do.</font></div>

<div style><font face="arial, sans-serif"><br></font></div><div style><font face="arial, sans-serif">&gt; </font><span style="font-family:arial,sans-serif;font-size:13px">Is it possible to make pqueue a full pSqueue implementation?</span></div>

<div style><span style="font-family:arial,sans-serif;font-size:13px">Not without rewriting the API and data structure...or, equivalently, just starting from scratch.</span></div><div style><font face="arial, sans-serif"><br>

</font></div></div><div class="gmail_extra"><br clear="all"><div>Louis Wasserman<br><a href="mailto:wasserman.louis@gmail.com">wasserman.louis@gmail.com</a><br><a href="http://profiles.google.com/wasserman.louis">http://profiles.google.com/wasserman.louis</a></div>


<br><br><div class="gmail_quote">On Thu, Mar 28, 2013 at 10:20 PM, Niklas Hambüchen <span dir="ltr">&lt;<a href="mailto:mail@nh2.me" target="_blank">mail@nh2.me</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

(This is a slightly detailed email. If you are the maintainer of one of<br>
the packages benchmarked here, you might want to read it though.)<br>
<br>
<br>
Today I was looking for a Priority Queue that also allows a delete<br>
operation (some call this a &quot;Priority Search Queue&quot;).<br>
<br>
I found<br>
<a href="http://stackoverflow.com/questions/6976559/comparison-of-priority-queue-implementations-in-haskell" target="_blank">http://stackoverflow.com/questions/6976559/comparison-of-priority-queue-implementations-in-haskell</a><br>


and after looking at the 10 queue alternatives, I got to the following<br>
conclusions:<br>
<br>
* Only 3 of them allow to delete entries (are p*s*queues)<br>
* Most of them are outdated or at least unmaintained for the last 3-5 years<br>
* There was an effort to get a priority queue into containers (see the<br>
stackoverflow link), but it was not agreed on<br>
* Those efforts were driven by Louis Wasserman, who wrote one of the 3<br>
psqueues (queuelike), but now only maintains a non-ps-queue (pqueue)<br>
that seems to be the most popular priority queue implementation<br>
<br>
<br>
PSQueue implementations<br>
-----------------------<br>
<br>
The three packages that are psqueues are:<br>
<br>
- PSQueue (<a href="http://hackage.haskell.org/package/PSQueue-1.1" target="_blank">http://hackage.haskell.org/package/PSQueue-1.1</a>)<br>
  * original implementation from paper of Ralf Hinze<br>
  * last upload 2008<br>
  * no test suite (but small commented out QC properties), no benchmarks<br>
  * no code repository<br>
<br>
- fingertree-psqueue<br>
(<a href="http://hackage.haskell.org/package/fingertree-psqueue-0.3" target="_blank">http://hackage.haskell.org/package/fingertree-psqueue-0.3</a>)<br>
  * last upload 2011<br>
  * no tests, no benchmarks<br>
  * no code repository<br>
<br>
- queuelike (<a href="http://hackage.haskell.org/package/queuelike-1.0.9" target="_blank">http://hackage.haskell.org/package/queuelike-1.0.9</a>)<br>
  * last upload 2009<br>
  * no tests, no benchmarks<br>
  * no code repository<br>
<br>
<br>
Benchmarks<br>
----------<br>
<br>
Unfortunately, none of them had tests, code in repositories or any<br>
indication about their real-world performance, so I made some criterion<br>
benchmarks. You can find them here:<br>
<br>
<a href="https://github.com/nh2/psqueue-benchmarks" target="_blank">https://github.com/nh2/psqueue-benchmarks</a><br>
Graphs:<br>
<a href="http://htmlpreview.github.com/?https://raw.github.com/nh2/psqueue-benchmarks/master/report.html" target="_blank">http://htmlpreview.github.com/?https://raw.github.com/nh2/psqueue-benchmarks/master/report.html</a><br>


<br>
<br>
Benchmark results<br>
-----------------<br>
<br>
* PSQueue throws a stack space overflow if you try to put in 100000 Ints<br>
<br>
* PSQueue suffers from some significant worst case in terms of queue<br>
creation, sometimes creating a queue from random numbers just takes 5<br>
times longer (1st graph). This only happens sometimes (despite Criterion)<br>
<br>
* queuelike creation is instant - it seems to work around my benchmark<br>
somehow<br>
<br>
* converting a queuelike queue to a list surprisingly takes 10 times<br>
longer than with the other packages<br>
<br>
* in terms of average performance, the three are quite close to each<br>
other (apart from the point above). queuelike seems fastest,<br>
fingertree-psqueue is second and PSQueue slowest, with a difference of<br>
+30% to the next one<br>
<br>
<br>
My questions to the maintainers<br>
-------------------------------<br>
<br>
@Scott:<br>
Do you have an idea why PSQueue stack overflows?<br>
<br>
@Louis:<br>
Why did you switch from queuelike to pqueue?<br>
Could you put the code up somewhere manageable (repo)?<br>
Is it possible to make pqueue a full pSqueue implementation?<br>
<span class="HOEnZb"><font color="#888888"><br>
Niklas<br>
</font></span></blockquote></div><br></div>