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@alexjacobson.com tel:917-770-6565 http://alexjacobson.com
S. Alexander Jacobson wrote:
Does FiniteMap used Arrays, Lists, or Algebraic Types?
when in doubt, RTFC: http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/libraries/base/Data/Finite... data FiniteMap key elt = EmptyFM | Branch key elt -- Key and elt stored here IF_GHC(Int#,Int{-STRICT-}) -- Size >= 1 (FiniteMap key elt) -- Children (FiniteMap key elt) the hugs distribution even says where this comes from: This code is derived from that in the paper: \begin{display} S Adams "Efficient sets: a balancing act" Journal of functional programming 3(4) Oct 1993, pp553-562 \end{display} -- -- Johannes Waldmann, Tel/Fax: (0341) 3076 6479 / 6480 -- ------ http://www.imn.htwk-leipzig.de/~waldmann/ ---------
"S. Alexander Jacobson" <alex@alexjacobson.com> writes:
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!
I'm probably missing something, but how can you do this for general Ord types? Don't you need a linear search through the array to find the correct subtree? -kzm -- If I haven't seen further, it is by standing in the footprints of giants
as a tangent, for absurdly fast and optimal (optimized to the cache line) maps see http://judy.sourceforge.net/ the algorithms behind them are very cool. see http://judy.sourceforge.net/downloads/10minutes.htm for a quick discussion of why they are fast (there is a fewhundred page book too) heh. although I doubt any of the optimizations will be implementable in haskell any time soon. not ghc's Haskell# even... John -- --------------------------------------------------------------------------- John Meacham - California Institute of Technology, Alum. - john@foo.net ---------------------------------------------------------------------------
participants (4)
-
Johannes Waldmann -
John Meacham -
Ketil Malde -
S. Alexander Jacobson