[clean-list] why does this program use so little memory?
igouy2 at yahoo.com
Fri Nov 17 18:36:03 MET 2006
Thank you, I'll attach that explanation to the program.
--- John van Groningen <johnvg at cs.ru.nl> wrote:
> Isaac Gouy wrote:
> >Someone has finally asked for an explanation why this Clean program
> >the Computer Language Shootout seems to use so much less memory than
> >the other programs.
> >I can only speculate, so I'd appreciate more knowledgeable
> The Tree datatype in this program is not strict:
> :: Tree a = TreeNode a (Tree a) (Tree a) | Nil
> so the following function that creates the Tree's in the program:
> bottomup :: !Int !Int -> .(Tree Int)
> bottomup i d
> | d == 0
> = TreeNode i Nil Nil
> = TreeNode i (bottomup (2*i-1)(d-1)) (bottomup (2*i)(d-1))
> will create only one TreeNode and 2 thunks, one for each bottomup
> call, each time it is called (except if d==0). If such a thunk
> is evaluated, the bottomup function is called again and another
> TreeNode with 2 thunks is created (except if d==0), etc.
> (actually part of the TreeNode overwrites the thunk node).
> These Tree's are traversed by the following function:
> itemcheck Nil = 0
> itemcheck (TreeNode a left right)
> = a + itemcheck(left) - itemcheck(right)
> If this function is called with a TreeNode, the following happens;
> - The elements of the TreeNode (a, left and right) are moved to
> or the stack. The reference to this TreeNode is removed from the
> or stack, so that the garbage collector can reclaim the memory
> by this node (if this was the only reference).
> - The integer a is evaluated and pushed on the stack. The reference
> this integer node is removed from the register or stack.
> - left is evaluated and itemcheck is called with left as argument.
> references to left (within this function) are removed from
> or the stack, so that the garbage collector can reclaim the memory
> by this node after the recursive call to itemcheck has loaded the
> of the TreeNode.
> - the same happens for right: right is evaluated and itemcheck is
> with right as argument. Other references to right are removed from
> registers or the stack, so that the garbage collector can reclaim
> memory used by this node after the recursive call to itemcheck has
> the elements of the TreeNode.
> - the three integers (a and the results of the itemcheck calls) are
> used to
> compute the result of the function, and the function returns.
> Consequently, if itemcheck is applied to a Tree created by bottomup,
> memory used by a TreeNode created by bottomup can be reclaimed almost
> immediately by the garbage collector after the elements are loaded
> in registers or pushed on the stack by itemcheck.
> So the garbage will mark or copy at most one TreeNode and at most 2
> and an Int node for each recursive call to itemcheck (that is being
> So the low memory usage is caused by lazy evaluation. Other non
> languages like Haskell should have similar memory usage for this
> By the way, the program can be made faster by making the integer in
> Tree strict and unboxed:
> :: Tree = TreeNode !Int Tree Tree | Nil
> bottomup :: !Int !Int -> Tree
> Kind regards,
> John van Groningen
Compare mortgage rates for today.
Get up to 5 free quotes.
More information about the clean-list