[m-dev.] Re: [mercury-users] tabling

[Fergus Henderson]

On 30-Nov-2000, Zoltan Somogyi <zs at cs.mu.OZ.AU> wrote:
> 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.

For a GC tailored to Mercury, that's true, but for a plug-in GC that does
not know about Mercury, such as the ones used for the .NET and Java ports,
the burden does seem to me to be at least somewhat onerous.  Knowing
about roots is easy enough; either the GC will follow global variables
automatically or it will provide a way to register new roots (together
with their types).  But having to know about pointer hash tables and
treat them specially is much more difficult; off-hand I'm not sure
whether .NET or Java provide anything like that.  (These two systems
do provide hash consing support, though; it might be possible to use
that.)

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

That's true for our currently supported implementations, i.e. for `--gc
conservative' and `--gc none', but for `--gc accurate' the implementation
that I posted won't work; we'd need to use `c_pointer' rather than `int'
for the address type, and we'd need to teach the tabling implementation
how to table `c_pointer' values.

> In fact, any approach that requires the runtime to know about object(T)
> as a special type would impose distributed fat.

`c_pointer' already needs to be handled specially, so using
`c_pointer' rather than `int' for the address type would impose
no additional distributed fat.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------