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. 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.
Is System.eq supposed to be guaranteed to distinguish between structurally
equal values that have been bound together? If so then this would prevent
the above optimization -- but perhaps its specification is too strong in
that case.
Yes. System.eq just tests whether its arguments, which actually are
memory references, are identical. It does not take into account
structual equality.
Cheers,
raph
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
