Opened 8 years ago

Closed 3 years ago

#1752 closed bug (wontfix)

CSE can create space leaks by increasing sharing

Reported by: guest Owned by:
Priority: low Milestone:
Component: Compiler Version: 6.6.1
Keywords: Cc:
Operating System: Windows Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):


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)

Attachments (1)

fibsquares.hs (450 bytes) - added by guest 8 years ago.

Download all attachments as: .zip

Change History (5)

Changed 8 years ago by guest


comment:1 Changed 8 years ago by simonpj

  • Milestone set to _|_
  • Priority changed from normal to low

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)

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.


comment:2 Changed 7 years ago by simonmar

  • Architecture changed from Multiple to Unknown/Multiple

comment:3 Changed 3 years ago by morabbin

  • Type of failure set to Runtime performance bug

Marking as run-time perf bug.

comment:4 Changed 3 years ago by simonmar

  • Resolution set to wontfix
  • Status changed from new to closed
  • Summary changed from space leak caused by $ vs. () with -O2 to CSE can create space leaks by increasing sharing

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

Note: See TracTickets for help on using tickets.