[Haskell] performance tuning Data.FiniteMap

[S. Alexander Jacobson]

I believe FiniteMap works by representing the data
in binary trees.  It is therefore O(log2(n)) to
read and update.

However, if my application reads many more times
than it writes, then perhaps I can get a
substantial performance boost by increasing the
branch factor on the tree.  For example, if each
node was an array of 256 elements, reads would be
O(log256(n)), a 128x improvement!

Note: I don't know what sort of penalty writes
would have.  In theory they would be 128x as
expensive as well because each update would
require copying 256 branches.  However, in
practice, I would bet that memcpy of 1k blocks can
be optimized at the CPU so much that the
difference might not be meaningful.

Questions:
Am I interpreting the performance issues correctly?
Does FiniteMap used Arrays, Lists, or Algebraic Types?
If arrays, is there an easy way to change the branching in FiniteMap?
Do Haskell arrays do fast memcpy for small arrays?

-Alex-

_________________________________________________________________
S. Alexander Jacobson                  mailto:me at alexjacobson.com
tel:917-770-6565                       http://alexjacobson.com