[clean-list] why does this program use so little memory?

[John van Groningen]

Isaac Gouy wrote:
>Someone has finally asked for an explanation why this Clean program on
>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
>explanations.
>
>http://shootout.alioth.debian.org/gp4/benchmark.php?test=binarytrees&lang=clean&id=0

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 registers
   or the stack. The reference to this TreeNode is removed from the register
   or stack, so that the garbage collector can reclaim the memory used
   by this node (if this was the only reference).

- The integer a is evaluated and pushed on the stack. The reference to
   this integer node is removed from the register or stack.

- left is evaluated and itemcheck is called with left as argument. Other
   references to left (within this function) are removed from registers
   or the stack, so that the garbage collector can reclaim the memory used
   by this node after the recursive call to itemcheck has loaded the elements
   of the TreeNode.

- the same happens for right: right is evaluated and itemcheck is called
   with right as argument. Other references to right are removed from
   registers or the stack, so that the garbage collector can reclaim the
   memory used by this node after the recursive call to itemcheck has loaded
   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, the
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 thunks
and an Int node for each recursive call to itemcheck (that is being evaluated).


So the low memory usage is caused by lazy evaluation. Other non strict
languages like Haskell should have similar memory usage for this program.


By the way, the program can be made faster by making the integer in the
Tree strict and unboxed:

:: Tree = TreeNode !Int Tree Tree | Nil

bottomup :: !Int !Int -> Tree


Kind regards,

John van Groningen
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.science.ru.nl/pipermail/clean-list/attachments/20061114/87d53be8/attachment.html