Unification, comparison

[Filip Konvička]

Hi,

>> 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.  This makes the traversal of data quite complex, and makes the 
> memory representation quite error-prone.  Currently only a variable can 
> become an indirection to something else.
> 
> In most programs, something like 99% of unifications are simple variable 
> bindings.  Very few actually require recursive unification.  Your idea 
> implies an overhead on *every* operation, even if you don't use the full 
> power of unification!  The current implementation provides a better 
> tradeoff for most cases.
> 
>> The main advantage is for memory usage -- it tends to reduce the 
>> number of
>> copies of identical structures, as the ones that are no longer referenced
>> are garbage collected. I don't remember where I first heard about this 
>> idea
>> (maybe on the C2 wiki?), but some Lisp implementations used it, I think.
> 
> I am not sure this is worth the effort.  My experience tells me that 
> this kind of tricks potentially brings more problems than solutions.

Since the constraint store is monotonic, I thought that the equality 
constraints (or even the equality test results) were cached in some way. 
I was not sure about the equality test, but I thought it that was clear 
for unification (I did have the idea of one of the variables 
"disappearing", which - as it seems - actually is the case only if the 
variable is free).

If making one of the variables being unified point to the other data 
structure is difficult, why not have a cache of *variables* that have 
been explicitly unified/tested for equality? (This may be stupid, but I 
wonder what would be the performance with such modification...)

Cheers,
Filip