[Haskell-cafe] A first glimps on the {-# NOUPDATE #-} pragma

[Carter Schonwald]

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 <breitner at 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120828/553d3982/attachment.htm>