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
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
