[mercury-users] tabling

[Zoltan Somogyi]

I wrote:
> We could add an optional argument to the pragma memo declaration to tell the
> compiler that a given set of arguments should be tabled by address, not by
> value.

On 29-Nov-2000, Fergus Henderson <fjh at cs.mu.OZ.AU> wrote:
> The main difficulty with this proposal is that for implementations
> with garbage collectors that move objects and that don't preserve the
> relative ordering of pointers, a table of addresses would have to be
> searched using linear search.  So on some implementations you might
> get radically worse performance if there are many different values
> for those arguments in the table.

Any such garbage collector would need to be aware of the tables, because they
are roots, and may be the only root pointing to a still live data structure.
The relevant tabling data structure is a hash table; when an address changes,
its hash value does too. Requiring the collector to preserve the validity of
the hash table by rehashing its elements does not seem too onerous a burden.

> The advantage of this approach is that you can table on structured
> data with some fields of the structured data being tabled by address
> and other fields tabled by value.  Also it doesn't require any new syntax;
> only the object(T) type and the tabling routines in the runtime library
> need to know about it, not the compiler front-end.

Actually, with the definitions in your mail, the tabling routines in the
runtime do *not* need to know about object(T); they can be used unchanged.
In fact, any approach that requires the runtime to know about object(T)
as a special type would impose distributed fat.

Your approach would seem to be the best solution to MC's current problem.

Zoltan.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------