Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.haskell > #238 > unrolled thread

Space leak

Back to article view | Back to comp.lang.haskell

Contents

  Space leak Paul Rubin <no.email@nospam.invalid> - 2012-12-12 14:36 -0800
    Re: Space leak Piotr Kalinowski <pitkali@gmail.com> - 2012-12-13 13:58 +0100
      Re: Space leak Paul Rubin <no.email@nospam.invalid> - 2012-12-13 08:40 -0800
        Re: Space leak Piotr Kalinowski <pitkali@gmail.com> - 2012-12-17 14:18 +0100
        Re: Space leak Wolfgang Ehrlich <wolfgang.ehrlich@googlemail.com> - 2013-01-08 06:15 -0800
          Re: Space leak Wolfgang Ehrlich <wolfgang.ehrlich@googlemail.com> - 2013-01-09 00:15 -0800
    Re: Space leak Dirk Thierbach <dthierbach@usenet.arcornews.de> - 2012-12-14 00:07 +0100
    Re: Space leak "Albert Y. C. Lai" <trebla@vex.net> - 2012-12-24 18:51 -0500

#238 — Space leak

I had a space leak in a program that I distilled down to the following:

   main = print $ length (replicateM 15 "012")

This should generate all the 15-digit ternary numbers (with leading 0's)
so the length of the list is 3**15=14348907.  It gets that result
correctly, but uses almost a gigabyte of ram in computing it.

As an exercise I wrote my own version of the List datatype and the monad
instance for it doing the obvious things, and the same behavior
happened.  Writing a strict version of the length function using foldl1'
didn't help either.

It's not real obvious to me what's going on.  Is there a simple
explanation why replicateM doesn't generate values lazily that are
consumed by length?

Thanks.

[toc] | [next] | [standalone]

#239

Paul Rubin <no.email@nospam.invalid> writes:

> I had a space leak in a program that I distilled down to the following:
>
>    main = print $ length (replicateM 15 "012")
>
> This should generate all the 15-digit ternary numbers (with leading 0's)
> so the length of the list is 3**15=14348907.  It gets that result
> correctly, but uses almost a gigabyte of ram in computing it.
>
> As an exercise I wrote my own version of the List datatype and the monad
> instance for it doing the obvious things, and the same behavior
> happened.  Writing a strict version of the length function using foldl1'
> didn't help either.
>
> It's not real obvious to me what's going on.  Is there a simple
> explanation why replicateM doesn't generate values lazily that are
> consumed by length?

replicateM could produce result lazily, but length still needs to
traverse the whole list in order to determine its length. This process
of traversing the list forces evaluation of all its contents.

In other words, length does not consume values returned by replicateM.
It consumes a single value: a list, and it needs to fully evaluate it's
structure.

Regards,
Piotr Kalinowski

[toc] | [prev] | [next] | [standalone]

#240

Piotr Kalinowski <pitkali@gmail.com> writes:
> In other words, length does not consume values returned by replicateM.
> It consumes a single value: a list, and it needs to fully evaluate it's
> structure.

I don't understand, the list it receives is in WHNF so it should just
be a single (:) constructor with a value and a thunk.

If I type "length [1..]" into ghci, it burns cpu but doesn't expand
in memory.  What is different?

[toc] | [prev] | [next] | [standalone]

#244

Paul Rubin <no.email@nospam.invalid> writes:

> If I type "length [1..]" into ghci, it burns cpu but doesn't expand
> in memory.  What is different?

Hmm, true. I might be wrong. I'm not an expert here.

Regards,
Piotr Kalinowski

[toc] | [prev] | [next] | [standalone]

#246

Am Donnerstag, 13. Dezember 2012 17:40:41 UTC+1 schrieb Paul Rubin:
> Piotr Kalinowski <pitkali@gmail.com> writes:
> > In other words, length does not consume values returned by replicateM.
> > It consumes a single value: a list, and it needs to fully evaluate it's
> > structure.
> 
> I don't understand, the list it receives is in WHNF so it should just
> be a single (:) constructor with a value and a thunk.
> 
> If I type "length [1..]" into ghci, it burns cpu but doesn't expand
> in memory.  What is different?

Just guessing: It may be the algorithm that causes the space leak.

To create the list of 2^15 elements the algorithm creates a sublist of 2^14 elements and uses this sublist three times to build the requested list. It is the sublist that occupies the memory.

Just a simple example for illustration:

    burn_memory :: Int -> Int
    burn_memory n =
      let sublist = [1 .. n]
      in length (sublist ++ sublist)

[toc] | [prev] | [next] | [standalone]

#247

Am Dienstag, 8. Januar 2013 15:15:34 UTC+1 schrieb Wolfgang Ehrlich:
> Am Donnerstag, 13. Dezember 2012 17:40:41 UTC+1 schrieb Paul Rubin:
> > Piotr Kalinowski <pitkali@gmail.com> writes:
> > > In other words, length does not consume values returned by replicateM.
> > > It consumes a single value: a list, and it needs to fully evaluate it's
> > > structure.
> > 
> > I don't understand, the list it receives is in WHNF so it should just
> > be a single (:) constructor with a value and a thunk.
> > 
> > If I type "length [1..]" into ghci, it burns cpu but doesn't expand
> > in memory.  What is different?
> 
> Just guessing: It may be the algorithm that causes the space leak.
> 
> To create the list of 2^15 elements the algorithm creates a sublist of 2^14 elements and uses this sublist three times to build the requested list. It is the sublist that occupies the memory.
> 
> Just a simple example for illustration:
> 
>     burn_memory :: Int -> Int
>     burn_memory n =
>       let sublist = [1 .. n]
>       in length (sublist ++ sublist)

Oops, I got something wrong: "2^15" should be "3^15" and
"2^14" should be "3^14". Sorry for the inconvenience.

Back to the problem. Calling

    Control.Monad.replicateM n "012"

with different values of *n* yields:

    n=0: [""]
    n=1: ["0","1","2"]
    n=2: ["00","01","02","10","11","12","20","21","22"]
    n=3:
         ["000","001","002","010","011","012","020","021","022"
         ,"100","101","102","110","111","112","120","121","122"
         ,"200","201","202","210","211","212","220","221","222"
         ]

This clearly shows how each list is built by using the previous
list three times.

As a remedy, you might consider to devise an algorithm that
builds the lists differently, avoiding the multiple use of
complete intermediate lists, e.g. by using each list element
multiple times. The resulting lists would be as shown below:

    n=0: [""]
    n=1: ["0","1","2"]
    n=2: ["00","10","20","01","11","21","02","12","22"]
    n=3:
         ["000","100","200","010","110","210","020","120","220"
         ,"001","101","201","011","111","211","021","121","221"
         ,"002","102","202","012","112","212","022","122","222"
         ]

[toc] | [prev] | [next] | [standalone]

#241

Paul Rubin <no.email@nospam.invalid> wrote:
> I had a space leak in a program that I distilled down to the following:
> 
>   main = print $ length (replicateM 15 "012")
> 
> This should generate all the 15-digit ternary numbers (with leading 0's)
> so the length of the list is 3**15=14348907.  It gets that result
> correctly, but uses almost a gigabyte of ram in computing it.
> 
> As an exercise I wrote my own version of the List datatype and the monad
> instance for it doing the obvious things, and the same behavior
> happened.  Writing a strict version of the length function using foldl1'
> didn't help either.
> 
> It's not real obvious to me what's going on.  Is there a simple
> explanation why replicateM doesn't generate values lazily that are
> consumed by length?

I didn't verify this in detail, but if you look at the definitions:

  replicateM n x = sequence (replicate n x)
  
  sequence ms = foldr k (return []) ms where
    k m m' = do { x <- m; xs <- m'; return (x:xs) }
  
  instance  Monad []  where
    m >>= k = foldr ((++) . k) [] m
  
you see that there's a lot of (++) in the monadic composition in addition
to sharing of the result from m'. So my intuition is that all these 
pile up as unevaluated expressions and use up memory.

If you'd implement the same algorithm more directly, something
along the lines of

  count :: Int -> [a] -> [a] -> [[a]]
  count 0  _     _  = [[]]
  count k []     ys = []
  count k (x:xs) ys = map (x:) (count (k-1) ys ys) ++ count k xs ys
  
  count' k xs = count k xs xs
  
  main = print $ length $ count' 15 "012"
  
i.e. without (++) and not sharing the recursive call, you should see
a decrease of memory usage. As I said, untested and just my intuition.
You're welcome to test and maybe add some strictness till it works
correctly. :-)

- Dirk

[toc] | [prev] | [next] | [standalone]

#245

On 12-12-12 05:36 PM, Paul Rubin wrote:
> I had a space leak in a program that I distilled down to the following:
>
>     main = print $ length (replicateM 15 "012")
>
> This should generate all the 15-digit ternary numbers (with leading 0's)
> so the length of the list is 3**15=14348907.  It gets that result
> correctly, but uses almost a gigabyte of ram in computing it.

This is very interesting. Experiment environment:

Ubuntu 12.04 x86 32-bit, GHC 7.4.2 from GHC website, use command line 
option "+RTS -t" to count memory footprint.

The following program seems to take exponential memory when optimized, 
constant memory when unoptimized (yes yes should be linear, but the 
slope is so small):

import System.Environment(getArgs)
main = do
   n <- (read . head) `fmap` getArgs
   print (length (mysequence (replicate n "012")))
mysequence [] = return []
mysequence (m:ms) = do
   x <- m
   xs <- mysequence ms
   return (x:xs)

(Commands:
ghc -fforce-recomp f1.hs
./f1 10 +RTS -t
play with other numbers

ghc -fforce-recomp -O f1.hs
./f1 10 +RTS -t
play with other numbers)

The following program seems to take exponential memory whether optimized 
or not:

import System.Environment(getArgs)
main = do
   n <- (read . head) `fmap` getArgs
   print (length (mysequence (replicate n "012")))
mysequence ms = foldr k (return []) ms where
   k m m' = do
     x <- m
     xs <- m'
     return (x:xs)

Supplying homebrew foldrs does not seem to make a difference.

You are right in that the program should and can take just linear memory 
under a standard lazy evaluation model.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.haskell

csiph-web