Opened 10 years ago

Closed 10 years ago

Last modified 10 years ago

#3437 closed bug (fixed)

Optimizer creates space leak on simple code

Reported by: lilac Owned by:
Priority: normal Milestone:
Component: Compiler Version: 6.10.3
Keywords: Cc:
Operating System: Linux Architecture: x86_64 (amd64)
Type of failure: Runtime performance bug Test Case: simplCore/should_run/T3437
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

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

Change History (3)

comment:1 Changed 10 years ago by simonpj

difficulty: Unknown

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

comment:2 Changed 10 years ago by simonpj

Resolution: fixed
Status: newclosed
Test Case: simplCore/should_run/T3437
Type: bugrun-time performance bug

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

comment:3 Changed 10 years ago by simonmar

Type of failure: Runtime performance bug
Note: See TracTickets for help on using tickets.