[m-dev.] hash consing

[Zoltan Somogyi]

> 	Calls to the specified constructors for the specified type
> 	should be tabled; as a result, equality checking and tabling
> 	for values of this type will be O(1) rather than O(N).

Only for terms whose principal functor is hashconsed.

> 	The mode checker should record that the result of a construction
> 		unification creating a term of a hash-consed type
> 		is not unique.

I thought more about this, and this is not enough. It must also record
that the *arguments* may also become non-unique; if this construction
is the first with the given arguments, then those arguments will be
recorded in the table and may be referred to from elsewhere.

Of course, it is possible that in the mode analysis code this effect
falls out as a consequence of the non-uniqueness of the term being constructed.

> 	Unification should be changed as follows.
> 	For partially hash-consed types, unify(in, in) would do a switch
> 	on the functor, and then for hash-consed functors it would
> 	just compare the address.
> 	For completely hash-consed types unify(in, in) should just compare
> 	the address; no switch is needed in this case.

This is what we should do with the present type-specific unification
predicates, although doing term address comparisons requires inserting
pragma C code into their bodies.

When we remove type-specific unifications in favor of interpreting
typeinfos, however, the situation changes. The cost of checking whether
the type is not trivial, and the test will fail most of the time. This is
distributed fat. It is probably more efficient for unify to do something
like this when it finds that the type_ctor_rep is du_type:

	if the two words are identical
		succeed
	compute the primary tags
	if different
		fail
	look up the primary tag descriptor
	if no secondary tag
		goto same_functor
	if remote secondary tag
		compute secondary tags
		if different
			fail
		find functor descriptor
	else if local secondary tag
		compute secondary tags
		if different
			fail
		find functor descriptor
	else
		/* no secondary tag */
		find functor descriptor
	if the two words are identical
		succeed
	if functor descriptor says functor is hash-consed
		fail
	else
		compare arguments left to right

One of the two occurrences of "if the two words are identical, succeed"
should be deleted, but it is an open question which one; each will be
better than the other for some workloads.

The comparison code should be similar, except that "failure" now requires
deciding between < and >.

There was also one other optimization we discussed. At the moment,
when the implementation of a predicate with pragma memo finds that the
current input arguments have been seen before, it checks whether that
previous call has finished yet or not. If not, then that call has an
infinite loop. This check can be omitted if termination analysis has
proven that the predicate always terminates (has strictly decreasing
argument sizes in recursive calls).

On the compilation environment front, we discussed the idea that
the tabling stuff should be moved out of private_builtin.m into a new
module (e.g. table_builtin), which would not be automatically imported;
instead any memo pragma in the input should also act as an
"import_module table_builtin". This should reduce most compilation times.

Yet another item in our discussion was that each tabling memo should
have three variants: the current one, one in which the table is garbage
collectable (which allows the implementation to offer better guarantees
about space consumption at the expense of fewer guarantees about execution
time), and one in which the tabling is only probabilistic. The last option
probably does not make sense for minimal model tabling.

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