I actually found a (potential) problem with the GHC implementation.
See here:
https://github.com/nh2/psqueue-benchmarks/blob/db89731c5b4bdd2ff2ef81022a65f894036d8453/QueueBenchmark.hs#L44
If I fromList 100 entries into the queue, it stack space overflows.
I got the same problem with the
Does not compiles under ghc 7.6.2
Date: Sat, 13 Apr 2013 11:09:13 +0800
From: m...@nh2.me
To: k...@iij.ad.jp
CC: haskell-cafe@haskell.org
Subject: Re: [Haskell-cafe] ANN: psqueue-benchmarks - benchmarks of priority
queue implementations
I actually found a (potential) problem with the GHC
Hi,
See here:
https://github.com/nh2/psqueue-benchmarks/blob/db89731c5b4bdd2ff2ef81022a65f894036d8453/QueueBenchmark.hs#L44
If I fromList 100 entries into the queue, it stack space overflows.
Are you sure that this is a bug of GHC PSQ?
I think that replicateM _GHC_CRASH_N causes
On 30/03/13 06:44, Louis Wasserman wrote:
That said, I'm not sure I follow how queuelike is a
psqueue at all as opposed to a pqueue?
Louis,
you are actually right. I was tricked by the delete function, which
takes only the queue, not the key, so it simply pops the top - queuelike
is not a
@Cale, do you have a repo of fingertree-psqueue around?
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Hi Niklas,
* PSQueue throws a stack space overflow if you try to put in 10
* Ints
A slightly different implementation is used in GHC:
https://github.com/ghc/packages-base/blob/master/GHC/Event/PSQ.hs
Could you test it? If this code also has the same problem, I need to
fix it.
I do not know why it overflows. It's been a while, but isn't the answer
usually too much laziness? Maybe try changing the foldr in fromList to
foldr'? I would try it out quickly but do not have ghc installed on any
computers here.
I am happy start a repo for this library, but there is not much
Hey Scott,
I quickly tried your suggestion, plugging in foldr' from Data.Foldable
and sprinkling a few seqs in some places, but it doesn't help the stack
overflow.
On Fri 29 Mar 2013 16:23:55 GMT, Scott Dillard wrote:
I do not know why it overflows. It's been a while, but isn't the
answer
Hey Kazu,
I added GHC's PSQ to the benchmark, the new figures are on
http://htmlpreview.github.com/?https://raw.github.com/nh2/psqueue-benchmarks/master/report.html
No, it does not stack overflow, and it seems to perform slightly better
than the other implementations; it also doesn't suffer from
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
Hey Louis,
I think that queuelike is still a nice psqueue implementation (and I
personally don't dislike the api), so may I ask two more questions:
* Do you have any clue why toList is 10 times slower than in the other
implementation? It is based on extract, and queuelike's extract is very
fast
I don't remember the answer to either of your questions, I'm afraid --
queuelike was last updated in 2009 (!), and that's really the last time I
looked at it. That said, I'm not sure I follow how queuelike is a psqueue
at all as opposed to a pqueue?
Louis Wasserman
wasserman.lo...@gmail.com
Hi Niklas,
No, it does not stack overflow, and it seems to perform slightly better
than the other implementations; it also doesn't suffer from the toList
slowness problem as does listlike.
Thanks. It's nice.
However, it is probably not as generally usable as it hardcodes the
priorities to
(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
14 matches
Mail list logo