Hello! I am using the FiniteMap datatype and since Haskell never modifies variables but rather copies them (?) I wonder what the performance of the FiniteMap type is in Haskell. Lookup is of course done in O(log n) but is insertion done in O(n) or O(log n)? For example, does the function addToFM :: Ord key => FiniteMap key elt -> key -> elt -> FiniteMap key elt belong to O(n) or O(log n) (where n is the size of the map) ? If it belongs to O(n), aren't the maps really really useless? If it belongs to O(log n), how is this achieved? (my guess is that it is O(n) of course : ) Best regards, Magnus Lindberg
On Fri, 2003-02-07 at 21:25, Magnus Lindberg wrote:
I am using the FiniteMap datatype and since Haskell never modifies variables but rather copies them (?) I wonder what the performance of the FiniteMap type is in Haskell. Lookup is of course done in O(log n) but is insertion done in O(n) or O(log n)?
For example, does the function
addToFM :: Ord key => FiniteMap key elt -> key -> elt -> FiniteMap key elt
belong to O(n) or O(log n) (where n is the size of the map) ?
Insertion seems to take O(log n) time (measure it!). This is because that you don't need to copy all the nodes in the tree -- just the nodes whose values or descendants have changed, which is (roughly*) the path from the root of the tree to the insertion point. The subtrees that have not changed are safe to share even if you hold on to the old tree, because you know they'll never be modified. Cheers, -- Mieszko *modulo rotations required to keep the tree approximately balanced, but those are along the insertion path too.
Dear Magnus,
I wonder what the performance of the FiniteMap type is in Haskell. Lookup is of course done in O(log n) but is insertion done in O(n) or O(log n)? ... If it belongs to O(n), aren't the maps really really useless? If it belongs to O(log n), how is this achieved? (my guess is that it is O(n) of course : )
I have once been thinking the same, but you can rest assured, insert is O(log n) (for a balanced tree map implementation). A pure language must indeed copy its values (since it is a new one) but it can also *share* values that stay the same. In the case of the balanced tree, the "path" to the inserted node will be copied since they consist of new and different nodes, but all the subtrees of this path stay the same and will be shared among all new insertions. It is rather mind-boggling when you start thinking about how the actual heap looks after a while, but fortunately, you never have to think about that in Haskell :-) (btw. This is really fun to watch if you got a tool like the graphical Hood). All the best, Daan. ps. I have written a fairly extensive (and documented) data structure library called DData that has efficient Maps, Sets, Bags etc. Also works well with Hugs and other haskell98 compilers. http://www.cs.uu.nl/~daan/ddata.html
For example, does the function
addToFM :: Ord key => FiniteMap key elt -> key -> elt -> FiniteMap key elt
belong to O(n) or O(log n) (where n is the size of the map) ?
If it belongs to O(n), aren't the maps really really useless? If it belongs to O(log n), how is this achieved? (my guess is that it is O(n) of course : )
Best regards, Magnus Lindberg _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Hello again and thanks for your answers, Daan an Mieszko. Now, Haskell has a garbage collector, so Haskell must know how many pointers there are to all objects in the heap (or?). Then, if a finite map for example only has one single pointer to it, then it ought to be all right to modify the finite map (or whatever datastructure we are considering), I mean really modify the map without making any copies, just like in imperative languages. Perhaps there might be pointers to nodes inside the tree and I guess that could complicate the matter somewhat. But for Haskell arrays it ought to be possible to really modify the array if it is used by only one pointer ? Are such optimizations possible, and if they are, are they already implemented in for example GHC ? Or am I wrong somewhere ? Best regards, Magnus Lindberg
Perhaps you should look at the Clean languages, which is similar to Haskell, but has a feature called "uniqueness typing". Using the type system, you can figure out the information that you are asking for and as far as I know, their implementation is optimzed in the manner you want. In fact, their whole IO system is built around that idea. Have a look at http://www.cs.kun.nl/~clean/ -Peter ML> Now, Haskell has a garbage collector, so Haskell must know how many ML> pointers there are to all objects in the heap (or?). Then, if a finite map ML> for example only has one single pointer to it, then it ought to be all ML> right to modify the finite map (or whatever datastructure we are ML> considering), I mean really modify the map without making any copies, just ML> like in imperative languages. Perhaps there might be pointers to nodes ML> inside the tree and I guess that could complicate the matter somewhat. But ML> for Haskell arrays it ought to be possible to really modify the array if ML> it is used by only one pointer ? ML> Are such optimizations possible, and if they are, are they already ML> implemented in for example GHC ? Or am I wrong somewhere ?
participants (4)
-
Daan Leijen -
Magnus Lindberg -
Mieszko Lis -
Peter Thiemann