I had a look at this. It's an old chestnut: lazy pattern matching. You have let ((commands, s), x) = run (read iters) 5 in do ...do something with commands... print x Trouble is, the 'x' hangs onto both components of the pair, even though it only needs one. It's not enough to force the pair earlier, which you probably tried, because the state monad you are using is itself lazy, and uses masses of lazy pattern matching. You could return the state paired with each item, rather than just the state at the end, perhaps, or use a stricter state monad. This lazy-pattern-matching leak is a well-known problem, to which I do not know a good solution. There was a paper from Chalmers about 8 years ago about building more cleverness into the compiler, but it amounted to extending Core with a lazy tuple binding. Fair enough, but quite a big addition to Core and one I've never done. better ideas welcome simon | -----Original Message----- | From: glasgow-haskell-users-bounces@haskell.org [mailto:glasgow-haskell-users- | bounces@haskell.org] On Behalf Of Ian Lynagh | Sent: 12 June 2004 18:54 | To: glasgow-haskell-users@haskell.org | Subject: Space usage | | | Hi all, | | My intuition tells me that the code in | | http://urchin.earth.li/~ian/Mem.hs | | should have the same space usage regardless of whether USESMEM is | defined. However, when compiling with | | ghc -Wall -O2 -cpp --make Mem -o mem | | and running | | ./mem True 100000 > /dev/null | | it runs in constant space but compiling with | | ghc -Wall -O2 -cpp -DUSESMEM --make Mem -o mem | | and running in the same way it increases up to >100M. | | Is this an instance of GHC not being as smart as it could? | | Or is it a case in which I need to give it additional strictness | annotations in order to get it to run in constant space (and if so, | what annotations would be best?)? | | | Thanks | Ian | | _______________________________________________ | Glasgow-haskell-users mailing list | Glasgow-haskell-users@haskell.org | http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
"Simon Peyton-Jones"
I had a look at this. It's an old chestnut: lazy pattern matching. You have let ((commands, s), x) = run (read iters) 5 in do ...do something with commands... print x
Trouble is, the 'x' hangs onto both components of the pair, even though it only needs one.
This lazy-pattern-matching leak is a well-known problem, to which I do not know a good solution. There was a paper from Chalmers about 8 years ago about building more cleverness into the compiler, but it amounted to extending Core with a lazy tuple binding. Fair enough, but quite a big addition to Core and one I've never done.
You probably mean J. Sparud, "Fixing Some Space Leaks without a Garbage Collector", FPCA'93. http://citeseer.ist.psu.edu/sparud93fixing.html as implemented in hbc. It is also possible to use Wadler's garbage-collector fix for this space leak, as implemented in nhc98. P Wadler, "Fixing a Space Leak with a Garbage Collector", SP&E Sept 1987. When the GC discovers a selector function applied to an evaluated argument, it "evaluates" the selector on-the-fly by just swizzling pointers. It needs some co-operation from the compiler to make selector functions look obvious, but that isn't too difficult. Regards, Malcolm
On Tuesday 17 Aug 2004 5:11 pm, Malcolm Wallace wrote:
It is also possible to use Wadler's garbage-collector fix for this space leak, as implemented in nhc98. P Wadler, "Fixing a Space Leak with a Garbage Collector", SP&E Sept 1987.
When the GC discovers a selector function applied to an evaluated argument, it "evaluates" the selector on-the-fly by just swizzling pointers. It needs some co-operation from the compiler to make selector functions look obvious, but that isn't too difficult.
So ghc doesn't do this (or something better)? I'm surprised because it seems like a really basic and simple feature to me. I implemented a toy FPL a few years ago and even my gc incorporated this optimisation. It's a bit strange that this should have been overlooked considering in all other respects ghc is far more sophisticated than my efforts were :-) Regards -- Adrian Hey
Adrian Hey wrote:
On Tuesday 17 Aug 2004 5:11 pm, Malcolm Wallace wrote:
It is also possible to use Wadler's garbage-collector fix for this space leak, as implemented in nhc98. P Wadler, "Fixing a Space Leak with a Garbage Collector", SP&E Sept 1987.
When the GC discovers a selector function applied to an evaluated argument, it "evaluates" the selector on-the-fly by just swizzling pointers. It needs some co-operation from the compiler to make selector functions look obvious, but that isn't too difficult.
So ghc doesn't do this (or something better)? I'm surprised because it seems like a really basic and simple feature to me. I implemented a toy FPL a few years ago and even my gc incorporated this optimisation. It's a bit strange that this should have been overlooked considering in all other respects ghc is far more sophisticated than my efforts were :-)
As Simon pointed out, it's not so easy to do this with an optimizing compiler that may inline selector functions. The "right" way to do this is to have specialized code that runs during GC for each thunk. This was investigated in Christina von Dorrien's licentiate thesis "Stingy evaluation". -- Lennart
Simon Peyton-Jones wrote:
I had a look at this. It's an old chestnut: lazy pattern matching. You have let ((commands, s), x) = run (read iters) 5 in do ...do something with commands... print x
Trouble is, the 'x' hangs onto both components of the pair, even though it only needs one.
It's not enough to force the pair earlier, which you probably tried, because the state monad you are using is itself lazy, and uses masses of lazy pattern matching.
You could return the state paired with each item, rather than just the state at the end, perhaps, or use a stricter state monad.
This lazy-pattern-matching leak is a well-known problem, to which I do not know a good solution. There was a paper from Chalmers about 8 years ago about building more cleverness into the compiler, but it amounted to extending Core with a lazy tuple binding. Fair enough, but quite a big addition to Core and one I've never done.
Simon, I suggest that you take another look at Jan Sparud's paper. No extension of Core is needed to implement it. All that is needed is a strange (impure) primitive function. To maintain type correctness you also need a family of functions that are really the identity, but with different types. Read the paper, I think you could add it to ghc without too much trouble. -- Lennart
participants (4)
-
Adrian Hey -
Lennart Augustsson -
Malcolm Wallace -
Simon Peyton-Jones