[Haskell] performance tuning Data.FiniteMap

[Simon Peyton-Jones]

| > (//) is very slow 
| Is that inherent in Haskell (or laziness) or is it
| just an artifact of the current GHC
| implementation?  Would the problem be solved by
| making my arrays strict or by using Unboxed
| arrays?  Is there a faster array implementation
| around?

It's slow because it costs O(n) for what someone might expect to be an
O(1) operation.  Since the compiler does not know whether the 'old'
array is going to be re-used for something else, it's forced to make a
copy of the array, modifying the specified slot(s).

Yes, the implementation could use memcpy, but it's still ridiculously
expensive to copy a 10,000 word array to only modify one word.  (GHC
does not use memcpy -- it generates an explicit loop instead -- but it
could if we added a new primop to encapsulate memcpy.)

Advanced compiler optimisations might help, by detecting when the old
copy isn't needed, but they are much much harder in a lazy language, and
fragile to small program changes to boot.  GHC makes no such attempt.
An alternative is to put single-threaded-ness into the type system, as
Clean does.

Haskell's current story is to use O(log n) structures such as trees --
or to use a state monad.


| PS I'm sorry if these are obvious beginner
| questions.  I would really realy like to use
| Haskell for a production web application and am
| trying to work through the various issues. It is
| hard to find information on these sorts of things
| and the absense of field testing means you just
| have to ask these questions in advance.

You should feel no need to apologise.  Our community *needs* people like
you, who are using Haskell for real applications.  That's how we'll
learn "where the shoe pinches".   Ask away.

Simon