Re: Space leak in a fold even after the usual fixes
I take it that size of the array does not depend on arg ?
Apparently, despite your attempts to force evaluation, the array still contains many unevaluated expressions. Documentation for the vector pacakge reveals that Data.Vector is a *boxed* array, i.e. the entries are only evaluated on demand, so that's where the unevaluated expressions linger around.
Unless you need the extra laziness - which you probably don't, given how you've structured your algorithm - you might want to switch to Data.Vector.Unboxed or Data.Vector.Storable.
Correct. The array size doesn't depend on arg (arg only controls how much of the input list to process. I did not realize that the boxed arrays would have this extra-lazy behavior. The reason I chose boxed is because I needed to store these very large trees (custom data type) that I referenced in an earlier question. Since D.V.Unboxed and Storable don't appear to support non-standard data types, is there another package that might better fit my needs? Data.IntMap perhaps? I originally chose an array over a map because I need fast random access to individual elements (and cheap modification). Thanks again, Travis Erdman
Am Montag 12 April 2010 19:11:21 schrieb Travis Erdman:
I take it that size of the array does not depend on arg ?
Apparently, despite your attempts to force evaluation, the array still contains many unevaluated expressions. Documentation for the vector pacakge reveals that Data.Vector is a *boxed* array, i.e. the entries are only evaluated on demand, so that's where the unevaluated expressions linger around.
Unless you need the extra laziness - which you probably don't, given how you've structured your algorithm - you might want to switch to Data.Vector.Unboxed or Data.Vector.Storable.
Correct. The array size doesn't depend on arg (arg only controls how much of the input list to process.
I did not realize that the boxed arrays would have this extra-lazy behavior. The reason I chose boxed is because I needed to store these very large trees (custom data type) that I referenced in an earlier question. Since D.V.Unboxed and Storable don't appear to support non-standard data types, is there another package that might better fit my needs?
You could try to introduce the necessary strictness via Control.DeepSeq and/or Control.Parallel.Strategies, strictly writing (newTree `using` rnf) to the array.
Data.IntMap perhaps? I originally chose an array over a map because I need fast random access to individual elements (and cheap modification).
Thanks again,
Travis Erdman
Travis Erdman wrote:
I did not realize that the boxed arrays would have this extra-lazy behavior. The reason I chose boxed is because I needed to store these very large trees (custom data type) that I referenced in an earlier question. Since D.V.Unboxed and Storable don't appear to support non-standard data types, is there another package that might better fit my needs? Data.IntMap perhaps? I originally chose an array over a map because I need fast random access to individual elements (and cheap modification).
Concerning your choice of data structure, take note that data structures are *persistent* in Haskell, i.e. they cannot be mutated. So, while arrays provide random access in O(1) time, they need O(n) time to update because the whole array has to be copied (unless you ensure ephemeral use with the ST or IO monad). Nonetheless, the Data.Vector library provides functions like map that operate on the whole array and run in O(n) time. In comparison, Data.IntMap has O(size of Int in bits) lookup and O(size of Int in bits) update. Data.Vector is mainly about arrays of bytes, hence the prominence of Unboxed and Storable. You could make your tree an instance of Storable , but I think that's only possible for fixed size types anyway. Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com
participants (3)
-
Daniel Fischer -
Heinrich Apfelmus -
Travis Erdman