You got me there. Excellent point On Tuesday, August 28, 2012, Yves Parès wrote:

Monad? Simple strictness anotation is enough in that case:

upd_noupd n = let l = myenum' 0 n h = head l in h `seq` last l + h

Le mardi 28 août 2012 22:39:09 UTC+2, Carter Schonwald a écrit :

...

Hey Joachim, isn't this an example where the exact same issue could be solved via some suitable use of a monad for ordering those two computations on l?

cheers -Carter

On Tue, Aug 28, 2012 at 12:44 PM, Joachim Breitner wrote:

...

Dear GHC users,

I am experimenting with ways to /prevent/ sharing in Haskell, e.g. to avoid space leaks or to speed up evaluation. A first attempt was to duplicate closures on the heap to preserve the original one, see http://arxiv.org/abs/1207.2017 for a detailed description and information on the prototype implementation; no GHC patching required for that.

Currently I am trying a different angle: Simply avoid generating the code that will update a closure after its evaluation; hence the closure stays a thunk and will happily re-evaluate the next time it is used.

Here is a classical example. Take this function (it is basically [f..t] but with a fixed type and no risk of existing rules firing):

myenum :: Int -> Int -> [Int] myenum f t = if f <= t then f : myenum (f + 1) t else []

and this example where sharing hurts performance badly:

upd_upd n = let l = myenum 0 n in last l + head l

The problem is that during the evaluation of "last l", the list is live and needs to be kept in memory, although in this case, re-evaluating l for "head l" would be cheaper. If n is 50000000, then this takes 3845ms on my machine, measured with criterion, and a considerable amount of memory (3000MB).

So here is what you can do now: You can mark the value as non-updateable. We change myenum to

myenum' :: Int -> Int -> [Int] myenum' f t = if f <= t then f : ({-# NOUPDATE #-} myenum' (f + 1) t) else []

and use that:

upd_noupd n = let l = myenum' 0 n in last l + head l

The improvement is considerable: 531ms and not much memory used (18MB)

Actually, it should suffice to put the pragma in the definition of l without touching myenum:

noupd_noupd n = let l = {-# NOUPDATE #-} myenum 0 n in last l + head l

but this does not work with -O due to other optimizations in GHC. (It does work without optimization.)

The next step would be to think of conditions under which the compiler could automatically add the pragma, e.g. when it sees that evaluation a thunk is very cheap but will increase memory consumption considerable.

Also this does not have to be a pragma; it could just as well be a function "noupdate :: a -> a" that is treated specially by the compiler, similar to the "inline" function.

If you want to play around this, feel free to fetch it from the unshare branch of my ghc repository at http://git.nomeata.de/?p=ghc.**githttp://git.nomeata.de/?p=ghc.gitor https://github.com/nomeata/ghc for the GitHub-lovers. Note that the branch is repeatedly rebased against ghc master.

Greetings, Joachim

-- Dipl.-Math. Dipl.-Inform. Joachim Breitner Wissenschaftlicher Mitarbeiter http://pp.info.uni-karlsruhe.**de/~breitnerhttp://pp.info.uni-karlsruhe.de/%7Ebreitner

______________________________**_________________ Haskell-Cafe mailing list Haskel...@haskell.org http://www.haskell.org/**mailman/listinfo/haskell-cafehttp://www.haskell.org/mailman/listinfo/haskell-cafe