Optimizer creates space leak on simple code

[lilac]

The following code should run in constant space:

{-# LANGUAGE BangPatterns #-}
go (x:xs) !n !k = go xs 0 (n+k+1)
main = print (go (repeat 'x') 0 0 :: Int)

However, when compiled with -O2, it rapidly eats up the heap. If n and k are forced to be Int rather than Integer, the problem disappears.

Core for the above with -O2 is here:  http://hpaste.org/fastcgi/hpaste.fcgi/view?id=8268
The original code from which this was taken is here:  http://hpaste.org/fastcgi/hpaste.fcgi/view?id=8266

[simonpj]

Excellent bug thank you! It turns out that go is strict, but we don't do strictness analysis following SpecConstr so the specialised version of go is not (marked) strict. As a result, the latter builds a thunk each time around the loop, which creates the leak.

It's not hard to transfer strictness; I'll try that.

Simon

[simonpj]

Done! Fixed by

Fri Aug 21 10:52:51 BST 2009  simonpj@microsoft.com
  * Fix Trac #3437: strictness of specialised functions
  
  'lilac' helpful pin-pointed a space leak that was due to a specialised
  function being insufficiently strict.  Here's the new comment in SpecConstr:
  
  Note [Transfer strictness]
  ~~~~~~~~~~~~~~~~~~~~~~~~~~
  We must transfer strictness information from the original function to
  the specialised one.  Suppose, for example
  
    f has strictness     SS
          and a RULE     f (a:as) b = f_spec a as b
  
  Now we want f_spec to have strictess  LLS, otherwise we'll use call-by-need
  when calling f_spec instead of call-by-value.  And that can result in 
  unbounded worsening in space (cf the classic foldl vs foldl')
  
  See Trac #3437 for a good example.
  
  The function calcSpecStrictness performs the calculation.
  
  

    M ./compiler/specialise/SpecConstr.lhs +44

Thank you for identifying the problem so precisely.

Simon