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 <brei...@kit.edu>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.**git<http://git.nomeata.de/?p=ghc.git>or >>> 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/~breitner<http://pp.info.uni-karlsruhe.de/%7Ebreitner> >>> >>> ______________________________**_________________ >>> Haskell-Cafe mailing list >>> haskel...@haskell.org >>> http://www.haskell.org/**mailman/listinfo/haskell-cafe<http://www.haskell.org/mailman/listinfo/haskell-cafe> >>> >>> >>
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe