You got me there. Excellent point<span></span><br><br>On Tuesday, August 28, 2012, Yves Parès  wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Monad? Simple strictness anotation is enough in that case:<br>
<br>        upd_noupd n =<br>
            let l = myenum&#39; 0 n<br>                h = head l<br>
            in h `seq` last l + h<br><br>Le mardi 28 août 2012 22:39:09 UTC+2, Carter Schonwald a écrit :<blockquote class="gmail_quote" style="margin:0;margin-left:0.8ex;border-left:1px #ccc solid;padding-left:1ex">Hey Joachim,<div>
isn&#39;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?</div><div><br></div><div>cheers</div><div>-Carter<br><br><div class="gmail_quote">


On Tue, Aug 28, 2012 at 12:44 PM, Joachim Breitner <span dir="ltr">&lt;<a>brei...@kit.edu</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

Dear GHC users,<br>
<br>
I am experimenting with ways to /prevent/ sharing in Haskell, e.g. to<br>
avoid space leaks or to speed up evaluation. A first attempt was to<br>
duplicate closures on the heap to preserve the original one, see<br>
<a href="http://arxiv.org/abs/1207.2017" target="_blank">http://arxiv.org/abs/1207.2017</a> for a detailed description and<br>
information on the prototype implementation; no GHC patching required<br>
for that.<br>
<br>
Currently I am trying a different angle: Simply avoid generating the<br>
code that will update a closure after its evaluation; hence the closure<br>
stays a thunk and will happily re-evaluate the next time it is used.<br>
<br>
Here is a classical example. Take this function (it is basically [f..t]<br>
but with a fixed type and no risk of existing rules firing):<br>
<br>
        myenum :: Int -&gt; Int -&gt; [Int]<br>
        myenum f t = if f &lt;= t<br>
                     then f : myenum (f + 1) t<br>
                     else []<br>
<br>
and this example where sharing hurts performance badly:<br>
<br>
        upd_upd n =<br>
            let l = myenum 0 n<br>
            in last l + head l<br>
<br>
The problem is that during the evaluation of &quot;last l&quot;, the list is live<br>
and needs to be kept in memory, although in this case, re-evaluating l<br>
for &quot;head l&quot; would be cheaper. If n is 50000000, then this takes 3845ms<br>
on my machine, measured with criterion, and a considerable amount of<br>
memory (3000MB).<br>
<br>
So here is what you can do now: You can mark the value as<br>
non-updateable. We change myenum to<br>
<br>
        myenum&#39; :: Int -&gt; Int -&gt; [Int]<br>
        myenum&#39; f t = if f &lt;= t then f : ({-# NOUPDATE #-} myenum&#39; (f + 1) t) else []<br>
<br>
and use that:<br>
<br>
        upd_noupd n =<br>
            let l = myenum&#39; 0 n<br>
            in last l + head l<br>
<br>
The improvement is considerable: 531ms and not much memory used (18MB)<br>
<br>
<br>
Actually, it should suffice to put the pragma in the definition of l<br>
without touching myenum:<br>
<br>
        noupd_noupd n =<br>
            let l = {-# NOUPDATE #-} myenum 0 n<br>
            in last l + head l<br>
<br>
but this does not work with -O due to other optimizations in GHC. (It<br>
does work without optimization.)<br>
<br>
<br>
The next step would be to think of conditions under which the compiler<br>
could automatically add the pragma, e.g. when it sees that evaluation a<br>
thunk is very cheap but will increase memory consumption considerable.<br>
<br>
<br>
Also this does not have to be a pragma; it could just as well be a<br>
function &quot;noupdate :: a -&gt; a&quot; that is treated specially by the compiler,<br>
similar to the &quot;inline&quot; function.<br>
<br>
<br>
If you want to play around this, feel free to fetch it from the unshare<br>
branch of my ghc repository at <a href="http://git.nomeata.de/?p=ghc.git" target="_blank">http://git.nomeata.de/?p=ghc.<u></u>git</a> or<br>
<a href="https://github.com/nomeata/ghc" target="_blank">https://github.com/nomeata/ghc</a> for the GitHub-lovers. Note that the<br>
branch is repeatedly rebased against ghc master.<br>
<br>
<br>
Greetings,<br>
Joachim<br>
<span><font color="#888888"><br>
<br>
--<br>
Dipl.-Math. Dipl.-Inform. Joachim Breitner<br>
Wissenschaftlicher Mitarbeiter<br>
<a href="http://pp.info.uni-karlsruhe.de/%7Ebreitner" target="_blank">http://pp.info.uni-karlsruhe.<u></u>de/~breitner</a><br>
</font></span><br>______________________________<u></u>_________________<br>
Haskell-Cafe mailing list<br>
<a>Haskel...@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/<u></u>mailman/listinfo/haskell-cafe</a><br>
<br></blockquote></div><br></div>
</blockquote></blockquote>