www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Proposal: Operator overloading without temporaries

reply Don Clugston <dac nospam.com.au> writes:
Background: Operator overloading, in the form it exists in C++ and 
currently in D, inherently results in sub-optimal code, because it 
always results in unnecessary temporary objects being created.

For example,
X = A - ((B*C) + D)* E;

becomes:
T1 = B * C;
T2 = T1 + D;
T3 = T2 * E;
T4 = A - T3;
X = T4;
Four objects were created, whereas only one was strictly required.
In C++, there are libraries like Blitz++ which use complicated 
expression templates in order to avoid these creating these temporaries, 
and provide performance comparable with FORTRAN. I think D can do much 
better...
Note that temporaries are avoided when using the opXXXAssign() operators 
like +=.

===========
   Proposal
===========
(1) Allow the compiler to assume that b = b + c  can be replaced with b 
+= c. (In C++, operator + and operator += are just symbols, the compiler 
doesn't know that there is any relationship between them).
In the example above, this would allow the compiler to generate:
T1 = B * C;
T1 += D;
T1 *= E;

and we have eliminated two of the three temporaries.
(2). Fill in the gaps in the operator overloading table by introducing
opAddAssign_r, opSubAssign_r, etc.

Just as A.opSubAssign(B)
is the operation  A -= B  or equivalently  A = A - B, similarly

A.opSubAssign_r(B)
would mean
A = B - A.
and would only occur when temporaries are generated in expressions. Like 
-=, it's an operation which can frequently be performed very 
efficiently, but at present the language has no way of expressing it.

Our original example then becomes:

T1 = B.opMul(C);
T1.opAddAssign(D);
T1.opMulAssign(E);
T1.opSubAssign_r(A);
X = T1;
... and all the useless temporaries are gone!

More formally, when the expression tree for an expression is generated:
With a binary operator XXX, operating on left & right nodes:

if (the left node is *not* an original leaf node) {
    // the left node is a temporary, does not need to be preserved.
    // we don't care if the right node is a temporary or not
    look for opXXXAssign().
} else if (the the right node is not an original leaf node) {
    // the right node is a temporary
    look for opXXXAssign_r()
} else {
   // both left and right nodes are leaf nodes, we have to
   // create a temporary
    look for opXXX(), just as it does now.
}

These rules also cope with the situation where temporaries are required:
eg
X = (A*B) + (C*D);
becomes
T1 = A*B;
T2 = C*D;
T1 += T2;
X = T1;

If this were implemented, it would permanently eradicate (for D) the 
most significant advantage which Fortran has managed to retain over 
object-oriented languages. And I really don't think it would be 
difficult to implement, or have negative side-effects.

There are a couple of decisions to be made:
(I) should the compiler use opAdd() and generate a temporary, if 
opAddAssign_r() doesn't exist, to preserve existing behaviour? I think 
the answer to this is YES.
(II) should the compiler use opAdd() and generate a temporary, if 
oppAddAssign() doesn't exist, to preserve existing behaviour? Again, I'm 
inclined to answer YES.
(III) If the code includes +=, and there is an opAdd() but no 
opAddAssign(), should the compiler accept this, and just generate an 
opAdd() followed by an assignment?? This would mean that opAdd() would 
generate the += operation as well as +, while opAddAssign() would be a 
performance enhancement. (It would still be possible to have 
opAddAssign() without opAdd(), to have += but not +, but it would not be 
possible to have + without +=). This would mean that += would be 
*purely* syntactic sugar.

Decision III would be a little more difficult to implement and is of 
less obvious merit, I only mention it as a possibility.

Comments?
Mar 27 2006
next sibling parent "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"Don Clugston" <dac nospam.com.au> wrote in message 
news:e087or$dgm$1 digitaldaemon.com...

 Comments?


I really, really like this idea.  Granted, I don't do too much with operator 
overloading, but this seems like a very solid improvement to it.
Mar 27 2006
prev sibling next sibling parent "Craig Black" <cblack ara.com> writes:
Beautiful! An elegant solution to a long standing and annoying problem.

-Craig
Mar 27 2006
prev sibling next sibling parent Dave <Dave_member pathlink.com> writes:
Hear, hear! And my opinions are (I) yes, (II) yes and (III) no. And I'd like to
suggest that this optimization would be applied to built-in's like strX = strX ~
strY; => strX ~= strY;

The problem this addresses has driven me nuts in the C++ world as I've
maintained/optimized code. (i.e.: operator += is defined but not used where it
could be).

- Dave

In article <e087or$dgm$1 digitaldaemon.com>, Don Clugston says...

Background: Operator overloading, in the form it exists in C++ and 
currently in D, inherently results in sub-optimal code, because it 
always results in unnecessary temporary objects being created.

For example,
X = A - ((B*C) + D)* E;

becomes:
T1 = B * C;
T2 = T1 + D;
T3 = T2 * E;
T4 = A - T3;
X = T4;
Four objects were created, whereas only one was strictly required.
In C++, there are libraries like Blitz++ which use complicated 
expression templates in order to avoid these creating these temporaries, 
and provide performance comparable with FORTRAN. I think D can do much 
better...
Note that temporaries are avoided when using the opXXXAssign() operators 
like +=.

===========
   Proposal
===========
(1) Allow the compiler to assume that b = b + c  can be replaced with b 
+= c. (In C++, operator + and operator += are just symbols, the compiler 
doesn't know that there is any relationship between them).
In the example above, this would allow the compiler to generate:
T1 = B * C;
T1 += D;
T1 *= E;

and we have eliminated two of the three temporaries.
(2). Fill in the gaps in the operator overloading table by introducing
opAddAssign_r, opSubAssign_r, etc.

Just as A.opSubAssign(B)
is the operation  A -= B  or equivalently  A = A - B, similarly

A.opSubAssign_r(B)
would mean
A = B - A.
and would only occur when temporaries are generated in expressions. Like 
-=, it's an operation which can frequently be performed very 
efficiently, but at present the language has no way of expressing it.

Our original example then becomes:

T1 = B.opMul(C);
T1.opAddAssign(D);
T1.opMulAssign(E);
T1.opSubAssign_r(A);
X = T1;
... and all the useless temporaries are gone!

More formally, when the expression tree for an expression is generated:
With a binary operator XXX, operating on left & right nodes:

if (the left node is *not* an original leaf node) {
    // the left node is a temporary, does not need to be preserved.
    // we don't care if the right node is a temporary or not
    look for opXXXAssign().
} else if (the the right node is not an original leaf node) {
    // the right node is a temporary
    look for opXXXAssign_r()
} else {
   // both left and right nodes are leaf nodes, we have to
   // create a temporary
    look for opXXX(), just as it does now.
}

These rules also cope with the situation where temporaries are required:
eg
X = (A*B) + (C*D);
becomes
T1 = A*B;
T2 = C*D;
T1 += T2;
X = T1;

If this were implemented, it would permanently eradicate (for D) the 
most significant advantage which Fortran has managed to retain over 
object-oriented languages. And I really don't think it would be 
difficult to implement, or have negative side-effects.

There are a couple of decisions to be made:
(I) should the compiler use opAdd() and generate a temporary, if 
opAddAssign_r() doesn't exist, to preserve existing behaviour? I think 
the answer to this is YES.
(II) should the compiler use opAdd() and generate a temporary, if 
oppAddAssign() doesn't exist, to preserve existing behaviour? Again, I'm 
inclined to answer YES.
(III) If the code includes +=, and there is an opAdd() but no 
opAddAssign(), should the compiler accept this, and just generate an 
opAdd() followed by an assignment?? This would mean that opAdd() would 
generate the += operation as well as +, while opAddAssign() would be a 
performance enhancement. (It would still be possible to have 
opAddAssign() without opAdd(), to have += but not +, but it would not be 
possible to have + without +=). This would mean that += would be 
*purely* syntactic sugar.

Decision III would be a little more difficult to implement and is of 
less obvious merit, I only mention it as a possibility.

Comments?
Mar 27 2006
prev sibling next sibling parent reply Charles <noone nowhere.com> writes:
Wow looks good ... too good.  How could this have gone 
un[noticed|implemented] in the  last 20 years ?  I'm anxious to here 
Walters take.

1. yes, 2. yes, 3. over my head :).

Charlie



Don Clugston wrote:

 Background: Operator overloading, in the form it exists in C++ and 
 currently in D, inherently results in sub-optimal code, because it 
 always results in unnecessary temporary objects being created.
 
 For example,
 X = A - ((B*C) + D)* E;
 
 becomes:
 T1 = B * C;
 T2 = T1 + D;
 T3 = T2 * E;
 T4 = A - T3;
 X = T4;
 Four objects were created, whereas only one was strictly required.
 In C++, there are libraries like Blitz++ which use complicated 
 expression templates in order to avoid these creating these temporaries, 
 and provide performance comparable with FORTRAN. I think D can do much 
 better...
 Note that temporaries are avoided when using the opXXXAssign() operators 
 like +=.
 
 ===========
   Proposal
 ===========
 (1) Allow the compiler to assume that b = b + c  can be replaced with b 
 += c. (In C++, operator + and operator += are just symbols, the compiler 
 doesn't know that there is any relationship between them).
 In the example above, this would allow the compiler to generate:
 T1 = B * C;
 T1 += D;
 T1 *= E;
 
 and we have eliminated two of the three temporaries.
 (2). Fill in the gaps in the operator overloading table by introducing
 opAddAssign_r, opSubAssign_r, etc.
 
 Just as A.opSubAssign(B)
 is the operation  A -= B  or equivalently  A = A - B, similarly
 
 A.opSubAssign_r(B)
 would mean
 A = B - A.
 and would only occur when temporaries are generated in expressions. Like 
 -=, it's an operation which can frequently be performed very 
 efficiently, but at present the language has no way of expressing it.
 
 Our original example then becomes:
 
 T1 = B.opMul(C);
 T1.opAddAssign(D);
 T1.opMulAssign(E);
 T1.opSubAssign_r(A);
 X = T1;
 ... and all the useless temporaries are gone!
 
 More formally, when the expression tree for an expression is generated:
 With a binary operator XXX, operating on left & right nodes:
 
 if (the left node is *not* an original leaf node) {
    // the left node is a temporary, does not need to be preserved.
    // we don't care if the right node is a temporary or not
    look for opXXXAssign().
 } else if (the the right node is not an original leaf node) {
    // the right node is a temporary
    look for opXXXAssign_r()
 } else {
   // both left and right nodes are leaf nodes, we have to
   // create a temporary
    look for opXXX(), just as it does now.
 }
 
 These rules also cope with the situation where temporaries are required:
 eg
 X = (A*B) + (C*D);
 becomes
 T1 = A*B;
 T2 = C*D;
 T1 += T2;
 X = T1;
 
 If this were implemented, it would permanently eradicate (for D) the 
 most significant advantage which Fortran has managed to retain over 
 object-oriented languages. And I really don't think it would be 
 difficult to implement, or have negative side-effects.
 
 There are a couple of decisions to be made:
 (I) should the compiler use opAdd() and generate a temporary, if 
 opAddAssign_r() doesn't exist, to preserve existing behaviour? I think 
 the answer to this is YES.
 (II) should the compiler use opAdd() and generate a temporary, if 
 oppAddAssign() doesn't exist, to preserve existing behaviour? Again, I'm 
 inclined to answer YES.
 (III) If the code includes +=, and there is an opAdd() but no 
 opAddAssign(), should the compiler accept this, and just generate an 
 opAdd() followed by an assignment?? This would mean that opAdd() would 
 generate the += operation as well as +, while opAddAssign() would be a 
 performance enhancement. (It would still be possible to have 
 opAddAssign() without opAdd(), to have += but not +, but it would not be 
 possible to have + without +=). This would mean that += would be 
 *purely* syntactic sugar.
 
 Decision III would be a little more difficult to implement and is of 
 less obvious merit, I only mention it as a possibility.
 
 Comments?
Mar 27 2006
parent reply Sean Kelly <sean f4.ca> writes:
Charles wrote:

 Wow looks good ... too good.  How could this have gone 
 un[noticed|implemented] in the  last 20 years ?  I'm anxious to here 
 Walters take.


I have a feeling this may be a lot more difficult in C++ because of 
ADL--there are simply a lot more functions to be evaluated when building 
expression trees.  Also, the standard doesn't seem to consider things 
from a compiler writer's perspective, which this three-value code 
optimization requires.


Sean
Mar 27 2006
parent reply kris <foo bar.com> writes:
Sean Kelly wrote:

 Charles wrote:
 

 Wow looks good ... too good.  How could this have gone 
 un[noticed|implemented] in the  last 20 years ?  I'm anxious to here 
 Walters take.


 
 
 I have a feeling this may be a lot more difficult in C++ because of 
 ADL--there are simply a lot more functions to be evaluated when building 
 expression trees.  Also, the standard doesn't seem to consider things 
 from a compiler writer's perspective, which this three-value code 
 optimization requires.
 
 
 Sean


ADL? Does that stand for Attention Deficit Level?
Mar 27 2006
next sibling parent pragma <pragma_member pathlink.com> writes:
In article <e09v1r$2tb0$1 digitaldaemon.com>, kris says...

Sean Kelly wrote:

 Charles wrote:
 

 Wow looks good ... too good.  How could this have gone 
 un[noticed|implemented] in the  last 20 years ?  I'm anxious to here 
 Walters take.


 
 
 I have a feeling this may be a lot more difficult in C++ because of 
 ADL--there are simply a lot more functions to be evaluated when building 
 expression trees.  Also, the standard doesn't seem to consider things 
 from a compiler writer's perspective, which this three-value code 
 optimization requires.
 
 
 Sean


ADL? Does that stand for Attention Deficit Level?


Sorry, I missed this entire thread.  What's this about now? 

<g>

- EricAnderton at yahoo
Mar 27 2006
prev sibling parent reply Sean Kelly <sean f4.ca> writes:
kris wrote:

 Sean Kelly wrote:

 Charles wrote:


 Wow looks good ... too good.  How could this have gone 
 un[noticed|implemented] in the  last 20 years ?  I'm anxious to here 
 Walters take.



 I have a feeling this may be a lot more difficult in C++ because of 
 ADL--there are simply a lot more functions to be evaluated when 
 building expression trees.  Also, the standard doesn't seem to 
 consider things from a compiler writer's perspective, which this 
 three-value code optimization requires.


 
 ADL? Does that stand for Attention Deficit Level?


Argument Dependent Lookup.  ie. the complex overload resolution 
semantics in C++.  Another potential issue is the lack of "_r" functions 
in C++, since while free functions can do quite a bit they must either 
use temporaries, be friend functions with very odd semantics, or do 
something akin to expression templates.


Sean
Mar 27 2006
parent Charles <noone nowhere.com> writes:
 Argument Dependent Lookup.  ie. the complex overload resolution
 semantics in C++.  Another potential issue is the lack of "_r" functions
 in C++, since while free functions can do quite a bit they must either
 use temporaries, be friend functions with very odd semantics, or do
 something akin to expression templates.


Ahh , I see.  Well I think this will be huge for D, great idea Don!


Sean Kelly wrote:

 kris wrote:
 

 Sean Kelly wrote:


 Charles wrote:


 Wow looks good ... too good.  How could this have gone 
 un[noticed|implemented] in the  last 20 years ?  I'm anxious to here 
 Walters take.




 I have a feeling this may be a lot more difficult in C++ because of 
 ADL--there are simply a lot more functions to be evaluated when 
 building expression trees.  Also, the standard doesn't seem to 
 consider things from a compiler writer's perspective, which this 
 three-value code optimization requires.



 ADL? Does that stand for Attention Deficit Level?


 
 
 Argument Dependent Lookup.  ie. the complex overload resolution 
 semantics in C++.  Another potential issue is the lack of "_r" functions 
 in C++, since while free functions can do quite a bit they must either 
 use temporaries, be friend functions with very odd semantics, or do 
 something akin to expression templates.
 
 
 Sean
Mar 27 2006
prev sibling next sibling parent "Walter Bright" <newshound digitalmars.com> writes:
I think it's a great idea.
Mar 27 2006
prev sibling next sibling parent "Regan Heath" <regan netwin.co.nz> writes:
On Mon, 27 Mar 2006 10:29:13 +0200, Don Clugston <dac nospam.com.au> wrote:

 Comments?


I was wondering the exact same thing recently:
http://www.digitalmars.com/drn-bin/wwwnews?digitalmars.D/35382

Do you think we gain anything by using the lhs variable where possible.  
i.e.

Instead of:

T1 = B.opMul(C);
T1.opAddAssign(D);
T1.opMulAssign(E);
T1.opSubAssign_r(A);
X = T1;

We have:

X = B;
X.opMulAssign(C);
X.opAddAssign(D);
X.opMulAssign(E);
X.opSubAssign_r(A);

It seems to me that this results in 1 less temporary and therefore 1 less  
assignment.

Of course, it doesn't help/work in cases where there is no existing lhs,  
i.e.

   foo(A - ((B*C) + D)* E);

Regan
Mar 27 2006
prev sibling next sibling parent Sean Kelly <sean f4.ca> writes:
Don Clugston wrote:

 Background: Operator overloading, in the form it exists in C++ and 
 currently in D, inherently results in sub-optimal code, because it 
 always results in unnecessary temporary objects being created.


...

 If this were implemented, it would permanently eradicate (for D) the 
 most significant advantage which Fortran has managed to retain over 
 object-oriented languages. And I really don't think it would be 
 difficult to implement, or have negative side-effects.


Very nice.  And much better than expression templates.  I'm all for it.


 There are a couple of decisions to be made:
 (I) should the compiler use opAdd() and generate a temporary, if 
 opAddAssign_r() doesn't exist, to preserve existing behaviour? I think 
 the answer to this is YES.


Yes.


 (II) should the compiler use opAdd() and generate a temporary, if 
 oppAddAssign() doesn't exist, to preserve existing behaviour? Again, I'm 
 inclined to answer YES.


Yes.


 (III) If the code includes +=, and there is an opAdd() but no 
 opAddAssign(), should the compiler accept this, and just generate an 
 opAdd() followed by an assignment?? This would mean that opAdd() would 
 generate the += operation as well as +, while opAddAssign() would be a 
 performance enhancement. (It would still be possible to have 
 opAddAssign() without opAdd(), to have += but not +, but it would not be 
 possible to have + without +=). This would mean that += would be 
 *purely* syntactic sugar.
 
 Decision III would be a little more difficult to implement and is of 
 less obvious merit, I only mention it as a possibility.


I'd say no to this initially, and see how things sort out.  It may be 
that this turns out to be desirable and it may not.  But theoretically, 
I'd prefer to know when an OpAssign fn is required that I haven't 
provided than to have the compiler silently accept the syntax anyway.


Sean
Mar 27 2006
prev sibling next sibling parent reply James Dunne <james.jdunne gmail.com> writes:
Don Clugston wrote:

 Background: Operator overloading, in the form it exists in C++ and 
 currently in D, inherently results in sub-optimal code, because it 
 always results in unnecessary temporary objects being created.
 
 For example,
 X = A - ((B*C) + D)* E;
 
 becomes:
 T1 = B * C;
 T2 = T1 + D;
 T3 = T2 * E;
 T4 = A - T3;
 X = T4;
 Four objects were created, whereas only one was strictly required.
 In C++, there are libraries like Blitz++ which use complicated 
 expression templates in order to avoid these creating these temporaries, 
 and provide performance comparable with FORTRAN. I think D can do much 
 better...
 Note that temporaries are avoided when using the opXXXAssign() operators 
 like +=.
 
 ===========
   Proposal
 ===========
 (1) Allow the compiler to assume that b = b + c  can be replaced with b 
 += c. (In C++, operator + and operator += are just symbols, the compiler 
 doesn't know that there is any relationship between them).
 In the example above, this would allow the compiler to generate:
 T1 = B * C;
 T1 += D;
 T1 *= E;
 
 and we have eliminated two of the three temporaries.
 (2). Fill in the gaps in the operator overloading table by introducing
 opAddAssign_r, opSubAssign_r, etc.
 
 Just as A.opSubAssign(B)
 is the operation  A -= B  or equivalently  A = A - B, similarly
 
 A.opSubAssign_r(B)
 would mean
 A = B - A.
 and would only occur when temporaries are generated in expressions. Like 
 -=, it's an operation which can frequently be performed very 
 efficiently, but at present the language has no way of expressing it.
 
 Our original example then becomes:
 
 T1 = B.opMul(C);
 T1.opAddAssign(D);
 T1.opMulAssign(E);
 T1.opSubAssign_r(A);
 X = T1;
 .... and all the useless temporaries are gone!
 
 More formally, when the expression tree for an expression is generated:
 With a binary operator XXX, operating on left & right nodes:
 
 if (the left node is *not* an original leaf node) {
    // the left node is a temporary, does not need to be preserved.
    // we don't care if the right node is a temporary or not
    look for opXXXAssign().
 } else if (the the right node is not an original leaf node) {
    // the right node is a temporary
    look for opXXXAssign_r()
 } else {
   // both left and right nodes are leaf nodes, we have to
   // create a temporary
    look for opXXX(), just as it does now.
 }
 
 These rules also cope with the situation where temporaries are required:
 eg
 X = (A*B) + (C*D);
 becomes
 T1 = A*B;
 T2 = C*D;
 T1 += T2;
 X = T1;
 
 If this were implemented, it would permanently eradicate (for D) the 
 most significant advantage which Fortran has managed to retain over 
 object-oriented languages. And I really don't think it would be 
 difficult to implement, or have negative side-effects.
 
 There are a couple of decisions to be made:
 (I) should the compiler use opAdd() and generate a temporary, if 
 opAddAssign_r() doesn't exist, to preserve existing behaviour? I think 
 the answer to this is YES.
 (II) should the compiler use opAdd() and generate a temporary, if 
 oppAddAssign() doesn't exist, to preserve existing behaviour? Again, I'm 
 inclined to answer YES.
 (III) If the code includes +=, and there is an opAdd() but no 
 opAddAssign(), should the compiler accept this, and just generate an 
 opAdd() followed by an assignment?? This would mean that opAdd() would 
 generate the += operation as well as +, while opAddAssign() would be a 
 performance enhancement. (It would still be possible to have 
 opAddAssign() without opAdd(), to have += but not +, but it would not be 
 possible to have + without +=). This would mean that += would be 
 *purely* syntactic sugar.
 
 Decision III would be a little more difficult to implement and is of 
 less obvious merit, I only mention it as a possibility.
 
 Comments?


I guess I'll be the "Negative Nancy" here for purposes of strengthening 
your proposal...

While being well laid out and well thought through, this proposal still 
screams to me that it's concentrating on the mathematical problem 
domain.  This is fine for assuming that classes implementing operators 
will be mimicing real-world mathematical entities, such as vectors, 
matricies, etc.  But will this affect other problem domains adversely?

I usually like to come from the "everything explicit" angle and don't 
want the compiler making decisions on my behalf; especially when I'm not 
aware of them.  My suggestion would be to add a keyword in the operator 
definition (or class definition) to indicate that you want this sort of 
operator overloading behavior, such that one could leave it off if the 
default behavior is desired for other such cases.

In what specific problem domain are you experiencing issues with the 
current operator overloading syntax/semantics?  Or is it just that you 
feel that the current syntax/semantics are not quite fully developed?

And last but not least, another problem is in the order of evaluation 
for the operator overload calls.  What do you propose for this?  I think 
in order for this _not_ to matter, you'd have to guarantee that the 
classes themselves are self-contained and would have no references to 
(or have any effect on) the other classes involved in the expression 
statement.

This brings me to another related issue: these temporaries are going to 
be allocated on the GC heap no matter what, correct?  What if a silent 
out-of-memory exception was thrown from a line of code appearing to have 
no effect on memory allocation whatsoever?

There's basically no control over the number of temporaries that could 
be generated.  Also, there'd be "no going back" from a GC to a manual 
allocation strategy (i.e. memory pools) because you've effectively lost 
handles to those blocks of memory for the temporaries.  One could use 
custom allocators on the class for this purpose, but that would have an 
adverse effect on normal usage of the class.  These findings lead me to 
believe that classes which overload operators should have the 
requirement of being 'auto' (as in RAII or RR).

-- 
Regards,
James Dunne
Mar 27 2006
parent reply Don Clugston <dac nospam.com.au> writes:
James Dunne wrote:

 
 While being well laid out and well thought through, this proposal still 
 screams to me that it's concentrating on the mathematical problem 
 domain.  This is fine for assuming that classes implementing operators 
 will be mimicing real-world mathematical entities, such as vectors, 
 matricies, etc.  But will this affect other problem domains adversely?


I don't know - but I don't think so. My feeling is that if it strays too 
far from a mathematical domain, it probably shouldn't be using 
overloading of the arithmetical operators. In particular, I think that 
it's very hard to justify a+=b being different to a=a+b.


 I usually like to come from the "everything explicit" angle and don't 
 want the compiler making decisions on my behalf; especially when I'm not 
 aware of them. 


I'll take this as another vote against (III).

My suggestion would be to add a keyword in the operator

 definition (or class definition) to indicate that you want this sort of 
 operator overloading behavior, such that one could leave it off if the 
 default behavior is desired for other such cases.




 In what specific problem domain are you experiencing issues with the 
 current operator overloading syntax/semantics?  Or is it just that you 
 feel that the current syntax/semantics are not quite fully developed?


I was specifically interested in linear algebra. In thinking about 
Norbet's matrix proposal, I was thinking that it doesn't make sense to 
work on the syntax when there's an inherent inefficiency underneath.
Ultimately, operator overloading is just syntactic sugar for function 
calls. The problem with the C++ approach is that it only provides 
function calls for two of the three situations. Consequently, you suffer 
an unnecessary performance hit every time you use operator +.



 And last but not least, another problem is in the order of evaluation 
 for the operator overload calls.  What do you propose for this?  I think 
 in order for this _not_ to matter, you'd have to guarantee that the 
 classes themselves are self-contained and would have no references to 
 (or have any effect on) the other classes involved in the expression 
 statement.


True, but I think this already applies to operator +.


 This brings me to another related issue: these temporaries are going to 
 be allocated on the GC heap no matter what, correct?  What if a silent 
 out-of-memory exception was thrown from a line of code appearing to have 
 no effect on memory allocation whatsoever?


Again, this already applies to opAdd. The only thing this proposal 
changes is that avoidable temporaries are not created. Unavoidable 
temporaries are unchanged.
You raise a good point, though -- unavoidable temporaries could be 
treated better (eg with memory pools), this proposal does not let you 
distinguish between "new temporary = a+b " and "new result = a+b", the 
former could be stored in a memory pool. I think that's a minor issue, 
though.


 There's basically no control over the number of temporaries that could 
 be generated.  Also, there'd be "no going back" from a GC to a manual 
 allocation strategy (i.e. memory pools) because you've effectively lost 
 handles to those blocks of memory for the temporaries.  One could use 
 custom allocators on the class for this purpose, but that would have an 
 adverse effect on normal usage of the class.  These findings lead me to 
 believe that classes which overload operators should have the 
 requirement of being 'auto' (as in RAII or RR).
Mar 27 2006
parent Sean Kelly <sean f4.ca> writes:
Don Clugston wrote:

 You raise a good point, though -- unavoidable temporaries could be 
 treated better (eg with memory pools), this proposal does not let you 
 distinguish between "new temporary = a+b " and "new result = a+b", the 
 former could be stored in a memory pool. I think that's a minor issue, 
 though.


I think that's something that could be added as a Quality of 
Implementation issue without violating the rules you've outlined.  ie. 
it doesn't matter where the memory comes from.  Temporaries could even 
be allocated using alloca in some cases.

As for other issues with the behavior--so long as this is spelled out in 
the spec then I don't see any problems with it.  As you've said, it's 
what's actually happening behind the scenes anyway, but defining it this 
way makes for the most efficient code generation possible, and this is a 
fantastic guarantee to have in the case of large objects.


Sean
Mar 28 2006
prev sibling next sibling parent reply Norbert Nemec <Norbert Nemec-online.de> writes:
I don't see any obvious reasons against this proposal, but one should
not overestimate it!

It is true that it allows a number of optimizations and helps avoiding
some unnecessary temporaries, but it is not a replacement for expression
templates or vectorized expressions (aka array expressions).

Imagine A,B,C,D and X being arrays of the same size and consider the
last example in the proposal:


 X = (A*B) + (C*D);
 becomes
 T1 = A*B;
 T2 = C*D;
 T1 += T2;
 X = T1;


Fortran90 could translate the original expression into something like
	for(int i=0;i<N;i++)
		X[i] = (A[i]*B[i]) + (C[i]*D[i]);
which not only eliminates *all* temporaries, but does something more:
handle all calculations in one loop, allowing the memory to be read
cache friendly and all the calculations being done in registers.

C++ expression templates as used in blitz++ et al allow the same kind of
optimizations. Array expressions in D could do the same thing. The
operator optimization cannot handle this optimization.

So, as it stands I have no objections against the proposal, but it
should *NOT* be used as excuse against expression templates or array
expressions in the long term.

Greetings,
Norbert
Mar 28 2006
parent reply Don Clugston <dac nospam.com.au> writes:
Norbert Nemec wrote:

 I don't see any obvious reasons against this proposal, but one should
 not overestimate it!
 
 It is true that it allows a number of optimizations and helps avoiding
 some unnecessary temporaries, but it is not a replacement for expression
 templates or vectorized expressions (aka array expressions).
 
 Imagine A,B,C,D and X being arrays of the same size and consider the
 last example in the proposal:
 

 X = (A*B) + (C*D);
 becomes
 T1 = A*B;
 T2 = C*D;
 T1 += T2;
 X = T1;


 
 Fortran90 could translate the original expression into something like
 	for(int i=0;i<N;i++)
 		X[i] = (A[i]*B[i]) + (C[i]*D[i]);
 which not only eliminates *all* temporaries, but does something more:
 handle all calculations in one loop, allowing the memory to be read
 cache friendly and all the calculations being done in registers.


Obviously not with real matrices (C*D is not a pointwise operation), but 
  point taken. (BTW, the temporaries are still there, they're just in 
registers this time (A[i]*B[i], C[i]*D[i]). The proposal does get rid of 
all unnecessary temporaries, the problem is that there's no vectorisation).


 C++ expression templates as used in blitz++ et al allow the same kind of
 optimizations. Array expressions in D could do the same thing. The
 operator optimization cannot handle this optimization.
 
 So, as it stands I have no objections against the proposal, but it
 should *NOT* be used as excuse against expression templates or array
 expressions in the long term.


I completely agree. I see this as fixing the general case, but it does 
nothing for vectorisation. I suspect that array expressions are somewhat 
special as regards expressions, because of the vectorisation 
possibility. If we had array expressions, this might eliminate the 
necessity for expression templates. Do you think that's right?

Thanks for putting this into perspective.


 Greetings,
 Norbert
Mar 28 2006
parent reply Norbert Nemec <Norbert Nemec-online.de> writes:
Don Clugston wrote:

 Obviously not with real matrices (C*D is not a pointwise operation), but
  point taken. (BTW, the temporaries are still there, they're just in
 registers this time (A[i]*B[i], C[i]*D[i]). The proposal does get rid of
 all unnecessary temporaries, the problem is that there's no vectorisation).


Point accepted. For matrices, the issues are much more complicated, but
still there is quite a bit of optimization possible when vectorization
is taken into accound. p.e. the expression A*B+C can be done very
efficiently when done in one shot. (There even are BLAS routines for
this kind of combined operations, which are very common in many fields
of application.)


 I completely agree. I see this as fixing the general case, but it does
 nothing for vectorisation. I suspect that array expressions are somewhat
 special as regards expressions, because of the vectorisation
 possibility. If we had array expressions, this might eliminate the
 necessity for expression templates. Do you think that's right?


Those have their right of existance and should be supported by the
language: array expressions are more comfortable to use and to optimize
than a corresponding ET-library, but expression templates can be used
for a much larger field of applications than just vectorized
expressions. Just consider the linear algebra example above, where an
expression template library might automatically optimize A*B+C into a
single BLAS function call.
Mar 28 2006
next sibling parent reply James Dunne <james.jdunne gmail.com> writes:
Norbert Nemec wrote:

 Don Clugston wrote:
 

Obviously not with real matrices (C*D is not a pointwise operation), but
 point taken. (BTW, the temporaries are still there, they're just in
registers this time (A[i]*B[i], C[i]*D[i]). The proposal does get rid of
all unnecessary temporaries, the problem is that there's no vectorisation).


 
 
 Point accepted. For matrices, the issues are much more complicated, but
 still there is quite a bit of optimization possible when vectorization
 is taken into accound. p.e. the expression A*B+C can be done very
 efficiently when done in one shot. (There even are BLAS routines for
 this kind of combined operations, which are very common in many fields
 of application.)
 
 

I completely agree. I see this as fixing the general case, but it does
nothing for vectorisation. I suspect that array expressions are somewhat
special as regards expressions, because of the vectorisation
possibility. If we had array expressions, this might eliminate the
necessity for expression templates. Do you think that's right?


 
 
 Those have their right of existance and should be supported by the
 language: array expressions are more comfortable to use and to optimize
 than a corresponding ET-library, but expression templates can be used
 for a much larger field of applications than just vectorized
 expressions. Just consider the linear algebra example above, where an
 expression template library might automatically optimize A*B+C into a
 single BLAS function call.


If possible, can someone lay out a clear definition of both "array 
expressions" and "expression templates"?  I'd really like to fully 
understand what's possible in this area for my own research.

Thanks,

-- 
-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GCS/MU/S d-pu s:+ a-->? C++++$ UL+++ P--- L+++ !E W-- N++ o? K? w--- O 
M--  V? PS PE Y+ PGP- t+ 5 X+ !R tv-->!tv b- DI++(+) D++ G e++>e 
h>--->++ r+++ y+++
------END GEEK CODE BLOCK------

James Dunne
Mar 28 2006
parent reply xs0 <xs0 xs0.com> writes:
James Dunne wrote:

 If possible, can someone lay out a clear definition of both "array 
 expressions" and "expression templates"?  I'd really like to fully 
 understand what's possible in this area for my own research.
 
 Thanks,
 


afaik, array expressions are just expressions which get evaluated 
element-wise over whole arrays:

a[] = b[] + c[]; // must be same length

is the same as

for (int i=0; i<a.length; i++)
     a[i] = b[i] + c[i];

The advantage of having them instead of doing for loops (in addition to 
aesthetics) is that the compiler can optimize the code much better (for 
example, by doing vectorization == AltiVec/MMX/SSE), because it clearly 
knows what you're doing - with a for loop, it's just a bunch of 
single-element operations.


Expression templates, otoh, are a somewhat complex template technique, 
which allows efficient evaluation of expressions over arbitrary types. 
Instead of evaluating the expression one operation at a time:

a = b + c * d

usually becomes

_t1 = c.opMul(d);
_t2 = b.opAdd(_t1);
a = _t2

the expressions first evaluate to template instances, which can then be 
inlined and optimized by the compiler. That obviously results in faster 
execution. The above example would become something like:

auto expr=Sum!(b, Product!(c, d));
a.length=expr.length;
for (int i=0; i<a.length; i++)
     a[i]=expr.evaluate(i); // hopefully inlines to b[i]+c[i]*d[i]

http://osl.iu.edu/~tveldhui/papers/Expression-Templates/exprtmpl.html

One problem in doing them in D is that you can't overload the = 
operator, so the best one can hope for is

(b+c*d).assignTo(a);
// or
a = (b+c*d).eval();

Another problem is that expression templates rely heavily on implicit 
instantiation, which is currently quite basic in D (but getting better).


Hope that helped :)


xs0
Mar 28 2006
parent James Dunne <james.jdunne gmail.com> writes:
xs0 wrote:

 James Dunne wrote:
 

 If possible, can someone lay out a clear definition of both "array 
 expressions" and "expression templates"?  I'd really like to fully 
 understand what's possible in this area for my own research.

 Thanks,


 
 afaik, array expressions are just expressions which get evaluated 
 element-wise over whole arrays:
 
 a[] = b[] + c[]; // must be same length
 
 is the same as
 
 for (int i=0; i<a.length; i++)
     a[i] = b[i] + c[i];
 
 The advantage of having them instead of doing for loops (in addition to 
 aesthetics) is that the compiler can optimize the code much better (for 
 example, by doing vectorization == AltiVec/MMX/SSE), because it clearly 
 knows what you're doing - with a for loop, it's just a bunch of 
 single-element operations.
 
 
 Expression templates, otoh, are a somewhat complex template technique, 
 which allows efficient evaluation of expressions over arbitrary types. 
 Instead of evaluating the expression one operation at a time:
 
 a = b + c * d
 
 usually becomes
 
 _t1 = c.opMul(d);
 _t2 = b.opAdd(_t1);
 a = _t2
 
 the expressions first evaluate to template instances, which can then be 
 inlined and optimized by the compiler. That obviously results in faster 
 execution. The above example would become something like:
 
 auto expr=Sum!(b, Product!(c, d));
 a.length=expr.length;
 for (int i=0; i<a.length; i++)
     a[i]=expr.evaluate(i); // hopefully inlines to b[i]+c[i]*d[i]
 
 http://osl.iu.edu/~tveldhui/papers/Expression-Templates/exprtmpl.html
 
 One problem in doing them in D is that you can't overload the = 
 operator, so the best one can hope for is
 
 (b+c*d).assignTo(a);
 // or
 a = (b+c*d).eval();
 
 Another problem is that expression templates rely heavily on implicit 
 instantiation, which is currently quite basic in D (but getting better).
 
 
 Hope that helped :)
 
 
 xs0


Yes, thank you very much!

-- 
-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GCS/MU/S d-pu s:+ a-->? C++++$ UL+++ P--- L+++ !E W-- N++ o? K? w--- O 
M--  V? PS PE Y+ PGP- t+ 5 X+ !R tv-->!tv b- DI++(+) D++ G e++>e 
h>--->++ r+++ y+++
------END GEEK CODE BLOCK------

James Dunne
Mar 28 2006
prev sibling parent reply Sean Kelly <sean f4.ca> writes:
Norbert Nemec wrote:

 Don Clugston wrote:

 Obviously not with real matrices (C*D is not a pointwise operation), but
  point taken. (BTW, the temporaries are still there, they're just in
 registers this time (A[i]*B[i], C[i]*D[i]). The proposal does get rid of
 all unnecessary temporaries, the problem is that there's no vectorisation).


 
 Point accepted. For matrices, the issues are much more complicated, but
 still there is quite a bit of optimization possible when vectorization
 is taken into accound. p.e. the expression A*B+C can be done very
 efficiently when done in one shot. (There even are BLAS routines for
 this kind of combined operations, which are very common in many fields
 of application.)


It almost seems like this could be handled via a special opIndex 
function: opIndexCalc or some such.  If the method exists for all 
involved types, then:

A = B + C

could be translated to:

for( size_t i = 0; i < A.length; ++i )
     A[i] = B[i] + C[i];

where the subscripting calls opIndexCalc instead of the standard 
opIndex.  But this leaves out array length checking, and simply throwing 
an IndexOutOfBounds exception if something goes wrong would leave A 
corrupted.  So perhaps some checking would also be required to see if 
opIndexCalc should be called?  The only catch is that this would likely 
need to occur at run-time:

if( A.matches( B ) && A.matches( C ) )
     for( size_t i = 0; i < A.length; ++i )
         A[i] = B[i] + C[i];
else
     A = B + C; // standard method using temporaries

I don't have enough experience to know what might work here, but it 
would be great if an alternative to expression templates could be devised.


Sean
Mar 28 2006
parent Norbert Nemec <Norbert Nemec-online.de> writes:
Sean Kelly wrote:

 I don't have enough experience to know what might work here, but it
 would be great if an alternative to expression templates could be devised.


I believe people should not be overly afraid of expression templates. In
C++ they are ugly because the whole template system is ugly. In
principle they are a tremendously powerful concept that should
definitely be supported in D as well as possible.

When I say that there should be support for array expressions that does
not rely on expression templates, that is only because I believe that
arrays are crucial enough for the language to justify this special
treatment.
Mar 28 2006
prev sibling next sibling parent Oskar Linde <oskar.lindeREM OVEgmail.com> writes:
I fully support this proposal. It makes sense to place stricter semantic 
requirements on overloaded operators. I can not see any problems. You 
seem to have everything covered. What restrictions should the compiler 
placed on the operator overloading signatures? Should it for instance be 
illegal to define an opAdd with a different return type than opAddAssign?

Don Clugston wrote:


 In C++, there are libraries like Blitz++ which use complicated 
 expression templates in order to avoid these creating these temporaries, 
 and provide performance comparable with FORTRAN. I think D can do much 
 better...


Expression templates would still be useful for other cases though. 
Consider: (A * B) % C.
Here, expression templates could allow evaluating a much more efficient 
modMul(A,B,C). Expression templates could also help writing less complex 
but still efficient code by allowing lazy evaluation.

/Oskar
Mar 28 2006
prev sibling parent reply Bruno Medeiros <daiphoenixNO SPAMlycos.com> writes:
Don Clugston wrote:

 Background: Operator overloading, in the form it exists in C++ and 
 currently in D, inherently results in sub-optimal code, because it 
 always results in unnecessary temporary objects being created.
 
 For example,
 X = A - ((B*C) + D)* E;
 
 becomes:
 T1 = B * C;
 T2 = T1 + D;
 T3 = T2 * E;
 T4 = A - T3;
 X = T4;
 Four objects were created, whereas only one was strictly required.


Ok, I'm new to this, so it took me a while to understand the problem. 
Let's see if I got it right: this is actually only a problem when the 
operator methods explicitly instantiate a *class object*, to be used as 
the return of the method, right?



-- 
Bruno Medeiros - CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Apr 02 2006
parent reply Don Clugston <dac nospam.com.au> writes:
Bruno Medeiros wrote:

 Don Clugston wrote:

 Background: Operator overloading, in the form it exists in C++ and 
 currently in D, inherently results in sub-optimal code, because it 
 always results in unnecessary temporary objects being created.

 For example,
 X = A - ((B*C) + D)* E;

 becomes:
 T1 = B * C;
 T2 = T1 + D;
 T3 = T2 * E;
 T4 = A - T3;
 X = T4;
 Four objects were created, whereas only one was strictly required.


 
 Ok, I'm new to this, so it took me a while to understand the problem. 
 Let's see if I got it right: this is actually only a problem when the 
 operator methods explicitly instantiate a *class object*, to be used as 
 the return of the method, right?


Not really, it applies everywhere that you can have overloaded 
operators. The cost of a temporary will be greater with classes, but for 
structs, eliminating temporaries will make it much easier for the 
compiler to optimise.
Apr 03 2006
parent reply Bruno Medeiros <brunodomedeirosATgmail SPAM.com> writes:
Don Clugston wrote:

 Bruno Medeiros wrote:

 Don Clugston wrote:

 Background: Operator overloading, in the form it exists in C++ and 
 currently in D, inherently results in sub-optimal code, because it 
 always results in unnecessary temporary objects being created.

 For example,
 X = A - ((B*C) + D)* E;

 becomes:
 T1 = B * C;
 T2 = T1 + D;
 T3 = T2 * E;
 T4 = A - T3;
 X = T4;
 Four objects were created, whereas only one was strictly required.


 Ok, I'm new to this, so it took me a while to understand the problem. 
 Let's see if I got it right: this is actually only a problem when the 
 operator methods explicitly instantiate a *class object*, to be used 
 as the return of the method, right?


 
 Not really, it applies everywhere that you can have overloaded 
 operators. The cost of a temporary will be greater with classes, but for 
 structs, eliminating temporaries will make it much easier for the 
 compiler to optimise.
 


But with structs (more generally, with stack-based value types), can't 
the compiler already optimize it? In your example, it seems to me that 
the compiler make the code so that it uses only two temporaries:

T1 = B * C;
T2 = T1 + D; // T1 is now free for use
T1 = T2 * E; // T2 is now free for use
T2 = A - T1; // T1 is now free for use
X = T2;

And, if inlining occurs, it can be made to use only one temporary, no?


-- 
Bruno Medeiros - CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Apr 04 2006
parent Don Clugston <dac nospam.com.au> writes:
Bruno Medeiros wrote:

 Don Clugston wrote:

 Bruno Medeiros wrote:

 Don Clugston wrote:

 Background: Operator overloading, in the form it exists in C++ and 
 currently in D, inherently results in sub-optimal code, because it 
 always results in unnecessary temporary objects being created.

 For example,
 X = A - ((B*C) + D)* E;

 becomes:
 T1 = B * C;
 T2 = T1 + D;
 T3 = T2 * E;
 T4 = A - T3;
 X = T4;
 Four objects were created, whereas only one was strictly required.


 Ok, I'm new to this, so it took me a while to understand the problem. 
 Let's see if I got it right: this is actually only a problem when the 
 operator methods explicitly instantiate a *class object*, to be used 
 as the return of the method, right?


 Not really, it applies everywhere that you can have overloaded 
 operators. The cost of a temporary will be greater with classes, but 
 for structs, eliminating temporaries will make it much easier for the 
 compiler to optimise.


 
 But with structs (more generally, with stack-based value types), can't 
 the compiler already optimize it? In your example, it seems to me that 
 the compiler make the code so that it uses only two temporaries:
 
 T1 = B * C;
 T2 = T1 + D; // T1 is now free for use
 T1 = T2 * E; // T2 is now free for use
 T2 = A - T1; // T1 is now free for use
 X = T2;


True, but for objects on the stack, the cost is really just in the 
copying of data, not the memory allocation. T1 and T2 still get 
initialised twice.


 And, if inlining occurs, it can be made to use only one temporary, no?


Indeed, the compiler might optimise it, if the structs are small enough. 
Which is why I said that it makes it "much easier for the compiler to 
optimise". It might be able to do it without this help, but my 
experience with C++ has been that inlining is unreliable.
Apr 05 2006