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

Nathan M. Holden nathanmholden at gmail.com
Sat Nov 21 13:57:21 EST 2009


I'm not a Haskell expert-- in fact, I'm a beginner, and that's why I'm here, 
but I read your blog post on the subject of this hash table program, and it 
seems to me from reading the comments in reply that you're just here trolling, 
because you're using an algorithm that is fundamentally not purely functional, 
and of course that's going to be slower, just like asking Joel Zumaya to pitch 
left handed.

If you were being honest about your complaint, you'd make an apples-to-apples 
comparison, and a number of commenters on your blog have proposed 
implementations that perform much better than your example.

Sorry if I'm just being a jerk,
Nathan M. Holden,
Haskell Beginner

On Saturday 21 November 2009 12:55:03 pm beginners-request at haskell.org wrote:
> Message: 4
> Date: Sat, 21 Nov 2009 18:02:33 +0000
> From: Jon Harrop <jon at ffconsultancy.com>
> Subject: Re: [Haskell-beginners] Re: Is Haskell for me?
> To: Ben Lippmeier <ben.lippmeier at anu.edu.au>
> Cc: beginners <beginners at haskell.org>
> Message-ID: <200911211802.33494.jon at ffconsultancy.com>
> Content-Type: text/plain;  charset="iso-8859-1"
> 
> 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?


More information about the Beginners mailing list