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

[Carter Schonwald]

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... 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<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... at haskell.org
>>> http://www.haskell.org/**mailman/listinfo/haskell-cafe<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/0705855d/attachment.htm>