[Haskell-cafe] Performance of functional priority queues

[Jon Harrop]

On Friday 25 December 2009 06:09:55 Matt Morrow wrote:
> On 12/23/09, Jon Harrop <jon at ffconsultancy.com> wrote:
> > And your results above indicate that the fastest imperative heap is over
> > 3x faster than the fastest functional heap?
>
> It's saying that
>
>   (1) Using an imprecise an
> inefficient-relative-to-a-accurate-GC-that-doesn't-
> have-to-assume-the-entire-memory-space-is-live-then-find-what's-dead is a
> recipe for inefficiency.

How is that relevant to what I wrote?

>   (2) And (1) even more so when you're comparing it to the same language
> with manual memory management and zero GC overhead.

There should be no GC overhead in the imperative case anyway.

>   (from here on out I disregard the C numbers (i like C, too))
>
>   (3) So now, it's saying that (given this sample, yada yada) among
> languages where this comparison is possible (i.e. the mutable version still
> has the GC running)
>         the functional version is on average 1.8 times slower.
>
>           ghci> ((126/70) + (290/150) + (1895/1123)) / 3
>           1.8069258929454834

You're assuming that other languages will not be a lot faster than Java even 
though C already is.

> > On Tuesday 16 June 2009 23:50:45 Richard O'Keefe wrote:
> >> I've now done some benchmarks myself in C, Java, and Smalltalk,
> >> comparing "imperative" versions of leftist heaps with "functional" ones.
> >> For what it's worth, on a 2.16GHz Intel Core 2 Duo Mac, the
> >> coefficient in front of the log(n) part was
> >>
> >>                  C       Java    ST(A)   ST(B)
> >> "Imperative"    40       70     150     1123
> >> "Functional"   240      126     290     1895
> >>
> >> where ST(A) was a native-code Smalltalk and ST(B) a byte-code one.
> >> The C/Functional case used the Boehm collector, untuned.
> >> Times are in nanoseconds.  Values of n ranged from 2 to 100; the
> >> correspondent was saying that small sizes were important.
> >>
> >> It seems that a factor of 2 for *this* problem is credible;
> >> a factor of 10 is not.

Post the code and I'll port it to F#.

Merry Christmas,
-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e