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

Johan Tibell johan.tibell at gmail.com
Fri Mar 29 19:35:42 CET 2013


I had a 5 second look at the PSQueue implementation and here's what I got
so far:

 * fromList should use foldl'.
 * LTree should be spine strict (i.e. strict in the (LTree k p) fields).
 * Winner should be strict in the (LTree k p) field and probably in all
other fields as well.

This is a nice example showing that strict fields is the right default. If
fields need to be lazy there should ideally be a comment explaining why
that is needed (e.g. in the case of finger trees and lists).


On Fri, Mar 29, 2013 at 9:53 AM, Niklas Hambüchen <mail at nh2.me> wrote:

> 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 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
> > history to import so anyone else may do it. I'm not sure how hackage
> > upload permissions work... I guess I just change the maintainer field
> > in the .cabal file from myself to someone else...? Any volunteers?
> >
> >
> >
> >
> > On Thu, Mar 28, 2013 at 11:16 PM, Kazu Yamamoto <kazu at iij.ad.jp
> > <mailto:kazu at iij.ad.jp>> wrote:
> >
> >     Hi Niklas,
> >
> >     > * PSQueue throws a stack space overflow if you try to put in 100000
> >     > * 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.
> >
> >     --Kazu
> >
> >
>
> _______________________________________________
> Haskell mailing list
> Haskell at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell/attachments/20130329/90173643/attachment.htm>


More information about the Haskell mailing list