[Haskell-cafe] Performance of functional priority queues

[Richard O'Keefe]

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.