I need some help with space and time leaks. I know of two types of space leak. The first type of leak occurs when a function uses unnecessary stack or heap space. GHCi> sum [1..10^6] *** Exception: stack overflow Apparently, the default definition for "sum" has a space leak. I can define my own sum in terms of strict foldl ...
sum' xs = foldl' (+) 0 xs
... and it doesn't overflow the stack. GHCi> sum' [1..10^6] 500000500000 (0.27 secs, 112403416 bytes) GHCi> sum' [1..10^7] 50000005000000 (2.73 secs, 1161223384 bytes) GHCi> sum' [1..10^8] 5000000050000000 (27.83 secs, 11645261144 bytes) I think there's still a space leak; I don't understand why GHCi using 10^8, 10^9, 10^10 bytes of memory for these calculations. The other type of space leak I know of is when I have a chunk of data in memory that I no longer need, such that the data is still being referenced somewhere. Since, in theory, I might still access the data, the garbage collector can't reclaim the memory. I'm not sure how to construct an example though. Regarding time leaks, I only know of one kind of leak. If I have a calculation that accumulates data over time, and I don't ask for any results until the end, then, due to laziness, that calculation might accumulate a chain of unevaluated thunks. When I get the the end and "demand" the final result, I have to wait for it while the RTS evaluates a long chain of thunks. The chain of unevaluated thunks is a space leak. The time leak occurs because the capture process and the accumulate process are supposed to be interleaved, such that I perform some computations after I capture each piece of data. If I have to wait around at the end, then it means the capture process and the accumulate process happened in sequence. As far as I know, every time leak has a companion space leak; it's not possible to create a time leak without a space leak to go with it. Is this really true? Now for the hard questions. 1. How do I go about detecting space and time leaks? 2. Once I find a leak, how do I fix it? 3. Are there any programming techniques I can use to avoid leaks? -- Ron
On 2007-10-04, Ronald Guida
I need some help with space and time leaks.
I know of two types of space leak. The first type of leak occurs when a function uses unnecessary stack or heap space.
GHCi> sum [1..10^6] *** Exception: stack overflow
Apparently, the default definition for "sum" has a space leak. I can define my own sum in terms of strict foldl ...
sum' xs = foldl' (+) 0 xs
... and it doesn't overflow the stack.
GHCi> sum' [1..10^6] 500000500000 (0.27 secs, 112403416 bytes)
GHCi> sum' [1..10^7] 50000005000000 (2.73 secs, 1161223384 bytes)
GHCi> sum' [1..10^8] 5000000050000000 (27.83 secs, 11645261144 bytes)
I think there's still a space leak; I don't understand why GHCi using 10^8, 10^9, 10^10 bytes of memory for these calculations.
This isn't a space leak. The memory reported is the total amount of allocation done, not the most used at a given time. A C program that did "x = malloc(20); free(x); x = malloc(20); free(x);" would be reporting 40. The run-time system is essentially constructing all of these Integers (and functions returning them) at one point or another, and these need to be represented. Compare with "last" on these structures: Prelude> last [1..10^6] 1000000 (0.06 secs, 40895096 bytes) Prelude> last [1..10^7] 10000000 (0.50 secs, 402118492 bytes) Prelude> last [1..10^8] 100000000 (4.74 secs, 4016449660 bytes) -- Aaron Denney -><-
Ronald Guida wrote:
Now for the hard questions. 1. How do I go about detecting space and time leaks? 2. Once I find a leak, how do I fix it? 3. Are there any programming techniques I can use to avoid leaks?
I'm hard time to believe I'll write something you do not know but I had similar problem and it was not hard to fix (despite some stories that it is very hard in Haskell). If you use ghc then skim over this, otherwise do not mind. Check also GHC User Guide. The options are described, well not very well but better than nothing. add 1) Here are few options I found most useful. compile with: -prof -auto-all run with: +RTS -p -hc -RTS ... to see what functions are creating leaks and which functions take the most time. Check out the <app>.prof and <app>.hp (the numbers in <app>.hp correspond to stack traces in <app>.prof (the no. column)). run with: +RTS -hr -RTS ... to see what is still keeping references to your data The stack traces corresponding to the numbers in <app>.hp are in <app>.prof. The stuff which is keeping the references are typically the routines which are creating closures and pass them around in their results instead of forcing computation and returning the processed data (which are hopefully much smaller than the input data processed). run with: +RTS -s +RTS ... and check your <app>.stat to see if your time problem is not actually a space problem leading to very poor GC performance. use hp2ps to look at the <app>.hp files add 2) Add ! to your data types at places from the result data structure to the final/leaf data structures which will keep the processed data. This is provided you do not need laziness on some places. If you do (e.g. so that you do not compute data fields which are not mostly used or when you actually require it for efficient processing (like foldr with function nonstrict in second arg)) then you need to use seq or preferably $! on the code paths which need to be strict and leave the rest of code paths lazy. Idea is that you need strictness somewhere so that your huge input data are compacted to the small output data on the fly instead at the very end when you ask for some result. add 3) There is something on the haskell wiki. Search for stack overflow and something about tail recursion and when it is a "red herring". I just looked for the data with google and there is enough of them. Peter.
Ronald Guida wrote:
I need some help with space and time leaks.
I know of two types of space leak. The first type of leak occurs when a function uses unnecessary stack or heap space.
GHCi> sum [1..10^6] *** Exception: stack overflow
Apparently, the default definition for "sum" has a space leak. I can define my own sum in terms of strict foldl ...
sum' xs = foldl' (+) 0 xs
... and it doesn't overflow the stack.
GHCi> sum' [1..10^6] 500000500000 (0.27 secs, 112403416 bytes)
But it fills the heap? My intuition is that foldr (+) 0 [1..10^6] is the fusion of a good producer and consumer so no heap is wasted constructing [1..10^6] but the stack is instead filled with (1+),(2+),...,(999999+) unary functions, whereas foldl' (+) 0 [1..10^6] does not fill the stack with anything but does fill the heap with [1..10^6] because foldl' is no longer a good consumer? If so, it seems that the stack is smaller than the heap (or else the size of (1+) is much larger than that the element of an [Int]. Anyone know the truth of any of this?
Dan Weston wrote:
Ronald Guida wrote:
I need some help with space and time leaks.
I know of two types of space leak. The first type of leak occurs when a function uses unnecessary stack or heap space.
GHCi> sum [1..10^6] *** Exception: stack overflow
Apparently, the default definition for "sum" has a space leak. I can define my own sum in terms of strict foldl ...
sum' xs = foldl' (+) 0 xs
... and it doesn't overflow the stack.
GHCi> sum' [1..10^6] 500000500000 (0.27 secs, 112403416 bytes)
But it fills the heap? My intuition is that
foldr (+) 0 [1..10^6]
is the fusion of a good producer and consumer so no heap is wasted constructing [1..10^6] but the stack is instead filled with (1+),(2+),...,(999999+) unary functions, whereas
foldl' (+) 0 [1..10^6]
does not fill the stack with anything but does fill the heap with [1..10^6] because foldl' is no longer a good consumer?
Nope, it runs in small space. The [1..10^6] is evaluated lazily, it is never larger than the thunk that represent the rest of the list. If foldl' is a "good consumer" then GHC can avoid making the list's cons-cells (:). If foldl' is not a "good consumer" then then each cons cell is created and then quickly garbage collected.
If so, it seems that the stack is smaller than the heap (or else the size of (1+) is much larger than that the element of an [Int].
Anyone know the truth of any of this?
participants (5)
-
Aaron Denney -
ChrisK -
Dan Weston -
Peter Hercek -
Ronald Guida