Space leak question
Bertram Felgenhauer
bertram.felgenhauer at googlemail.com
Tue Jul 26 10:57:54 CEST 2011
Hi Will,
> in reformulation of a code with no space leak, the leak reappeares.
>
> It takes near constant space to get at the n-th elt in the produced list here
> (http://ideone.com/fiifl):
>
> {-# OPTIONS_GHC -O2 -fno-cse #-}
> primes = 2 : ([3,5..] `minus`
> foldi (\(x:xs) -> (x:) . union xs)
> [[x*x, x*x+2*x..] | x<- ys])
> where
> ys = 3 : ([5,7..] `minus`
> foldi (\(x:xs) -> (x:) . union xs)
> [[x*x, x*x+2*x..] | x<- ys])
> foldi f (x:xs) = f x (foldi f (pairs f xs))
> pairs f (x:y:t) = f x y : pairs f t
>
>
> Here it doesn't (http://ideone.com/m744a):
>
> {-# OPTIONS_GHC -O2 -fno-cse #-}
> primes = 2 : g (fix g)
> where
> g = (3:) . ([5,7..] `minus`)
> . foldi (\(x:xs) -> (x:) . union xs)
> . map (\x-> [x*x, x*x+2*x..])
This is entirely expected. What is gobbling up the memory is the
shared [5,7..] list that some invocation of g consume while others
hang onto the head of the same list. (Note that g is a constant.)
If you change the code to make g pointful, and compile with
-fno-full-laziness, then the memory usage will go down again.
{-# OPTIONS_GHC -O2 -fno-full-laziness #-}
primes :: [Int]
primes = 2 : g (fix g)
where
g xs = (3:) . ([5,7..] `minus`)
. foldi (\(x:xs) -> (x:) . union xs)
. map (\x-> [x*x, x*x+2*x..]) $ xs
With -ffull-laziness, ghc will notice that [5,7..] does not depend on
xs, and float it out to the surrounding scope, essentially turning the
code into
{-# OPTIONS_GHC -O2 #-}
primes :: [Int]
primes = 2 : g (fix g)
where
g xs = (3:) . (odds `minus`)
. foldi (\(x:xs) -> (x:) . union xs)
. map (\x-> [x*x, x*x+2*x..]) $ xs
odds = [5,7..]
and the [5,7..] list will be shared once more.
Using -fno-cse has no effect in this example, because there are no
duplicate subexpressions in the code. It is still a good idea to
try this option when one encounters odd space leaks.
Bertram
More information about the Glasgow-haskell-users
mailing list