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

[Jon Harrop]

On Saturday 21 November 2009 18:57:21 you wrote:
> 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,

Not at all, that is a perfectly reasonable concern but I did already try to 
address it in my previous post:

> > 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.

For example, the following Haskell program builds a purely functional 
Data.Map:

module Main where

import Prelude hiding (lookup)
import Data.Map (empty, insert, lookup, size)

n = 1000000

build m 0 = m
build m n = build (insert x (1.0 / x) m) (n-1)
  where x = fromIntegral n :: Double

main = do
  let 
      m = build empty n
      (Just v) = lookup 100 m

  print $ size m
  print v

Running this program with different "n" gives:

        Data.Map
 1M:  2.797s  1.0x
 2M:  6.090s  2.2x
 4M: 14.226s  5.1x
 8M: 28.449s 10.2x
16M: 83.171s 29.7x

This is several times faster than Haskell's Data.Hashtable (because of the 
long-standing bug in their GC that I described) and is scaling better. 
However, if you compare with the timings I gave before:

      Data.Hashtable       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

you'll see that the absolute performance of this idiomatic Haskell solution is 
still absolutely awful: consistently about 50x slower than the F#.

This is also true in the context of sorting: Haskell's standard library 
routines for sorting are orders of magnitude slower than those found in most 
other compiled languages.

Suffice to say, idiomatic Haskell is also nowhere near being in the same 
ballpark as C++ with respect to performance. Realistically, with enough 
expertise you should be able to optimize most of your Haskell programs to 
beat Python's performance but there are some important cases where you will 
not even be able to do that.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e