[proto] RValue reference support?
Does proto have any support for rvalue references in terminals? I'm thinking that if you know that you're assigning an expression involving an rvalue-reference as a terminal, then there are some optimizations that can be performed that aren't otherwise possible. Thanks, John.
On 11/08/2011 14:34, John Maddock wrote:
Does proto have any support for rvalue references in terminals?
No, unfortunately. I think Eric said that for C++0x, it would be nice to rewrite a lot of things to make them simpler and faster to compile. I think it would be a useful addition in the current Proto without re-writing all of it though. I suspect however that if you don't rely on the default operator overloads and call make_expr yourself, it might work.
I'm thinking that if you know that you're assigning an expression involving an rvalue-reference as a terminal, then there are some optimizations that can be performed that aren't otherwise possible.
Do you have an example of a DSL where that would be useful?
No, unfortunately. I think Eric said that for C++0x, it would be nice to rewrite a lot of things to make them simpler and faster to compile.
I think it would be a useful addition in the current Proto without re-writing all of it though.
I suspect however that if you don't rely on the default operator overloads and call make_expr yourself, it might work.
I'm thinking that if you know that you're assigning an expression involving an rvalue-reference as a terminal, then there are some optimizations that can be performed that aren't otherwise possible.
Do you have an example of a DSL where that would be useful?
Well actually.... now I come to think of it some more, I'm not sure it's as useful as I first thought: a nice "luxury feature" maybe, but not essential. The example is the archetypical "big number" class - the idea is to minimize the number of temporaries created while evaluating an expression - not just removing "return by value from operator" that expression templates provide by default, but to analyze the expression, figure out a [semi-]optimal evaluation order and reuse temporaries as far as is possible. But I'm figuring that the occurrence of temporaries on the RHS of an expression, while not out of the question, is rare enough not to be too concerned about. Thanks for the prompt response, John.
On 8/11/2011 8:19 AM, John Maddock wrote:
No, unfortunately. I think Eric said that for C++0x, it would be nice to rewrite a lot of things to make them simpler and faster to compile.
I think it would be a useful addition in the current Proto without re-writing all of it though.
I suspect however that if you don't rely on the default operator overloads and call make_expr yourself, it might work.
I'm thinking that if you know that you're assigning an expression involving an rvalue-reference as a terminal, then there are some optimizations that can be performed that aren't otherwise possible.
Do you have an example of a DSL where that would be useful?
Well actually.... now I come to think of it some more, I'm not sure it's as useful as I first thought: a nice "luxury feature" maybe, but not essential.
The example is the archetypical "big number" class - the idea is to minimize the number of temporaries created while evaluating an expression - not just removing "return by value from operator" that expression templates provide by default, but to analyze the expression, figure out a [semi-]optimal evaluation order and reuse temporaries as far as is possible.
But I'm figuring that the occurrence of temporaries on the RHS of an expression, while not out of the question, is rare enough not to be too concerned about.
You can use Proto to eliminate the need for temporaries without rvalue reference support. What you describe above is a textbook application of expression templates. If it will save you 1 dynamic allocation every now and then, it's probably worth considering. Can you explain again why rvalue references are important for you? I'm not following. -- Eric Niebler BoostPro Computing http://www.boostpro.com
But I'm figuring that the occurrence of temporaries on the RHS of an expression, while not out of the question, is rare enough not to be too concerned about.
You can use Proto to eliminate the need for temporaries without rvalue reference support. What you describe above is a textbook application of expression templates. If it will save you 1 dynamic allocation every now and then, it's probably worth considering.
Can you explain again why rvalue references are important for you? I'm not following.
OK, lets say we have an expression: a = x * y + w * z; The order of evaluation might be: *assign x to a. * multiply a by y * create one temporary as a copy of w * multiple temp by z * add temp to a So we need one temporary to evaluate the expression. Now imagine that one of the variables isn't a variable at all, but a temporary, lets say the result of a (non-protoized) function call: a = x * y + foo() * z Now we don't need to create a temporary for foo() * z since *we have one already*. So if one of the terminals is an rvalue reference, we know that we can reuse that value as a temporary and trash it's value with impunity - as long as we do so after it's value has been used of course :-) HTH, John.
On 8/11/2011 10:50 AM, John Maddock wrote:
But I'm figuring that the occurrence of temporaries on the RHS of an expression, while not out of the question, is rare enough not to be too concerned about.
You can use Proto to eliminate the need for temporaries without rvalue reference support. What you describe above is a textbook application of expression templates. If it will save you 1 dynamic allocation every now and then, it's probably worth considering.
Can you explain again why rvalue references are important for you? I'm not following.
OK, lets say we have an expression:
a = x * y + w * z;
The order of evaluation might be:
*assign x to a. * multiply a by y * create one temporary as a copy of w * multiple temp by z * add temp to a
This part I don't understand, and it's probably because I don't know the particulars of the bigint domain. But I know if these things were vectors, it would go something like this: * walk the expression x*y + w*z (at runtime) and calculate the size of the resulting vector * allocate space for the result vector * walk the expression x*y + w*z and evaluate it (also at runtime), filling in the result vector directly (no temporaries). * swap the result vector with a's I'm ignorant of how bigint arithmetic works, but I wonder if a similar scheme might work here.
So we need one temporary to evaluate the expression.
Now imagine that one of the variables isn't a variable at all, but a temporary, lets say the result of a (non-protoized) function call:
a = x * y + foo() * z
Now we don't need to create a temporary for foo() * z since *we have one already*. So if one of the terminals is an rvalue reference, we know that we can reuse that value as a temporary and trash it's value with impunity - as long as we do so after it's value has been used of course :-)
OK, this much I understand. Thanks. -- Eric Niebler BoostPro Computing http://www.boostpro.com
On Thu, Aug 11, 2011 at 3:11 PM, Eric Niebler <eric@boostpro.com> wrote:
On 8/11/2011 10:50 AM, John Maddock wrote:
[snip]
Now imagine that one of the variables isn't a variable at all, but a temporary, lets say the result of a (non-protoized) function call:
a = x * y + foo() * z
If proto supported rvalue references then a could reuse foo()'s temporary resources and maybe avoid dynamic allocation for a. [snip]
-- Eric Niebler BoostPro Computing http://www.boostpro.com
Regards, -- Felipe Magno de Almeida
On 8/11/2011 11:25 AM, Felipe Magno de Almeida wrote:
On 8/11/2011 10:50 AM, John Maddock wrote:
Now imagine that one of the variables isn't a variable at all, but a temporary, lets say the result of a (non-protoized) function call:
a = x * y + foo() * z
If proto supported rvalue references then a could reuse foo()'s temporary resources and maybe avoid dynamic allocation for a.
I'm not actually sure that's true in the general case. foo()'s temporary is holding a value that is used in the computation. You can't reuse the memory until you are done with the value, and in the general case, that's not until you are done evaluating the expression. Consider how it works for vectors. You want to evaluate the expression as: tmp1 = foo(); tmp2 = vector of right size for (int i in 0 to tmp2.size()-1) tmp2[i] = x[i]*y[i]+tmp1[i]*z[i]; swap(a, tmp2); You're not ready to throw out tmp1 until after the for loop, so you need tmp2. OK, in this isolated case, you actually /could/ use tmp1 as your scratch space: tmp1[i] = x[i]*y[i]+tmp1[i]*z[i]; But in the general case, you can't know that it's ok to stomp a value (tmp1) that's still in use like this. And for bigint, I'm guessing that's not the case. -- Eric Niebler BoostPro Computing http://www.boostpro.com
On 08/11/2011 08:55 PM, Eric Niebler wrote:
Consider how it works for vectors. You want to evaluate the expression as:
tmp1 = foo(); tmp2 = vector of right size for (int i in 0 to tmp2.size()-1) tmp2[i] = x[i]*y[i]+tmp1[i]*z[i]; swap(a, tmp2);
or tmp1 = foo() a.resize(the_right_size) for (int i in 0 to a.size()-1) a[i] = x[i]*y[i]+tmp1[i]*z[i]; This avoids an unnecessary allocation if a is already of the right size. It's not strongly exception-safe, though.
If proto supported rvalue references then a could reuse foo()'s temporary resources and maybe avoid dynamic allocation for a.
I'm not actually sure that's true in the general case. foo()'s temporary is holding a value that is used in the computation. You can't reuse the memory until you are done with the value, and in the general case, that's not until you are done evaluating the expression. Consider how it works for vectors. You want to evaluate the expression as:
tmp1 = foo(); tmp2 = vector of right size for (int i in 0 to tmp2.size()-1) tmp2[i] = x[i]*y[i]+tmp1[i]*z[i]; swap(a, tmp2);
You're not ready to throw out tmp1 until after the for loop, so you need tmp2.
OK, in this isolated case, you actually /could/ use tmp1 as your scratch space:
tmp1[i] = x[i]*y[i]+tmp1[i]*z[i];
But in the general case, you can't know that it's ok to stomp a value (tmp1) that's still in use like this. And for bigint, I'm guessing that's not the case.
For sure in the general case this may not be a viable optimization, so I would probably expect proto to ignore revalue refs in the default evaluation context. Likewise the kind of fused multiply-add that you show in the vector case isn't available to me either. Imagine that each arithmetic op is a black box atomic operation (usually an external C routine - the vector/matrix equivalent would be to shell out to BLAS for example), so the only control I have is: * the order of operation. *how the expression is decomposed into the available atomics. * how many temporaries are needed to service those atomics. Also in the real-number case, functions returning result-by-value are as common as gloomy bankers (!) so the example I gave is not all that unusual - though for sure there are better gains to be made by proto-icing the most common functions (the usual transcendentals etc). I'm also able to figure out exactly when a value is used and when it's no longer needed, so if I also knew that it was a temporary already I could reuse it. Hope this explains things better, John.
On Thu, Aug 11, 2011 at 11:11 AM, Eric Niebler <eric@boostpro.com> wrote:
On 8/11/2011 10:50 AM, John Maddock wrote:
But I'm figuring that the occurrence of temporaries on the RHS of an expression, while not out of the question, is rare enough not to be too concerned about.
You can use Proto to eliminate the need for temporaries without rvalue reference support. What you describe above is a textbook application of expression templates. If it will save you 1 dynamic allocation every now and then, it's probably worth considering.
Can you explain again why rvalue references are important for you? I'm not following.
OK, lets say we have an expression:
a = x * y + w * z;
The order of evaluation might be:
*assign x to a. * multiply a by y * create one temporary as a copy of w * multiple temp by z * add temp to a
This part I don't understand, and it's probably because I don't know the particulars of the bigint domain. But I know if these things were vectors, it would go something like this:
* walk the expression x*y + w*z (at runtime) and calculate the size of the resulting vector * allocate space for the result vector * walk the expression x*y + w*z and evaluate it (also at runtime), filling in the result vector directly (no temporaries). * swap the result vector with a's
I'm ignorant of how bigint arithmetic works, but I wonder if a similar scheme might work here.
Maybe, but generally I think this is only really efficient if each component of the output depends on a small (constant) number of the components of the input and a small (constant) number of operations. If there ends up being a lot of redundant calculations among the various components of the output, then computing the output fully lazily component-by-component is likely suboptimal. E.g., I would think * being a convolution operator would qualify. - Jeff
On 8/11/2011 7:07 AM, Mathias Gaunard wrote:
On 11/08/2011 14:34, John Maddock wrote:
Does proto have any support for rvalue references in terminals?
No, unfortunately. I think Eric said that for C++0x, it would be nice to rewrite a lot of things to make them simpler and faster to compile.
That would be great.
I think it would be a useful addition in the current Proto without re-writing all of it though.
I agree.
I suspect however that if you don't rely on the default operator overloads and call make_expr yourself, it might work.
I don't think so. The make_expr overloads are also unaware of move semantics.
I'm thinking that if you know that you're assigning an expression involving an rvalue-reference as a terminal, then there are some optimizations that can be performed that aren't otherwise possible.
Do you have an example of a DSL where that would be useful?
-- Eric Niebler BoostPro Computing http://www.boostpro.com
participants (5)
-
Eric Niebler -
Felipe Magno de Almeida -
Jeffrey Lee Hellrung, Jr. -
John Maddock -
Mathias Gaunard