Move Semantics

[Jesse Perla]

Hi there,
I am writing many routines where I would strongly prefer: matrix<double> f(const matrix<double>& in)   to void f(const matrix<double>& in, matrix<double>& out )
There has been a lot of discussion about this from the C++ groups:

• The move library to support this in C++03
  
• http://cpp-next.com/archive/2009/08/want-speed-pass-by-value/

Also, I see that this is native to MTL:  http://www.osl.iu.edu/research/mtl/mtl4/doc/matrix_assignment.html#move_semantics

I don't understand expression templates well enough to know the current state in ublas, but is it possible to return large matrices in this way?  For example, if I took the following code: http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?LU_Matrix_Inversion and had it return a matrix instead, would that give overhead for large matrices?
Could I even nest it with no overhead in other vector expressions:   e.g.
matrix<double> C, B; //setup.  Assume they are very large
matrix<double> A = inv(B) + C;

If this pattern is not usable yet, any idea of when it would be?

Thanks,
Jesse


_______________________________________________
ublas mailing list
ublas@...
http://lists.boost.org/mailman/listinfo.cgi/ublas
Sent to: lists@...

[Gunter Winkler]

Jesse Perla schrieb:

> Hi there,
> I am writing many routines where I would strongly prefer:
> matrix<double> f(const matrix<double>& in)   to void f(const
> matrix<double>& in, matrix<double>& out )
> There has been a lot of discussion about this from the C++ groups:
>
>     * The move library to support this in C++03
>     * http://cpp-next.com/archive/2009/08/want-speed-pass-by-value/
>
> Also, I see that this is native to MTL:
> http://www.osl.iu.edu/research/mtl/mtl4/doc/matrix_assignment.html#move_semantics
>

in ublas the move semantics is partially available:

A.assign_temporary( same type as A )

this is implemented by swapping the internal storage objects.

> I don't understand expression templates well enough to know the
> current state in ublas, but is it possible to return large matrices in
> this way?  For example, if I took the following code:
> http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?LU_Matrix_Inversion
> and had it return a matrix instead, would that give overhead for large
> matrices?
> Could I even nest it with no overhead in other vector expressions:   e.g.
> matrix<double> C, B; //setup.  Assume they are very large
> matrix<double> A = inv(B) + C;
>

if B in very large than it is already very expensive to compute inv(B).
In order to optimize this we had to modify the inv() method to return an
expression template instead of acutally computing the result. Then the
computation is deferred until the assignement to A is executed. However
this only helps if we can easily compute the rhs expression element by
element.

> If this pattern is not usable yet, any idea of when it would be?

for inversions of general matrices I see no option except the usual
"decompose" and "solve" strategy which must be coded explicitly.

Back to your original question:

in order to see how the expression templates work you should have a look
at vector_expression.hpp, e.g., class vector_binary. This class simply
holds the two operands and  the operation to carry out. Right below this
class you see the implementation of the free functions operator+(),
operator-(), element_prod() and element_div() for vectors. The whole
magic is hidden in the iterators who should provide an optimal traversal
through both vectors. The actual computation is done in the
dereference() function (which simply calls functor::apply(xi,yi).


mfg
Gunter
 

>
> Thanks,
> Jesse
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> ublas mailing list
> ublas@...
> http://lists.boost.org/mailman/listinfo.cgi/ublas
> Sent to: guwi17@...

_______________________________________________
ublas mailing list
ublas@...
http://lists.boost.org/mailman/listinfo.cgi/ublas
Sent to: lists@...

[Jesse Perla]

On Wed, Sep 2, 2009 at 2:29 PM, Gunter Winkler <guwi17@...> wrote:

> Also, I see that this is native to MTL:
> http://www.osl.iu.edu/research/mtl/mtl4/doc/matrix_assignment.html#move_semantics
>

in ublas the move semantics is partially available:

A.assign_temporary( same type as A )

this is implemented by swapping the internal storage objects.

Awesome.

 

if B in very large than it is already very expensive to compute inv(B).
In order to optimize this we had to modify the inv() method to return an
expression template instead of acutally computing the result. Then the
computation is deferred until the assignement to A is executed. However
this only helps if we can easily compute the rhs expression element by
element.

Yup.  And as you say, that isn't the case here (or in many places where we end up using the bindings...)

 

> If this pattern is not usable yet, any idea of when it would be?

for inversions of general matrices I see no option except the usual
"decompose" and "solve" strategy which must be coded explicitly.

True, but somehow the MTL4 guys have move semantics working so that you can return the matrix expression...  Might be worth checking out their solution.  http://www.osl.iu.edu/research/mtl/mtl4/doc/matrix_assignment.html#move_semantics
 

So let me throw out the following idea:
1) People really want functional style returns, for all of the usual reasons.
2) I think that there are a lot of people using compilers with C++0X support, especially in numerics.  Intel 11.1 supports auto, decltype, and rvalue references.  GNU already has it.  And MSVC 2010 with have all of these as well.  I think it is reasonable to have some features that selectively turn features on based on compiler support.
3) Boost::move seems to be getting there... http://svn.boost.org/svn/boost/sandbox/move/libs/move/doc/html/index.html  so it might even be possible to get stuff working with C++03.

So, with all that said... is a possible solution to the return value thing to implement rvalues constructors, etc. for the matrix and vector expressions?  http://svn.boost.org/svn/boost/sandbox/move/libs/move/doc/html/move/implementing_movable_classes.html#move.implementing_movable_classes.copyable_and_movable_cpp0x

Could we have a preprocessor instruction that generates the rvalue implementations?  Can the assign_temporary() be used here to make the code easy?

If the assign_temporary only works for expressions of the same type, it might not work so well, but thought I would throw out the idea.  This feature would be almost as important as the operator* overloads for usability.

-Jesse


_______________________________________________
ublas mailing list
ublas@...
http://lists.boost.org/mailman/listinfo.cgi/ublas
Sent to: lists@...

[Nasos Iliopoulos]

Some parts of this message have been removed. Learn more about Nabble's security policy.

Wouldn't changing vectors' operator = allow that?
From:

BOOST_UBLAS_INLINE

vector &operator = (const vector &v) {

data () = v.data ();

return *this;

}

to

// pass by value for move semantics

BOOST_UBLAS_INLINE

vector &operator = (vector v) {

data().swap(v.data());

return *this;
}

and maybe add some checks depending on storage type.

On Fri, 2009-08-28 at 08:24 -0400, Jesse Perla wrote:
Hi there,

> I am writing many routines where I would strongly prefer: matrix<double> f(const matrix<double>& in)   to void f(const matrix<double>& in, matrix<double>& out )
> There has been a lot of discussion about this from the C++ groups:
> The move library to support this in C++03
>       * http://cpp-next.com/archive/2009/08/want-speed-pass-by-value/
>       * Also, I see that this is native to MTL:  http://www.osl.iu.edu/research/mtl/mtl4/doc/matrix_assignment.html#move_semantics
>
> I don't understand expression templates well enough to know the current state in ublas, but is it possible to return large matrices in this way?  For example, if I took the following code: http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?LU_Matrix_Inversion and had it return a matrix instead, would that give overhead for large matrices?
> Could I even nest it with no overhead in other vector expressions:   e.g.
> matrix<double> C, B; //setup.  Assume they are very large
> matrix<double> A = inv(B) + C;
>
> If this pattern is not usable yet, any idea of when it would be?
>
> Thanks,
> Jesse
>
> _______________________________________________
> ublas mailing list
> ublas@...
> http://lists.boost.org/mailman/listinfo.cgi/ublas

---

Windows Live: Make it easier for your friends to see what you’re up to on Facebook. Find out more.
_______________________________________________
ublas mailing list
ublas@...
http://lists.boost.org/mailman/listinfo.cgi/ublas
Sent to: lists@...

[Jesse Perla]

On Thu, Sep 10, 2009 at 10:04 AM, Nasos Iliopoulos <nasos_i@...> wrote:

Wouldn't changing vectors' operator = allow that?
From:

BOOST_UBLAS_INLINE

vector &operator = (const vector &v) {

data () = v.data ();

return *this;

}

to

// pass by value for move semantics

BOOST_UBLAS_INLINE

vector &operator = (vector v) {

data().swap(v.data());

return *this;
}

I believe the above is called shallow copy and changes the current semantics of ublas (see http://www.osl.iu.edu/research/mtl/mtl4/doc/shallow_copy_problems.html) .  For example:
matrix<double> A(2,2);
//..... set A....

matrix<double> B = A;

Now they point at the same thing, not a copy/move.


Also, what about rvalues.  e.g.:

matrix<double> A = 2 * B;


And last, since this is using expression templates, the "data" vector may not exist, and will frequently not have the same type.


I don't know that much about this stuff, but my understanding is that rvalue refereces and move semantics allow a library to overload the rvalue assignment to do a this kind of pointer swapping.  But this stuff is probably very difficult to do.

-Jesse


_______________________________________________
ublas mailing list
ublas@...
http://lists.boost.org/mailman/listinfo.cgi/ublas
Sent to: lists@...

[Nasos Iliopoulos]

Some parts of this message have been removed. Learn more about Nabble's security policy.

Jesse,
>I don't know that much about this stuff, but my understanding is that rvalue refereces and move semantics allow a library to overload the rvalue assignment to do a this kind of pointer swapping.  But this stuff is probably very difficult to do.

That's the trick data().swap(..) does, it takes the passed by value data and swaps its pointer with the object calling it <--I can discuss a bit more about that but it may get too technical (i.e. std::swap(..,..) vs container.swap(...) ). Also the compiler should be (in my case is) responsible to take care of the value passed using copy elision. If it is an rvalue it will pass it in without copying; or copy it if it is not - which is what we want.

I did some tests and if the you are interested I can prepare to post them. The memory in those tests certainly shows half memory usage with move semantics for a large vector. Tracing back gives no indication of the existence of two containers and the performance is increased by about 20-30%. Also there is no indication of shallow copy (left and right side containers remain two distinct objects with distinct storage).

Very Best
Nasos Iliopoulos
 

---

From: jesseperla@...
Date: Thu, 10 Sep 2009 17:09:38 -0400
To: ublas@...
Subject: Re: [ublas] Move Semantics

On Thu, Sep 10, 2009 at 10:04 AM, Nasos Iliopoulos <nasos_i@...> wrote:

Wouldn't changing vectors' operator = allow that?
From:

BOOST_UBLAS_INLINE

vector &operator = (const vector &v) {

data () = v.data ();

return *this;

}

to

// pass by value for move semantics

BOOST_UBLAS_INLINE

vector &operator = (vector v) {

data().swap(v.data());

return *this;
}

I believe the above is called shallow copy and changes the current semantics of ublas (see http://www.osl.iu.edu/research/mtl/mtl4/doc/shallow_copy_problems.html) .  For example:
matrix<double> A(2,2);
//..... set A....

matrix<double> B = A;

Now they point at the same thing, not a copy/move.


Also, what about rvalues.  e.g.:

matrix<double> A = 2 * B;


And last, since this is using expression templates, the "data" vector may not exist, and will frequently not have the same type.


I don't know that much about this stuff, but my understanding is that rvalue refereces and move semantics allow a library to overload the rvalue assignment to do a this kind of pointer swapping.  But this stuff is probably very difficult to do.

-Jesse

---

Windows Live: Make it easier for your friends to see what you’re up to on Facebook. Find out more.
_______________________________________________
ublas mailing list
ublas@...
http://lists.boost.org/mailman/listinfo.cgi/ublas
Sent to: lists@...

[Jesse Perla]

On Thu, Sep 10, 2009 at 5:43 PM, Nasos Iliopoulos <nasos_i@...> wrote:

Jesse,

>I don't know that much about this stuff, but my understanding is that rvalue refereces and move semantics allow a library to overload the rvalue assignment to do a this kind of pointer swapping.  But this stuff is probably very difficult to do.

I guess I knew what I was talking about when I suggested I don't know what I am talking about.
 

That's the trick data().swap(..) does, it takes the passed by value data and swaps its pointer with the object calling it <--I can discuss a bit more about that but it may get too technical (i.e. std::swap(..,..) vs container.swap(...) ). Also the compiler should be (in my case is) responsible to take care of the value passed using copy elision. If it is an rvalue it will pass it in without copying; or copy it if it is not - which is what we want.

I did some tests and if the you are interested I can prepare to post them. The memory in those tests certainly shows half memory usage with move semantics for a large vector. Tracing back gives no indication of the existence of two containers and the performance is increased by about 20-30%. Also there is no indication of shallow copy (left and right side containers remain two distinct objects with distinct storage).

Wow... is it really that easy?  I thought the above code would cause all sorts of aliasing disasters...

Is this really good enough to use for functions returning big matrices as return values?

Take the following:
template<typename MatrixT>
matrix<double> inv(const matrix_expression<MatrixT>& A)
{
  matrix<double> B(A().size1(), A().size2());
  //Say a complicated sequence to invert A into B, which can't just return a matrix expression.

return B;
}

vs. a standard one with the return value passed in by non-const reference.
template<typename MatrixT>
void inv(const matrix_expression<MatrixT>& A, matrix<double>& B)
{
  //Complicated sequence to invert A into B, which can't just return a matrix expression.
}

//Now take the client code, for very large matrices.
matrix<double> B = inv(A); //Does the swap method above cause an invalid data pointer due to returning a temporary?

Any overhead in the copy vs. inv(A, B); ?

//Now do it with matrix expressions on both sides...
matrix<double> B = 2 * inv( .5 * A);

Is there any overhead on this vs.:
matrix<double> B(A.size1(), A.size2());
inv(.5 * A, B);
B *= 2;



_______________________________________________
ublas mailing list
ublas@...
http://lists.boost.org/mailman/listinfo.cgi/ublas
Sent to: lists@...

[Nasos Iliopoulos]

Some parts of this message have been removed. Learn more about Nabble's security policy.

>Take the following:
>template<typename MatrixT>
>matrix<double> inv(const matrix_expression<MatrixT>& A)
>{
> matrix<double> B(A().size1(), A().size2());
> //Say a complicated sequence to invert A into B, which can't just return a matrix expression.
>
>return B;
>}

The code I tried it on was:

ublas::vector<double> doubleit(const ublas::vector<double> &m)

{

double<vector> r;

r=2.0*m;

return r;

}

So I don't see any reason why it shouldn't work on the inverse. With copy elision what will happen in the code you posted is the following:
(let's say that you do C=inv(A);
A will be of course be passed by reference
B will be created normally.
when B is returned it will be returned with copy elision (i.e. no real copy will happen)
when C is assigned to that, move semantics will kick in since it is assigned to an rvalue and just storage will be swaped (so no copy again).

Haven't tried it to see what a back trace will do, but I may if it is considered by uBlas developers.

> //Now do it with matrix expressions on both sides...
> matrix<double> B = 2 * inv( .5 * A);

so in this case:
0.5*A will first create an expression.
if inv is defined to work on matrix expressions there should be no copy here.
inv will then create the inverse matrix inside it.
the inverse matrix from within inv will return with copy eilision, so no copy will happen
2*...  will create a matrix expression.

up to know no unnecessary temporaries exist. From now on though:

B= assigned to this expression will create a temporary that the expression is evaluated into.

So, one unnecssary temporary here. Of course you could do:
B=inv(0.5*A); B*=2.0;

Lastly note this:
 matrix<double> B = 2 * inv( .5 * A); will call the copy constructor (not move semantics friendly).
move semantics friendly: matrix<double> B ; B=....

Best Regards
Nasos Iliopoulos

---

From: jesseperla@...
Date: Thu, 10 Sep 2009 20:05:39 -0400
To: ublas@...
Subject: Re: [ublas] Move Semantics

On Thu, Sep 10, 2009 at 5:43 PM, Nasos Iliopoulos <nasos_i@...> wrote:

Jesse,

>I don't know that much about this stuff, but my understanding is that rvalue refereces and move semantics allow a library to overload the rvalue assignment to do a this kind of pointer swapping.  But this stuff is probably very difficult to do.

I guess I knew what I was talking about when I suggested I don't know what I am talking about.
 

That's the trick data().swap(..) does, it takes the passed by value data and swaps its pointer with the object calling it <--I can discuss a bit more about that but it may get too technical (i.e. std::swap(..,..) vs container.swap(...) ). Also the compiler should be (in my case is) responsible to take care of the value passed using copy elision. If it is an rvalue it will pass it in without copying; or copy it if it is not - which is what we want.

I did some tests and if the you are interested I can prepare to post them. The memory in those tests certainly shows half memory usage with move semantics for a large vector. Tracing back gives no indication of the existence of two containers and the performance is increased by about 20-30%. Also there is no indication of shallow copy (left and right side containers remain two distinct objects with distinct storage).

Wow... is it really that easy?  I thought the above code would cause all sorts of aliasing disasters...

Is this really good enough to use for functions returning big matrices as return values?

Take the following:
template<typename MatrixT>
matrix<double> inv(const matrix_expression<MatrixT>& A)
{
  matrix<double> B(A().size1(), A().size2());
  //Say a complicated sequence to invert A into B, which can't just return a matrix expression.

return B;
}

vs. a standard one with the return value passed in by non-const reference.
template<typename MatrixT>
void inv(const matrix_expression<MatrixT>& A, matrix<double>& B)
{
  //Complicated sequence to invert A into B, which can't just return a matrix expression.
}

//Now take the client code, for very large matrices.
matrix<double> B = inv(A); //Does the swap method above cause an invalid data pointer due to returning a temporary?

Any overhead in the copy vs. inv(A, B); ?

//Now do it with matrix expressions on both sides...
matrix<double> B = 2 * inv( .5 * A);

Is there any overhead on this vs.:
matrix<double> B(A.size1(), A.size2());
inv(.5 * A, B);
B *= 2;

---

Hotmail® is up to 70% faster. Now good news travels really fast. Try it now.
_______________________________________________
ublas mailing list
ublas@...
http://lists.boost.org/mailman/listinfo.cgi/ublas
Sent to: lists@...

[Gunter Winkler]

Hello Nasos,

your explanation were very helpful. Could you provide an experimental
patch and a small test program to demonstrate the effects?

I suggest to add a preprocessor condition to enable/disable the move
semantics. This way we could easily add this feature to uBLAS in the
upcoming release without the risk of breaking someones code.

mfg
Gunter

Nasos Iliopoulos schrieb:

> >Take the following:
> [snip examples on move semantics]
> So, one unnecssary temporary here. Of course you could do:
> B=inv(0.5*A); B*=2.0;
>
> Lastly note this:
>  matrix<double> B = 2 * inv( .5 * A); will call the copy constructor
> (not move semantics friendly).
> move semantics friendly: matrix<double> B ; B=....
>

_______________________________________________
ublas mailing list
ublas@...
http://lists.boost.org/mailman/listinfo.cgi/ublas
Sent to: lists@...

[Nasos Iliopoulos]

Some parts of this message have been removed. Learn more about Nabble's security policy.

Hello Gunter,
I will do in the upcoming days. A great benefit that I see coming with this is the elimination of the need for noalias.
But there are some issues we must have in mind:
--Move semantics at this stage are done by copy elision and are NOT GUARANTEED  to be implemented by compilers. Preprocessor condition and maybe a test suite will make it sure for everyone. Compiler checks will also do. So this may tern to be a non-issue.

--To take full advantage of move semantics you really need rvalues (&& reference). Those are in the c++0x standard and not fully supported yet by most compilers. It would be nice to keep an experimental implementation since they will eventually be available and will greatly benefit uBlas.

--My last point is that with move semantics, resource stealing, perfect forwarding etc., we might be able to get B = inv(A) + C; with absolutely no unecessary copies. But there may be issues with expression templates (maybe it will be feasible to not need e.ts for rvalue evaluation) and I don't really know if uBlasers want to go that way anytime in the future. I am pretty positive in doing so, but I don't quite feel the weight of such a decision.

Will post my patches in the near future for the copy elision and basic move semantics.

Very Best
Nasos Iliopoulos

> Date: Sat, 12 Sep 2009 22:11:23 +0200
> From: guwi17@...
> To: ublas@...
> Subject: Re: [ublas] Move Semantics
>
> Hello Nasos,
>
> your explanation were very helpful. Could you provide an experimental
> patch and a small test program to demonstrate the effects?
>
> I suggest to add a preprocessor condition to enable/disable the move
> semantics. This way we could easily add this feature to uBLAS in the
> upcoming release without the risk of breaking someones code.
>
> mfg
> Gunter
>
> Nasos Iliopoulos schrieb:
> > >Take the following:
> > [snip examples on move semantics]
> > So, one unnecssary temporary here. Of course you could do:
> > B=inv(0.5*A); B*=2.0;
> >
> > Lastly note this:
> > matrix<double> B = 2 * inv( .5 * A); will call the copy constructor
> > (not move semantics friendly).
> > move semantics friendly: matrix<double> B ; B=....
> >
>
> _______________________________________________
> ublas mailing list
> ublas@...
> http://lists.boost.org/mailman/listinfo.cgi/ublas
> Sent to: nasos_i@...

---

Bing brings you health info from trusted sources. Try it now!
_______________________________________________
ublas mailing list
ublas@...
http://lists.boost.org/mailman/listinfo.cgi/ublas
Sent to: lists@...