[Haskell] performance tuning Data.FiniteMap
simonpj at microsoft.com
Wed Feb 25 08:39:29 EST 2004
| > (//) 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
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
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.
More information about the Haskell