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:[EMAIL PROTECTED] tel:917-770-6565 http://alexjacobson.com _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
