[Haskell-cafe] Performance of functional priority queues

[Matt Morrow]

On 12/25/09, Matt Morrow <moonpatio at gmail.com> wrote:
> On 12/23/09, Jon Harrop <jon at ffconsultancy.com> wrote:
>> And your results above indicate that the fastest imperative heap is over
>> 3x
>> faster than the fastest functional heap?

Also, I've now added you to (1) my list of people never to hire to
perform statistical computations for me where i'm looking for what's
actually going on, (2) my list of people to hire when i need to
mislead *via* statistics. However, (2) is pending verification that
you didn't actually think that. I can't imagine you did though. :)

Cheers,
Matt


>
> It's saying that
>
>   (1) Using an imprecise an
> inefficient-relative-to-a-accurate-GC-that-doesn't-
>
> have-to-assume-the-entire-memory-space-is-live-then-find-what's-dead
>         is a recipe for inefficiency.
>   (2) And (1) even more so when you're comparing it to the same language
> with
>        manual memory management and zero GC overhead.
>
>   (from here on out I disregard the C numbers (i like C, too))
>
>   (3) So now, it's saying that (given this sample, yada yada) among
> languages
>         where this comparison is possible (i.e. the mutable version
> still has the GC running)
>         the functional version is on average 1.8 times slower.
>
>           ghci> ((126/70) + (290/150) + (1895/1123)) / 3
>           1.8069258929454834
>
> Matt
>
>> 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.
>