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