Feedback request: priority queues in containers

Louis Wasserman wasserman.louis at gmail.com
Wed Mar 17 10:44:41 EDT 2010


I'd concur, but I haven't been able to install Criterion yet.  =(

Let me rewrite things with BenchPress, and see what happens.

I should add, though, that I think C *is* as optimized as D.  In particular,
some of the tricks that worked with D only worked because of the way the
spines were arranged.  (For instance, unrolling the children incrementally
was a trick that really worked because the children and the trees in the
spine were lined up, which meant that it needed the Skip combinator.)

Simon: I wasn't sure what to do there, because e.g. Data.Map, I think, is
strict that way.  I prefer the lazy way, though, so I certainly don't mind
keeping it lazy =)

Louis Wasserman
wasserman.louis at gmail.com
http://profiles.google.com/wasserman.louis


On Wed, Mar 17, 2010 at 4:04 AM, Johan Tibell <johan.tibell at gmail.com>wrote:

> I really recommend using Criterion to get rid of some of the many
> problems associated with benchmarking.
>
> http://hackage.haskell.org/package/criterion
>
> Cheers,
> Johan
>
> On Wed, Mar 17, 2010 at 9:35 AM, Jim Apple
> <jbapple+haskell-lib at gmail.com <jbapple%2Bhaskell-lib at gmail.com>> wrote:
> > I should also note that these timings are quite temperamental on my
> > computer; using profiling or removing the performGC calls can make C
> > faster than D and B faster than A.
> >
> >> Binomial priority queue timings (in milliseconds, averaged over 20 runs)
> >> A: Simple Brodal-Okasaki list implementation:
> >> 199.3697
> >> B: Wasserman nested type implementation, simple functions:
> >> 235.0143
> >> C: Wasserman's 'Quick' list implementation:
> >> 179.7227
> >> D: Wasserman's proposed nested type implementation:
> >> 163.47515
> >>
> >> D is still the fastest. However, A is a good bit faster than B. Is it
> >> possible that C would show a similar advantage over D if it were
> >> optimized as carefully as D?
> > _______________________________________________
> > Libraries mailing list
> > Libraries at haskell.org
> > http://www.haskell.org/mailman/listinfo/libraries
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20100317/adf73dc5/attachment.html


More information about the Libraries mailing list