Dictionaries and full laziness transformation

[Simon Peyton-Jones]

In general it's quite hard to solve this problem without risking losing sharing.

However in this case I added a simple arity analyser after the 7.0.1 release which solves the problem.  It'll be in 7.0.2.

Try with HEAD and check it does what you expect.

Simon

| -----Original Message-----
| From: glasgow-haskell-users-bounces at haskell.org [mailto:glasgow-haskell-
| users-bounces at haskell.org] On Behalf Of Akio Takano
| Sent: 07 February 2011 04:10
| To: glasgow-haskell-users at haskell.org
| Subject: Dictionaries and full laziness transformation
| 
| Hi,
| 
| I'm using GHC 7.0.1. I found that recursive overloaded functions tend
| to leak memory when compiled with full-laziness optimization on. Here
| is a simple case.
| 
| -- TestSub.hs
| {-# LANGUAGE BangPatterns #-}
| module TestSub where
| 
| {-# NOINLINE factorial #-}
| factorial :: (Num a) => a -> a -> a
| factorial !n !acc = if n == 0 then acc else factorial (n - 1) (acc * n)
| 
| -- main.hs
| import TestSub
| 
| factorial1 :: Int -> Int -> Int
| factorial1 = factorial
| 
| main = do
|     n <- readLn
|     print $ factorial1 n 1
| 
|     main
| 
| This program should run in constant space, and compiled with -O0 or
| -O2 -fno-full-laziness, it does. However with -O2, it takes a linear
| amount of memory. The core for factorial looks like this:
| 
| TestSub.factorial =
|   \ (@ a_ajm) ($dNum_slz :: GHC.Num.Num a_ajm) ->
|     let {
|       a_slA :: GHC.Classes.Eq a_ajm
|       [LclId]
|       a_slA = GHC.Num.$p1Num @ a_ajm $dNum_slz } in
|     let {
|       lvl2_slC :: a_ajm -> a_ajm -> a_ajm
|       [LclId]
|       lvl2_slC = TestSub.factorial @ a_ajm $dNum_slz } in
| ...
| 
| The problem is that lvl2_slC closure is created whenever factorial is
| applied to a Num dictionary, and kept alive until that application is
| GCed. In this program it never happens, because an application to the
| Num Int dictionary is referred to by the factorial1 CAF, and it
| recursively keeps the whole chain of closures alive.
| 
| I know that full laziness transformation *sometimes* causes a space
| leak, but this looks like a bad result to me, because:
| 
| - It looks like there is no point building a lot of equivalent
| closures, instead of one.
| - A lot of code can suffer from this behavior, because overloaded
| recursive functions are fairly common.
|   For example, unfoldConvStream function from the latest iteratee
| package suffers from this problem, if I understand correctly.
| 
| Does anyone have an idea on whether this can be fixed in GHC, or how
| to work around this problem?
| 
| Regards,
| 
| Takano Akio
| 
| _______________________________________________
| Glasgow-haskell-users mailing list
| Glasgow-haskell-users at haskell.org
| http://www.haskell.org/mailman/listinfo/glasgow-haskell-users