On Thu, Oct 19, 2006 at 06:23:35PM +0400, Bulat Ziganshin wrote:

Hello Andrea,

Wednesday, October 18, 2006, 9:34:28 PM, you wrote:

...

solution? Or just some hints on the kind of problem I'm facing: is it related to strictness/laziness, or it's just that I did not understand a single bit of how garbage collection works in Haskell?

i think, the second. unfortunately, i don't know good introduction to the actual GC implementation although i can give you a pair of not-so-friendly references: [...[

shortly speaking, memory allocated by GHC never shrinks.

Hello Bulat, well, you gave me a wonderfully clear introduction to Haskell GC, and now I have a better understanding of the output of the various profiling I'm doing. Thank you very much! Still, I cannot understand my specific problem, that is to say, why the function that reads a file retains so much memory. I did some test and the results are puzzling: - I tried reading the feed and directly converting it into the opml chunk to be inserted into the opml component of my StateT monad. The problem becomes far worse. Here the output of a heap profile: http://gorgias.mine.nu/haskell/a.out.feed2opml.ps as you can see, after opening one feed (397868 bytes), closing it, opening another one (410052 bytes), closing it and reopening the first one brings memory consumption to 152 Mega. Using the intermediate datatype (that is to say, reading the feed, transforming it into my datatype and then to the opml tree), reduces the problem: http://gorgias.mine.nu/haskell/a.out.feed2feedNotStrict.ps only 92 Mega of memory consumption for the very same operations. Making the intermediate datatype strict gives almost the same results: http://gorgias.mine.nu/haskell/a.out.feed2feedStrict.ps 98 Mega. Now, I come to believe the file reading is indeed strict, and that my problem could be related to StateT laziness. Does this makes sense? I'm now going to try to implement my opml state as a IORef and use a ReaderT monad to see if something new happens.

ps: if your program uses a lot if string, FPS will be a very great. it don;t change the GC behavior, just makes everything 10 times smaller :)

yes, but I'm using HXT and this is using normal strings to store xml text nodes. So I could have some improvements with IO but not that much in memory consumption, unless I totally change my implementation. Anyway, even if I could reduce from 152 to 15 mega the memory consumption for reading 2 feeds, I'd be running out of memory, on my laptop, in one day instead that 5 minutes. Anyway I should face the fact that it is not the string implementation in Haskell that is causing the problem. The problem is probably me! Thanks for your kind attention. Regards Andrea

Hallo Bulat! On Fri, Oct 20, 2006 at 10:21:51PM +0400, Bulat Ziganshin wrote:

first, GC don't occurs automatically when you close file. you can help GHC by using performGC from System.Mem. i does it in my own prog

I did not get an appreciable improvement with performGC, as you can see from here: http://gorgias.mine.nu/haskell/a.out.withPerformGC.ps But I found a solution: just write the opml state component to a file! At first I decided to write it and reload it: http://gorgias.mine.nu/haskell/a.out.withFileReload.ps But I get a better result by just writing it (to /dev/null or to a real file): http://gorgias.mine.nu/haskell/a.out.withFileWrite.ps This way everything is garbage collected and the graph is what I would expect. Now, this is a good solution since the opml file is generally small (I have a file with 100 subscribed feeds and it is just 46Kbyte) and it stores information on the folder layout, so it must be saved anyway.

second, each Char in ghc occupies 12 bytes (!), so each of your files occupies about 5 mb of memory. if you will count the previous problem, the 2 or 3 files can be hels in memory at the same time (just because they was not yet GCd) so memory usage may become, say, 10 mb

multiplying this at 2.5 or even 3 factor which i described in previous letter means, say, 30 mb used

30 Mega used for reading a feed is a number that I seem to get. I also prevent the user from opening more then one feed at once. When a new feed is opened, the old feed gets removed, the opml file is written, the old stuff is garbage collected and the new stuff is added. Now, the memory fingerprint of the program is given by the most memory consuming feed. It is running at about 60-65 Mega. Not that bad, compared to the previous situation. Thank you very much for your suggestions. Regards Andrea

Hallo! Thanks a lot for stopping by. On Sat, Oct 21, 2006 at 06:41:32PM +0200, Udo Stenzel wrote:

The correct solution however, is the application of 'seq' at the right places. To understand where these are, perform a simulation of Haskell's reduction strategy on paper.

I will definitely try that.

...

30 Mega used for reading a feed is a number that I seem to get.

Depends on what you're doing with the data. If you scan a stream of Chars exactly once, the space requirement per Char is next to irrelevant. If you're keeping lots of Strings around, using PackedStrings will help (and be sure to pack strictly). But I actually suspect, you are running a backtracking parser over your input, so the whole input is read into a String and cannot be disposed of as long as the parser might backtrack. If this is Parsec, you need to remove a redundant 'try'. If it is the Read class, you need to replace it by Parsec or ReadP...

No. I'm actually using the ReadDocument module of HXT for reading my input and writeDocument for writing. So, it's parsec, on your side...;-) The application I'm writing is basically a HXT application, with an hscurser gui. If you have some hints on how to make memory consumption go down that would be great. Thanks for your kind attention. Andrea

Hello Andrea, Saturday, October 21, 2006, 3:44:31 PM, you wrote:

...

first, GC don't occurs automatically when you close file. you can help GHC by using performGC from System.Mem. i does it in my own prog

But I found a solution: just write the opml state component to a file!

and just after that you should call performGC. as Udo already said, writing to file just forces all thunks to be evaluated. before writing, you have hundreds of thousands of unevaluted functions, so it's no wonder that so much memory used. there is a faster way to do it: return $! x==x as Udo said, it should be better to evaluate thunks just when they are created, by using proper 'seq' calls. another solution is to make your fields strict by using '!': data T = T !Int !S but this limited to types explicitly defined by you, you can't create lists of strict elements, for example: data T = T [!Int] -- impossible!

added. Now, the memory fingerprint of the program is given by the most memory consuming feed. It is running at about 60-65 Mega. Not that bad, compared to the previous situation.

during 2 years of developing my own program i've made memory requirements 20 or 30 times lower. this included writing my own packed strings lib :))) -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

Hello Andrea, Sunday, October 22, 2006, 1:37:55 PM, you wrote:

...

as Udo said, it should be better to evaluate thunks just when they are created, by using proper 'seq' calls.

While I understand why you and Udo are right, still it is difficult for me to related this discussion to my code. So I wrote a small example that reproduces my problem, with the hope that this will help me understand your point.

sorry, i will not dig into details of its working. i will just explain common rule: if you calc something, make sure that returned value at any attempt to use it will be completely evaluated. it's something rather close to the problems of doing IO in lazy environment, thoroughly described in my IO inside manual for example, this definition: f a b = (a*b,a+b) will return you unevaluated thunk. even when it is used, it may be computed partially: main = do let x = f 1 2 print (fst x) here print will force evaluation of first value in pair, but not the second one. but you can improve it by telling 'if you need value of f, you should evaluate its components first': f a b = let x = a*b y = a+b in x `seq` y `seq` (x,y) this f definition will not evaluate x and y automatically. BUT its returned value is not (x,y). its returned value is x `seq` y `seq` (x,y) and when further computation try to use it in any way, it can't put hands on the pair before it will evaluate x and y values. are you understand? this technique therefore may be used to construct values that will be fully evaluated on any attempt to use any_ part of such value. say, f a = let x = .. y = .. z = .. in x `seq` y `seq` z `seq` T x y z g = let x = f 1 y = f 2 z = f 3 in x `seq` y `seq` z `seq` S x y z here value returned by g on any attempt to use it will force evaluation of two levels of data structure. this can be repeated again and again but writing to file or comparing does the same. that is difference. when you write value to file, you does all evaluations at once but before this moment you have large datastructure full of chunks built in memory. seq-ing technique can help when you build you structure step-by-step in some sequential environment (read monad) so, the following: main = do let x = g return $! (field1 x) will evaluate the whole value returned by g. but it will be equivalent to main = do let x = g'' return $! x==x where g'' - the same function without seqs to get real advantage, you need to build your value sequentially in monad and force evaluation of each step results: main = do let x = f 1 return $! x let y = f 2 return $! y let z = f 3 return $! z let a = T x y z .. so, the seq-ing technique will be better that you current one only in the case when values build are used to build other parts of these datastructure - in this case additional seq's may force evaluation of more part of datastructure than actually requested about your example - this monad is strict, i.e. its operations are sequenced like in IO monad itself (this monad just carries additional state information between IO operations). what you need to do - is to force that any updates/requests will force evaluation. then strictness of monad will guarantee you that evaluation will be perfomed at each step. this will work both for IO and your monad: do let x = a*b return $! x -- here x is evaluated the trick here is that where execution reaches the 'return $!' point, it needs to strictly evaluate value of 'return $! x' expression. this expression, that is equivalent to (x `seq` return x) need to evaluate x before it can return anything! as a result, 'return $! x' is executable statement (like putStr, for example) that force evaluation of x. i.e. it guarantees that x will be executed just at this moment, before executing next statement in 'do' block so, by inserting 'return $!' statements, you may force evaluation of thunks at given lines of your program, and of course you want to evaluate every thunk just at the moment it's created. now we need to look into your program and just find places where thunks are created:

data Mystate = Mystate {mystate :: [String]}

first rule of strict evaluation - use newtype instead of data for one-element constructors. newtype Mystate = Mystate {mystate :: [String]} is equivalent to data Mystate = Mystate {mystate :: ![String]} note '!' for making field strict. if you can't use newtype - make all fields strict next moment - [String] is a [[Char]], i.e. it's a lazy list of lazy lists. you should ensure that both levels of lists are strictly evaluated if you need to avoid thunks

type SL = StateT Mystate IO

getState :: SL [String] getState = do s <- get return $ mystate s

first place where we not strict enough. this expression will return _unevaluated_ thunk (mystate s). but you can force its evaluation before return:

return $! mystate s

so, your code return something like (mystate (Mystate ["a"])) while my code will evaluate this expression, throwing out function call, and return result of function evaluation: ["a"]. I should emphasize that it will not evaluate any thunks inside list of strings. but as long as your state is fully evaluated before storing, this operator will be able to return strictly evaluated value. it is how all this works

setState ns = modify (\s -> s {mystate = ns})

here you modify state, but don't ensure that string list is evaluated on both levels. well, it will be ok if you ensure evaluation at _each_ call to this function. alternatively, you can force evaluation before assignment by: setState ns = do return $! map length ns modify (\s -> s {mystate = ns})

getFile :: String -> SL () getFile p = do f <- liftIO $ readFile p let lns = lines f -- forces evaluation of lns liftIO $ putStrLn $ "Number of lines: " ++ show (length lns) setState lns promptLoop

here you evaluate only higher level of [String] before assigning it to state. but for this operation ('lines' on file contents) it's enough, we don't need to evaluate individual chars here

showLine :: Int -> SL () showLine nr = do s <- getState liftIO $ putStrLn $ s !! nr promptLoop

promptStr = "lFilename [load the file Filename] - sNr [show the line Nr of Filename] - q to quit"

promptLoop :: SL () promptLoop = do liftIO $ putStrLn promptStr str <- liftIO getLine case str of ('l':ss) -> getFile ss ('s':nr) -> showLine (read nr) ('q':[]) -> liftIO $ return ()

you can omit liftIO here, just return () will be ok :)

_ -> promptLoop

main = evalStateT promptLoop $ Mystate []

if StateT is strict monad transformer, this code don't have space leaks. you create thunks in two places, in one place you already evaluate it, and i wrote what to do in second place. for another code, you should watch assignments to state and ensure that assigned values are fully evaluated -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

Hello Andrea, Sunday, October 22, 2006, 6:06:24 PM, you wrote:

...

f a b = let x = a*b y = a+b in x `seq` y `seq` (x,y)

this f definition will not evaluate x and y automatically. BUT its returned value is not (x,y). its returned value is x `seq` y `seq` (x,y) and when further computation try to use it in any way, it can't put hands on the pair before it will evaluate x and y values. are you understand?

Yes, I do understand. But, as far as I know, "seq" will just evaluate x and y enough to see if they are not bottom. So, if x and y are a deep data structure, they won't be evaluated entirely, right?

x (and y) should be not considered here as data value! it's an expression which should be evaluated to bottom or non-bottom, i.e. some data constructor. but what if expression of x (i.e. thunk) by itself contains 'seq' call? say let x = 1/0 `seq` 1 y = x `seq` 2 print y try it ;) it will require to evaluate y value that requires to evaluate x that requires to eval 1/0! so when we construct some value we may ensure that all its parts will be evaluated once some part will be requested: x `seq` y `seq` T x y when you construct data values with seq recursively, this will lead to that whole deep datastructure will be evaluated once any part of it will be requested i don't propose you to do exactly this, just explain how this works and why works

That is to say:

...

to get real advantage, you need to build your value sequentially in monad and force evaluation of each step results:

main = do let x = f 1 return $! x let y = f 2 return $! y let z = f 3 return $! z let a = T x y z ..

...

...

...

setState ns = modify (\s -> s {mystate = ns})

here you modify state, but don't ensure that string list is evaluated on both levels. well, it will be ok if you ensure evaluation at _each_ call to this function. alternatively, you can force evaluation before assignment by:

setState ns = do return $! map length ns modify (\s -> s {mystate = ns})

this is the crucial point. You are forcing evaluation with $! map length, I'm doing it with writeFile. I do not see very much difference. That's an ad hoc solution. Since I need to write the state, instead of (needlessly) looking for the length of it's members, I write it...;-)

yes, it's the same. _right_ way is to use speciall deepSeq function that is like 'seq' but does full evaluation. unfortunately, haskell/ghc don't give us ready-to-use implementation. equality testing and other tricks are just the ways to make full evaluation of this datastructure and they are unnecessary if you really consume it all

By the way, the problem is not ns, but s, the old state. The new state has been evaluated by the code below (when we display the number of lines). So you need to change your code with:

do s <- getState modify (\s -> s {mystate = ns})

otherwise you are going to have the same space leak as my original code had. In other word, it is possible to have a user who keeps on loading files without looking at any line (in this case getState is never called and so there is no "return $! mystate s"!).

this '$!' only suppress one small thunk that contains mystate call on MyState: mystate (MyState s) => s. it don't evaluates anything else, so adding s<-getState will not change anything. if you want to do full evaluatin, you should add the same 'return $! map length state' to the getState, but instead you can add this just to setState :))) so, you don't need to use 'map length' in getState. you don't need to call getState in setState. and you may omit 'map length' call in setState if you will ensure that all calls to it fully evaluate this list. for beginning, in you non-toy code, you may add this call and see that will happen next, this line

modify (\s -> s {mystate = ns})

really produce unevaluated thunk. monad state will point to expression 's {mystate = ns}'. it's better to represent in functional style: setMyState s ns. as you can see, this thunk points to the old value of s. while you (and me) know that this value is really unused, RTS (GHC run-time system) don't know it! as a result, all old file contents are hold in memory until you evaluate this thunk :))) instead of 'modify' you should use the following sequence: s <- get put $! s {mystate = ns} it's my fault - i don't seen this memory leak until we digged into each step of evaluation :) you can run performGC at this moment to ensure that memory will never contain more than two file's contents. if you want to hold no more that one contents, use the following: setState [] performGC s <- getContents setState (lines s) although, i also suggest to add performGC after each substantial step (reading, conversion) and then try to remove one after one and see results

This produces the same as: setState ns = do s <- getState -- that does: return $ mystate s liftIO $ writeFile "/dev/null" s modify (\s -> s {mystate = ns})

as i just understood, the old 's' value is held in memory even after modify, so evaluating it really allow to reduce memory usage :) of course, using put$! should be even better

...

if StateT is strict monad transformer, this code don't have space leaks. you create thunks in two places, in one place you already evaluate it, and i wrote what to do in second place.

Yes, indeed. But just because we forced evaluation in a way that `seq` cannot do. Am I right?

yes, the strict evaluation order of this monad gives us possibility to evaluate thunks just at some steps of execution instead of linking evaluation to requests of data inside of some structure. strict monad gives us strict context on which we can rely

Thanks a lot for you patience. You did help me a lot. And this is not the first time. I appreciate. Really.

i like to teach :) -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

Hello Udo, Sunday, October 22, 2006, 6:41:24 PM, you wrote:

...

Now, the state will not be entirely consumed/evaluated by the user, and so it will not become garbage. Am I right?

No. The state cannot become garbage, because there is still a reference to it. As long as runStateT has not returned, any part of the state can still be accessed, so it is not garbage.

this monad state is not something fixed, it's completely replaced by each setState call (and old state becomes garbage from this moment). in particular, with this toy example, after reading each next file, old file contents continue its life as garbage

Completely evaluating the state will not reduce memory consumption in your case, because the list of lists won't be substantially smaller that the thunk to create it. In fact, evaluating this thunk will consume memory.

while this is true for this particular data (i.e., getContents >>= lines) in general this is not true. f.e. [[toUpper 'a']] list will need more memory in unevaluated form

...

Where should I force evaluation?

You can't. Your state really is that large, at least in the toy example. You'd need a different data structure ((Array Int ByteString) or (Map Int ByteString) come to mind) and then make that strict.

[ByteString] will be enough. Andrea, may be you can convert strings to bytestrings after hxt conversion? -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com