[Haskell-cafe] Performance of functional priority queues
jon at ffconsultancy.com
Fri Dec 25 13:10:49 EST 2009
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
> 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
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#.
Dr Jon Harrop, Flying Frog Consultancy Ltd.
More information about the Haskell-Cafe