[Haskell-cafe] Space leak with replicateM

[Alexander Eyers-Taylor]

Hello

Looking at the generated core numbers is shared in both cases. This is 
very small list and hence shouldn't
create the memory problems.

The problem comes from floating out.

The test1 expands to roughly the following (in imperative pseudo code)

sequence [nums,nums,nums,nums]=
   xs := sequence [nums,n]
   for (a in nums)
     for (rest in xs)
       yield (a:rest)

while test2 expands becomes

for (a in nums)
   for (b in nums)
     for (c in nums)
       for (d in nums)
         yield [a,b,c,d]

In the first case xs is shared between all elements in nums.

If we write out explicit definitions of replicateM specialised to lists  
we see

replicateM' 0 xs = return []
replicateM' n xs = do
   a <- xs
   b <- replicateM' (n-1) xs
   return (a:b)

which is optimised to be


replicateM' 0 xs = return []
replicateM' n xs =
let recCase = replicateM' (n-1) xs
    in do a <- xs
          b <- recCase
          return (a:b)

wheras we can write


replicateM'' 0 xs = return []
replicateM'' n xs = do
   b <- replicateM' (n-1) xs
   a <- xs
   return (b ++ [a])

The second version has no space leak. However when n is large it is 
inefficient due
to ++ but this can probably be avoided. The reason why this causes a 
space leak
is due to ghc floating the recursive case out of the lambda which is 
then shared between
the iterations. This avoid some computation but then causes a space leak.

test2 itself optimises really well and causes fusion resulting in the tight
structure

Alex

On 16/06/15 10:09, Joachim Breitner wrote:
> Hi,
>
> Am Dienstag, den 16.06.2015, 03:37 -0400 schrieb Ken Takusagawa II:
>> In the following program, the function "test1" results in huge memory
>> usage, but substituting "test2", which does essentially the same
>> thing, does not.  GHC 7.10.1, AMD64.  Is there a different
>> implementation of replicateM that avoids the space leak?
>>
>> module Main where {
>> import Control.Monad;
>>
>> numbers :: [Int];
>> numbers=[1..200];
>>
>> -- has a space leak
>> test1 :: [[Int]];
>> test1 = replicateM 4 numbers;
>>
>> -- no space leak
>> test2 :: [[Int]];
>> test2 = do {
>> x1 <- numbers;
>> x2 <- numbers;
>> x3 <- numbers;
>> x4 <- numbers;
>> return [x1,x2,x3,x4];
>> };
>>
>> main :: IO();
>> main = print $ length $ test1;
>>
>> }
>>
> Could be the state hack causing `numbers` to inline, see
> http://stackoverflow.com/questions/29404065/why-does-this-haskell-code-run-slower-with-o/30603291#30603291
> and
> https://ghc.haskell.org/trac/ghc/ticket/9349
>
> Greetings,
> Joachim
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe