[Haskell-cafe] Performance of functional priority queues
ok at cs.otago.ac.nz
Tue Jun 16 18:50:45 EDT 2009
On 15 Jun 2009, at 7:54 pm, Luke Palmer wrote:
> One of the correspondents in that thread claims that it is
> provably impossible to have an efficient priority queue implementation
> without mutability.
> If he so claims, maybe you can challenge him by asking for a proof?
He claims that the burden is on my end.
> Such a proof would probably only involve asymptotics, since it's
> very hard to prove anything when actual raw speed is involved.
> If that's the case, you can use Okasaki to back yourself up (or
> back him up; I am not familiar with the results in this area).
He is aware of Okasaki's book, about which he was somewhat offensive.
One thing that's clear is that he _isn't_ talking about asymptotics.
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.
More information about the Haskell-Cafe