Memory usage

[William Marsh]

In message <3A1D3124.933312D8@dcse.fee.vutbr.cz>, Dusan Kolar
<kolar@dcse.fee.vutbr.cz> writes
  
 >Hello,
 >
 >  working on a small utility for de/compression of special files
 >using special algorithm (useless in other cases and not important
 >for the problem) I've encountered I cannot decompress even small
 >files because I always run out of the memory.
 >
 >  After some time I've found the problem. It can be simplified
 >to the following function (computing nothing reasonable):

Dusan's function, (reformatted - this message is a hugs script,
unless the lines get wrapped by your email) is:

> tst :: [a] -> [a] -> [a] -> [a]
> tst l []     = id
> tst l (x:xs) = if null l then ((++) [x]) . (tst (l++[x]) xs) 
>                 else if null (tail l) then ((++) [x,last l]) . 
>                         (tst (tail l++[last l]++[x]) xs)
>                 else ((++) [x,last l]) . 
>                         (tst (tail (tail l)++[last l]++[x]) xs)
 
 >Trying to run it in hugs (default settings) this way:
 >
 > tst [] [1..20000] []
 >
 >the program stops writing almost all the lines and running out of
 >memory.

From the example you give, I assume that the 'purpose' 
of tst is to compute p  efficiently, where

> p :: [a] -> [a]
> p xs = tst [] xs []

  p [1,2]     = [1,2,1]
  p [1,2,3]   = [1,2,1,3,2]
  p [1,2,3,4] = [1,2,1,3,2,4,3]

It looks as though this function can be computed in 
constant space, but p leaks space. I check this by 
starting hugs with a small heap:
  hugs +g -h30k
Then:

Main> last $ p [1..10000]
{{Gc:17584}}{{Gc:15496}}{{Gc:13652}}{{Gc:12036}}{{Gc:10608}}{{Gc:9352}}
{{Gc:8246 }}{{Gc:7258}}{{Gc:6396}}{{Gc:5644}}{{Gc:4964}}{{Gc:4379}}
{{Gc:3865}}{{Gc:3404}}{{Gc:3002}}{{Gc:2642}}{{Gc:2340}}{{Gc:2052}}
{{Gc:1816}}{{Gc:1592}}{{Gc:1404}}{{Gc:1248}}{{Gc:1092}}{{Gc:960}}
(89416 reductions, 159870 cells, 23 garbage collections)
{{Gc:960}}ERROR: Garbage collection fails to reclaim sufficient space

The tst function is 'equivalent' to tst1, which 
is derived by splitting out the cases and simplifying.
I prefer this style!

> tst1:: [a] -> [a] -> [a] -> [a]
> tst1 _       []     b = b
> tst1 []      (x:xs) b = [x] ++ tst1 [x] xs b
> tst1 [y]     (x:xs) b = [x,y] ++ tst1 [y,x] xs b
> tst1 [y,z]   (x:xs) b = [x,z] ++ tst1 [z,x] xs b
> tst1 (y:z:m) (x:xs) b = [x,n] ++ tst1 (m ++ [n,x]) xs b
>                           where n = last m

> p1 :: [a] -> [a]
> p1 xs = tst1 [] xs []

Also, p1 *doesn't leak space*. Why? I really haven't much
idea: it may be because there is only one 'last m', but a 
better guess could be that tst is a bit too complicated!

Main> last $ p1 [1..10000]
{{Gc:19934}}{{Gc:19932}}{{Gc:19932}}{{Gc:19932}}{{Gc:19932}}{{Gc:19932}}
{{Gc:19932}}{{Gc:19932}}{{Gc:19932}}{{Gc:19932}}{{Gc:19932}}{{Gc:19932}}
{{Gc:19932}}{{Gc:19932}}{{Gc:19932}}{{Gc:19932}}{{Gc:19932}}{{Gc:19932}}
{{Gc:19932}}{{Gc:19932}}{{Gc:19932}}{{Gc:19932}}{{Gc:19932}}9999
(240028 reductions, 440040 cells, 23 garbage collections)
{{Gc:19967}}Main>

The following 'specification' of p uses lots of space:
> p0 :: [a] -> [a] 
> p0 []  = []
> p0 [x] = [x]
> p0 xs  = p0 (init xs) ++ [last xs, last $ init xs]

Another 'implementation' using constant space is:
> p2 :: [a] -> [a]
> p2 []        = []
> p2 [x]       = [x]
> p2 xs@(x:ys) = (x:merge ys xs)
>   where
>     merge []     _      = []
>     merge (a:as) (b:bs) = (a:b:merge as bs)

There have been lots of messages on this list concerning
space leaks in Haskell. It seems that only compiler writers
can understand the causes of subtle space leaks.  This isn't 
really very satisfactory.

Hope this helps.
-- 
William Marsh