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.
For example, suppose that the Oz source contains an equality test
"<variableA> == <expressionB>", where expression evaluates to <valueB>.
Using pseudo-C notation, this would be compiled to a primitive
"variableEqualsValue(&variableA, valueB)":
bool variableEqualsValue(variable *pvarA, value *pvalB) {
value *pvalA = derefVariable(pvarA); /* may block if undetermined */
if (pvalA == pvalB) return true;
if (valueEqualsValue(pvalA, pvalB)) {
+ setVariable(pvarA, pvalB);
return true;
}
return false;
}
Similarly, "<variableA> == <variableB>" would be compiled to a primitive:
bool variableEqualsVariable(variable *pvarA, variable *pvarB) {
value *pvalA = derefVariable(pvarA); /* may block if undetermined */
value *pvalB = derefVariable(pvarB); /* may block if undetermined */
if (pvalA == pvalB) return true;
if (valueEqualsValue(pvalA, pvalB)) {
+ if (pvalA < pvalB) { /* raw address comparison */
+ setVariable(pvarB, pvalA);
+ } else {
+ setVariable(pvarA, pvalB);
+ }
return true;
}
return false;
}
Unification can be handled similarly. It does not matter whether the
variables are single-assignment or fully mutable (since we only set them
to a value structurally equal to their current value).
The primitives are presented as functions for illustration; anything that
is inlined would still be inlined. The additional code relative to what an
implementation must do already is in the lines marked +. Note that this code
is only on the "slow path", where the values are structurally equal but not
address-equal.
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 optimization also applies whenever "valueEqualsValue" notices that two
substructures are equal, even if the overall values on which it was called
are not equal.
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.
--
David Hopwood <[EMAIL PROTECTED]>
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
