[Haskell-cafe] Performance of functional priority queues
jon at ffconsultancy.com
Wed Dec 23 19:55:11 EST 2009
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.
More information about the Haskell-Cafe