<!doctype html public "-//W3C//DTD W3 HTML//EN">
<html><head><style type="text/css"><!--
blockquote, dl, ul, ol, li { padding-top: 0 ; padding-bottom: 0 }
--></style><title>Re: [clean-list] why does this program use so
little memor</title></head><body>
<div><br></div>
<div>Isaac Gouy wrote:</div>
<blockquote type="cite" cite>Someone has finally asked for an
explanation why this Clean program on<br>
the Computer Language Shootout seems to use so much less memory
than<br>
the other programs.<br>
<br>
I can only speculate, so I'd appreciate more knowledgeable<br>
explanations.<br>
</blockquote>
<blockquote type="cite"
cite
>http://shootout.alioth.debian.org/gp4/benchmark.php?test=binarytrees<span
></span>&lang=clean&id=0</blockquote>
<div><br></div>
<div>The Tree datatype in this program is not strict:</div>
<div><br></div>
<div><font face="Courier" size="+1" color="#000000">:: Tree a =
TreeNode a (Tree a) (Tree a) | Nil</font></div>
<div><font face="Courier" size="+1" color="#000000"><br></font></div>
<div><font face="Courier" size="+1" color="#000000">so the following
function that creates the Tree's in the program:</font></div>
<div><font face="Courier" size="+1" color="#000000"><br></font></div>
<div><font face="Courier" size="+1" color="#000000">bottomup ::
!</font><font face="Courier" size="+1"
color="#7F0055"><b>Int</b></font><font face="Courier" size="+1"
color="#000000"> !</font><font face="Courier" size="+1"
color="#7F0055"><b>Int</b></font><font face="Courier" size="+1"
color="#000000"> -> .(Tree</font><font face="Courier" size="+1"
color="#7F0055"><b> Int</b></font><font face="Courier" size="+1"
color="#000000">)</font></div>
<div><font face="Courier" size="+1" color="#000000">bottomup i
d</font></div>
<div><font face="Courier" size="+1" color="#000000"> | d
== 0</font></div>
<div><font face="Courier" size="+1"
color="#000000"> = TreeNode i Nil
Nil</font></div>
<div><font face="Courier" size="+1"
color="#000000"> = TreeNode i (bottomup
(2*i-1)(d-1)) (bottomup (2*i)(d-1))</font></div>
<div><font face="Courier" size="+1" color="#000000"><br></font></div>
<div><font face="Courier" size="+1" color="#000000">will create only
one TreeNode and 2 thunks, one for each bottomup</font></div>
<div><font face="Courier" size="+1" color="#000000">call, each time it
is called (except if d==0). If such a thunk</font></div>
<div><font face="Courier" size="+1" color="#000000">is evaluated, the
bottomup function is called again and another</font></div>
<div><font face="Courier" size="+1" color="#000000">TreeNode with 2
thunks is created (except if d==0), etc.</font></div>
<div><font face="Courier" size="+1" color="#000000">(actually part of
the TreeNode overwrites the thunk node).</font></div>
<div><font face="Courier" size="+1" color="#000000"><br></font></div>
<div><font face="Courier" size="+1" color="#000000">These Tree's are
traversed by the following function:</font></div>
<div><font face="Courier" size="+1" color="#000000"><br>
itemcheck Nil = 0<br>
itemcheck (TreeNode a left right)</font></div>
<div><font face="Courier" size="+1" color="#000000"> = a +
itemcheck(left) - itemcheck(right)</font></div>
<div><br></div>
<div>If this function is called with a TreeNode, the following
happens;</div>
<div><br></div>
<div>- The elements of the TreeNode (a, left and right) are moved to
registers</div>
<div> or the stack. The reference to this TreeNode is removed
from the register</div>
<div> or stack, so that the garbage collector can reclaim the
memory used</div>
<div> by this node (if this was the only reference).</div>
<div><br></div>
<div>- The integer a is evaluated and pushed on the stack. The
reference to</div>
<div> this integer node is removed from the register or
stack.</div>
<div><br></div>
<div>- left is evaluated and itemcheck is called with left as
argument. Other</div>
<div> references to left (within this function) are removed from
registers</div>
<div> or the stack, so that the garbage collector can reclaim
the memory used</div>
<div> by this node after the recursive call to itemcheck has
loaded the elements</div>
<div> of the TreeNode.</div>
<div><br></div>
<div>- the same happens for right: right is evaluated and itemcheck is
called</div>
<div> with right as argument. Other references to right are
removed from</div>
<div> registers or the stack, so that the garbage collector can
reclaim the</div>
<div> memory used by this node after the recursive call to
itemcheck has loaded</div>
<div> the elements of the TreeNode.</div>
<div><br></div>
<div>- the three integers (a and the results of the itemcheck calls)
are used to</div>
<div> compute the result of the function, and the function
returns.</div>
<div><br></div>
<div>Consequently, if itemcheck is applied to a Tree created by
bottomup, the</div>
<div>memory used by a TreeNode created by bottomup can be reclaimed
almost</div>
<div>immediately by the garbage collector after the elements are
loaded</div>
<div>in registers or pushed on the stack by itemcheck.</div>
<div>So the garbage will mark or copy at most one TreeNode and at most
2 thunks</div>
<div>and an Int node for each recursive call to itemcheck (that is
being evaluated).</div>
<div><br></div>
<div><br></div>
<div>So the low memory usage is caused by lazy evaluation. Other non
strict</div>
<div>languages like Haskell should have similar memory usage for this
program.</div>
<div><br></div>
<div><br></div>
<div>By the way, the program can be made faster by making the integer
in the</div>
<div>Tree strict and unboxed:</div>
<div><br></div>
<div><font face="Courier" size="+1" color="#000000">:: Tree = TreeNode
!Int Tree Tree | Nil</font></div>
<div><font face="Courier" size="+1" color="#000000"><br></font></div>
<div><font face="Courier" size="+1" color="#000000">bottomup ::
!</font><font face="Courier" size="+1"
color="#7F0055"><b>Int</b></font><font face="Courier" size="+1"
color="#000000"> !</font><font face="Courier" size="+1"
color="#7F0055"><b>Int</b></font><font face="Courier" size="+1"
color="#000000"> -> Tree</font></div>
<div><font face="Courier" size="+1" color="#000000"><br></font></div>
<div><br></div>
<div>Kind regards,</div>
<div><br></div>
<div>John van Groningen</div>
</body>
</html>