CSE can create space leaks by increasing sharing

[guest]

The following program exhibits a space leak on GHC6.6.1. "noleak" doesn't exhibit the leak. The only difference is choosing to use $ (leaky) instead of () (non-leaky).

No leak happens if optimizations are off.

Compiled with c:\haskell> ghc -O2 --make fibsquares.hs

module Main where

fibs a b = a : fibs b (a+b)

odds (x:xs) = evens xs
evens (x:xs) = x : odds xs

square x = x*x
sumSucc xs = zipWith (+) xs (tail xs)

main = spaceleak

spaceleak = 
    mapM_ print $ zip [0..] $ takeWhile id $
    zipWith (==) (odds $ fibs 0 1) $ 
    sumSucc $ map square $ fibs 0 1

noleak =
    mapM_ print $ zip [0..] $ takeWhile id $
    zipWith (==) (odds $ fibs 0 1)
    (sumSucc $ map square $ fibs 0 1)

[guest]

leaky!

[simonpj]

I don't think it's anything to do with the "$"; both versions leak in GHC 6.6.1 and 6.8. Heres is a boiled-down version:

module Main(main) where

 fibs a b = a : fibs b (a+b)

 odds (x:y:ys) = x : odds ys

 main = print $ zipWith (==) (odds (fibs 0 1))
		  	     (fibs 0 1)

Try compiling with -O and running with

  ./leak +RTS -Sstderr > /dev/null

What happens is that GHC does commmon-subexpression on the (fibs 0 1) to give:

 fibs01 = fibs 0 1
 main = print $ zipWith (==) (odds fibs01)
		  	     fibs01

Now the left argument of zipWith marches down the infinite twice as fast as the right argument, so there's an ever-increasing chunk in between the two. See the chapter on pragmatics in my 1987 book.

If you switch off common sub-expression -fno-cse then all is happy again.

I don't know how to fix this. We also get bug reports about unexpected lack of commmon sub-expression, so it's a difficult transformation to get right!

I'll leave it as low priority for now.

Simon

[morabbin]

Marking as run-time perf bug.

[simonmar]

Known issue with CSE, not likely to ever get fixed.