[mercury-users] Structure reuse

Michael Day mikeday at yeslogic.com
Tue Jul 15 09:50:38 AEST 2003


> Are you really trying to reduce the program's space usage, or just to
> improve its locality and speed?

Ultimately I am trying to improve its speed, however in this case that
would appear to require improving its locality and reducing its space
usage (to avoid thrashing).

> Generally structure reuse optimization will only improve the speed of
> the program, not its space usage.  The reason is that the memory which
> structure reuse reuses is garbage anyway; if structure reuse optimization
> is not done, the memory will be reclaimed automatically by the garbage
> collector.  The advantage of structure reuse is that it increases speed
> by improving locality and by making garbage collections less frequent.

I realise that the memory will eventually be reclaimed by the garbage
collector, but I'm hazy as to exactly *when* it will be reclaimed.

For example, given this predicate for updating a tree:

update(T0, T) :-
    update0(T0, T1),
    update1(T1, T2),
    ...
    updateN(TN, T).

Each of the updateN predicates will traverse the entire tree, modifying
particular fields to create a new tree. The frequency of garbage
collection will affect the memory usage of this code.

If garbage collection is continuous, or extremely frequent, it will be
able to reclaim each tree node as they are modified, which is what I would
love to be able to achieve with structure reuse. That way, only one tree
exists throughout the entire update process.

If garbage collection takes place roughly after each updateN call, then
each predicate will build a copy of the tree and then the old one will be
destroyed, requiring memory to hold two trees.

If garbage collection takes place infrequently, say after the entire
update process, or when it feels that memory is getting tight, or when it
starts swapping, then it will require memory to hold N trees.

It would be nice to be able to write code like this and have the compiler
determine that it can update the tree in-place, eliminating unnecessary
copying and memory allocation, improving locality, reducing memory usage
and so on. I have no idea whether that is feasible though, or whether it 
would require assistance from the programmer by specifying unique modes or 
something like that.

Cheers,

Michael

-- 
YesLogic Prince prints XML!
http://yeslogic.com

--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------



More information about the users mailing list