[Haskell-beginners] Re: Is Haskell for me?

Jon Harrop jon at ffconsultancy.com
Sat Nov 21 13:02:33 EST 2009

On Saturday 21 November 2009 11:56:09 Ben Lippmeier wrote:
> Hmm. I'd be careful about conflating algorithmic complexity with memory
> management issues.

No need. Just look at how badly the performance scales for Haskell vs other 
languages. For example, inserting 1-16 million floating point key/values into 
a hash table:

          Haskell         OCaml         F#
 1M:   3.198s   1.0x   1.129s  1.0x  0.080s  1.0x
 2M:   8.498s   2.7x   2.313s  2.0x  0.138s  1.7x
 4M:  25.697s   8.0x   4.567s  4.0x  0.281s  3.5x
 8M:  97.994s  30.6x  10.450s  9.3x  0.637s  8.0x
16M: 388.080s 121.4x  23.261s 20.6x  1.338s 16.7x

Note that Haskell is 290x slower than F# on that last test.

In practice, you would turn to a purely functional dictionary in Haskell based 
upon balanced binary trees in order to work around this long-standing bug in 
the GC but those trees incur O(log n) indirections and typically run orders 
of magnitude slower than a decent hash table.

Suffice to say, Haskell is nowhere near being in the ballpark of C++'s 
performance for basic functionality like dictionaries and sorting.

> By the above reasoning, if I were to run any program 
> using arrays on a system with a two space garbage collector (which copies
> all live objects during each GC) I could say the worst case algorithmic
> complexity was O(n). That doesn't sound right.

Can you write a program that demonstrates this effect as I did?

> I could take this further and say that in a virtual memory system, there is
> a chance that the whole heap gets copied to the disk and back between each
> array update.

Can you write a program that demonstrates this effect as I did?

Dr Jon Harrop, Flying Frog Consultancy Ltd.

More information about the Beginners mailing list