[Haskell-cafe] Performance of functional priority queues

[Jon Harrop]

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.

And your results above indicate that the fastest imperative heap is over 3x 
faster than the fastest functional heap?

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