On Mon, Jun 19, 2006 at 05:50:13PM +0100, Duncan Coutts wrote:
> On Mon, 2006-06-19 at 17:03 +0100, Jon Fairbairn wrote:
> > il [] = error "foo"
> > il [x] = ([], x)
> > il (x:xs) = cof x (il xs)
> > where cof x ~(a,b) = (x:a, b)
> > -- !
>
> From a quick test, it looks like none of our suggested solutions
> actually work in constant space.
>
> main = interact $ \s ->
> case il s of
> (xs, x) -> let l = length xs
> in l `seq` show (l,x)
I was hoping to have enlightenment served to me, but since nobody has
explained this, I took a crack at it. I still can't explain it, but I
got some data that maybe somebody else will understand. My code:
initlast :: [a] -> ([a], a)
initlast [x] = ([], x)
initlast (x:xs) = let (init, last) = initlast xs
in (x:init, {-# SCC "last" #-} last)
lenshow n (_:xs) last = let n1 = n+1 in n1 `seq` lenshow n1 xs last
lenshow n [] last = show (n,last)
main = interact $ \s -> case initlast s of
(xs, x) -> lenshow 0 xs x
lenshow is just "show (length xs, x)", written out so I can tweak it
later. This exhibits the runaway space usage with a large input that
Duncan described. If you throw away "last" in lenshow and just "show
n", it runs in constant space.
It seems that the reference to "last" that I annotated as a cost center
is holding a chain of trivial thunks--trivial because "last" is just
being copied from the result of the recursive call to initlast. I
thought maybe I could get rid of them by returning an unboxed tuple from
initlast, but this turned out to make no difference.
Profiling gave a couple hints. Retainer set profiling (-hr) showed the
retainer set holding all the memory was
{<Main.last,Main.initlast,Main.main,Main.CAF>}
I think this confirms that last holding a chain of thunks. I'm still
surprised that ghc doesn't see that they're trivial. It feels like it
should be an easy optimization.
Constructor and type profiling (-hd and -hy) both show the memory held
by stg_ap_1_upd_info. I don't know what that means.
Most frustrating, I can't find any work around: No matter how I tried
to write initlast, it had the same leak when consumed this way. (NB:
functional implementations only need apply.) Granted, I can't think of
any good reason to code in this style, but it's hard for me to accept
that it should be impossible.
Finally, here is a (silly) version that doesn't leak:
initlast :: [a] -> ([a], [a])
initlast [x] = ([], [x])
initlast (x:xs) = let (init, last) = initlast xs
in (x:init, undefined:last)
lenshow n (_:xs) (_:ls) = let n1 = n+1 in n1 `seq` lenshow n1 xs ls
lenshow n [] [last] = show (n,last)
This is the first case I recall in which adding more constructors makes
a space leak go away, because it gives me something to force (vis
"_:ls). With the original implementation, there was no way to "partly
force" last, one thunk at a time. Have others used this technique?
Andrew