On 21/12/05, Tomasz Zielonka
On Wed, Dec 21, 2005 at 07:13:07PM +0000, Philippa Cowderoy wrote:
Try running
putStrLn (unlines (repeat "hello!"))
You may be surprised ;-)
Or not ;-) But yes, I should've checked and my comments on how that'll behave stand. It would be nice to think something clever could happen regarding memory management as well, but I'm familiar enough with GCed systems by now to be somewhat wary of cleverness.
I don't know how it's done, but when you compile it with 'ghc -O2', the program runs in constant space. Unfortunately with Hugs and GHCi it grows.
It really shouldn't grow at all, and at least in my short tests in ghci and hugs, it doesn't grow for me. The putStrLn won't force any more of the string than it wants to print at any moment, and afterward, that part of the string is garbage, and should get collected right away. There are two ways to make a Haskell program more efficient: Make it stricter, or make it lazier. What do I mean by the latter? Simply that if you can design each part of your program (as much as possible) to be able to output something only given a small prefix of its input, then you'll often see some really nice efficiency. The pipeline scheduler which I wrote for a summer job made heavy use of this fact, and at a few points in the design/coding, I made ridiculously large performance gains in both memory consumption and runtime simply by making sure that lists and other structures were lazily produced. In the end, the result was a (combinatorially large) list of all the possible schedules for the given input code, in order of algorithm greediness. Taking the head of the list was essentially running the greedy algorithm, but if the greedy solution, say, couldn't be register allocated, the next item in the list could be observed, which would backtrack a bit and find another. In fact, the entire algorithm was designed this way. That's essentially what the list monad gives you, after all. Leaning on laziness can result in very elegant generative algorithms which run quite quickly. Strictness is really only desired when you are trying to collapse something large down into a small summary. That's what things like foldl' are for. - Cale