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.lo...@gmail.com http://profiles.google.com/wasserman.louis On Thu, Mar 28, 2013 at 10:20 PM, Niklas Hambüchen <m...@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 >
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
