[Haskell-cafe] Performance of functional priority queues

[Daniel Peebles]

He sounds like a bit of a troll, but I agree the question itself is an
interesting one and I'd be interested to see if anyone has an "answer"
(although given the lack of criteria, it'll be hard to address his
points exactly)

On Tue, Jun 16, 2009 at 6:50 PM, Richard O'Keefe<ok at cs.otago.ac.nz> wrote:
>
> 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.
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>