Re: [Haskell-cafe] Performance of functional priority queues

On Friday 25 December 2009 06:09:55 Matt Morrow wrote:

On 12/23/09, Jon Harrop 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