Destructive updates to plain ADTs
Hi all, is there any way to perform a destructive update on a plain ADT? Imagine I have a simple data Tree a = Nil | Node a (Tree a) (Tree a) I would like to be able to modify right subtree of an existing tree. I can do that for example when using IORefs by changing the datatype to data Tree a = Nil | Node a (IORef (Tree a)) (IORef (Tree a)) and use unsafePerformIO + writeIORef. But the IORefs cause additional complexity when working with the data type. At the moment I am interested in any GHC solution, be it non-portable or version specific. I would like just to run some benchmarks and see the results. Cheers, Milan
On Sun, Sep 9, 2012 at 1:46 AM, Milan Straka
Hi all,
is there any way to perform a destructive update on a plain ADT? Imagine I have a simple data Tree a = Nil | Node a (Tree a) (Tree a) I would like to be able to modify right subtree of an existing tree.
I can do that for example when using IORefs by changing the datatype to data Tree a = Nil | Node a (IORef (Tree a)) (IORef (Tree a)) and use unsafePerformIO + writeIORef. But the IORefs cause additional complexity when working with the data type.
At the moment I am interested in any GHC solution, be it non-portable or version specific. I would like just to run some benchmarks and see the results.
Cheers, Milan
You can do it if you refer to the children using Array#s. That's what I do in unordered-containers to implement a more efficient fromList. For arbitrary field types I don't think there's a way (although it would be useful when birthing persistent data structures). -- Johan
is there any way to perform a destructive update on a plain ADT? Imagine I have a simple data Tree a = Nil | Node a (Tree a) (Tree a) I would like to be able to modify right subtree of an existing tree.
I can do that for example when using IORefs by changing the datatype to data Tree a = Nil | Node a (IORef (Tree a)) (IORef (Tree a)) and use unsafePerformIO + writeIORef. But the IORefs cause additional complexity when working with the data type.
At the moment I am interested in any GHC solution, be it non-portable or version specific. I would like just to run some benchmarks and see the results.
Cheers, Milan
You can do it if you refer to the children using Array#s. That's what I do in unordered-containers to implement a more efficient fromList.
But the Array# adds another level of indirection, which seem wasteful if it has 2 elements. Also creating and cloning array is calling method in runtime, which is another source of (minor) slowdown.
For arbitrary field types I don't think there's a way (although it would be useful when birthing persistent data structures).
That is my reason for asking this. I was hoping for some Addr# trick or something like that. If I understand the GHC runtime correctly, rewriting a pointer in an ADT should not break any garbage collecting and similar. Cheers, Milan
On 09/09/2012 11:03, Milan Straka wrote:
I was hoping for some Addr# trick or something like that. If I understand the GHC runtime correctly, rewriting a pointer in an ADT should not break any garbage collecting and similar.
Don't you need to worry about having something in the old generation suddenly pointing to something in a younger generation? Ganesh
Why modify it instead of creating the new one and let the previous tree get garbage collected?
On Sep 9, 2012, at 12:46 PM, Milan Straka
Hi all,
is there any way to perform a destructive update on a plain ADT? Imagine I have a simple data Tree a = Nil | Node a (Tree a) (Tree a) I would like to be able to modify right subtree of an existing tree.
I can do that for example when using IORefs by changing the datatype to data Tree a = Nil | Node a (IORef (Tree a)) (IORef (Tree a)) and use unsafePerformIO + writeIORef. But the IORefs cause additional complexity when working with the data type.
At the moment I am interested in any GHC solution, be it non-portable or version specific. I would like just to run some benchmarks and see the results.
Cheers, Milan
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On Sun, Sep 9, 2012 at 2:19 AM, MigMit
Why modify it instead of creating the new one and let the previous tree get garbage collected?
You can avoid a bunch of copying and allocation by modifying the nodes in-place. See http://blog.johantibell.com/2012/03/improvements-to-hashmap-and-hashset.html for some numbers. -- Johan
Milan Straka
is there any way to perform a destructive update on a plain ADT?
Hi Milan, perhaps this is a dumb question, but given that you're using a lazy functional language: why do you want to do destructive updates at all? Perhaps you'd be better off using an imperative/object-oriented language? If you're trying to create a static data structure, perhaps the credit card transform is the approach to use?
... I would like just to run some benchmarks and see the results.
Running benchmarks for destructive updates in Haskell seems a waste of time(?) AntC
Hi,
is there any way to perform a destructive update on a plain ADT?
Hi Milan, perhaps this is a dumb question, but given that you're using a lazy functional language: why do you want to do destructive updates at all?
Perhaps you'd be better off using an imperative/object-oriented language?
I am one of the maintainers of the containers package, so I definitely want to stick to Haskell :) The reason for me wanting to do destructive updates is speed -- if I could perform destructive updates during the construction of persistent structure (e.g., inside Data.Map.fromList), the performance would improve.
... I would like just to run some benchmarks and see the results.
Running benchmarks for destructive updates in Haskell seems a waste of time(?)
Johan successfully improved unordered-containers by using destructive updates during construction, but he is using Array# where destructive updates are possible. I was wondering if I could do similar thing in containers... Cheers, Milan
participants (5)
-
AntC -
Ganesh Sittampalam -
Johan Tibell -
MigMit -
Milan Straka