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 <breit...@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 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 > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > >
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe