Unification, comparison

[Raphael Collet]

David Hopwood wrote:
> Raphael Collet wrote:
>> David Hopwood wrote:
>>
>>> Hmm. I believe the following optimization is worth considering: when two
>>> variables are either bound together or successfully tested for structural
>>> equality, set both to point to the structure with the lower address.
>>>
>>> (Note that this only incurs extra overhead in the slow path where the
>>> full unification or structural equality algorithms are needed, not in the
>>> fast paths where they either already have the same address, or one was
>>> unbound.)
>> Your suggestion implies that the memory representation of a record could
>> be turned into an indirection to another representation of the same
>> record.
> 
> I explained this poorly. The intent was that no extra indirections are added;
> the optimization only applies to cases where there is already an indirection.

Please read carefully my former reply:
http://www.mozart-oz.org/pipermail/mozart-users/2006/014360.html

I checked Mozart's unification procedure, and the "optimization" is 
possible.  A few nontrivial modifications are necessary, though.  But I 
am still not convinced it is worth the effort.

> If the same comparison is done one more time, then the optimization will
> pay off. In some cases, where it leads to a large data structure becoming
> unreachable, it can pay off spectacularly, in terms of memory use and cache
> behaviour. (This is the rationale behind preferring the lower address: you
> want to consistently choose the same instance of the structure to survive.)

The problem is that the case you are mentioning simply never happens in 
most programs!

> In some implementations of GC'd languages, especially those with concurrent
> GC (see <http://citeseer.csail.mit.edu/huelsbergen93concurrent.html>), and
> lazy functional languages, it is already the case that any object access
> might have to traverse a forwarding pointer. Then the optimization can be
> applied in more cases.

We use that technique during GC, but this phase is not interleaved with 
code interpretation.

Cheers,
raph