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

[Arjen]

Great, such explanations do make the programs more readable.

Unfortunately, this Clean entry is now disqualified. Other lazy 
functional languages, which use lazy trees, are valid.

Maybe someone can explain why Clean #3 performs so poor compared to 
OCaml and MLton? The Clean Tree type is already specialized and strict.

regards,
	Arjen


Isaac Gouy wrote:
> 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
>> 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
> 
> 
> 
>  
> ____________________________________________________________________________________
> Sponsored Link
> 
> Compare mortgage rates for today. 
> Get up to 5 free quotes. 
> Www2.nextag.com
> _______________________________________________
> clean-list mailing list
> clean-list at science.ru.nl
> http://mailman.science.ru.nl/mailman/listinfo/clean-list