[patch] Move Semantics for uBlas

[Nasos Iliopoulos]

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

Dear all,
In response to the discussion on move semantics in this list I am sending this patch, that implements move semantics in uBlas as currently supported by most compilers, along with a test program. As you will find out the additions are minimal.

An immediate effect of this patch is the elimination of the need for noalias in types vector<T> and matrix<T>, when assigned to the same type. Although this patch implements move semantics for bounded_ and c_ (vector and matrix) types, they don't have any effect at those types, due to their underlying storage. I included it for possible future exploitation.

In the test example (main.cpp) two tests are defined, one for vectors and one for matrices. The aim of this example is to print the pointers of the storage of each of the containers, before and after the assignment to a temporary object. When move semantics are enabled, the vector<T> and matrix<T> storage is moved from the temporary and no copy is performed.

If move semantics are supported by your compiler you will get an output like the following:
matrix<double> --------------------------------------------------------------------
Temporary pointer r: 0x94790c0
Pointer (must be equal to temp. pointer if move semantics are enabled) : 0x94790c0

Notes:
 - It should be no surprise to see matrices and vectors been passed by VALUE, the compiler takes care and either moves (if the underlying code does not modify the object), or copies (if the underlying code modifies the object).
 - There might be some space for some improvements (like clearing the data, before swaping)
 - Move semantics don't eliminate temporaries. They rather move their storage around so no copies are performed.
 - MSVC does no implement Named Return Value Optimization in debug mode. So if you build in debug with this compiler you might get different behaviour than a release build. Also see:
https://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?FeedbackID=483229
 - Enabling move semantics is done via #define BOOST_UBLAS_MOVE_SEMANTICS.
 - All unit tests run successfully.
 - There is plenty of room for optimizations when c++0x standard is out, taking advantage of rvalue references. (I have a sweet vector implementation using that).
 - If you enable move semantics and your compiler does not support them, the operation will just be as passing by const reference.

Your valuable feedback would be much appreciated.

Interesting links.
[1] http://cpp-next.com/archive/2009/08/want-speed-pass-by-value/
[2] http://blogs.msdn.com/vcblog/archive/2009/02/03/rvalue-references-c-0x-features-in-vc10-part-2.aspx
[3] http://cpp-next.com/archive/2009/09/move-it-with-rvalue-references/

Best
Nasos Iliopoulos

---

Ready for Fall shows? Use Bing to find helpful ratings and reviews on digital tv's. Click here.

---

#define BOOST_UBLAS_MOVE_SEMANTICS
#include <boost/numeric/ublas/vector.hpp>
#include <boost/numeric/ublas/matrix.hpp>
#include "boost/numeric/ublas/io.hpp"

namespace ublas= boost::numeric::ublas;
std::vector<double> a;

ublas::vector<double> doubleit(ublas::vector<double> m)
{
    ublas::vector<double> r;
    r=2.0*m;
    std::cout << "Temporary pointer: " << &r[0] << std::endl;
    return r;
}
template <class T,size_t N>
ublas::bounded_vector<T,N > doubleit(ublas::bounded_vector<T, N> m)
{
    ublas::bounded_vector<T,N> r;
    r=2.0*m;
    std::cout << "Temporary pointer: " << &r[0] << std::endl;
    return r;
}

template <class T,size_t N>
ublas::c_vector<T,N > doubleit(ublas::c_vector<T, N> m)
{
    ublas::c_vector<T,N> r;
    r=2.0*m;
    std::cout << "Temporary pointer: " << &r[0] << std::endl;
    return r;
}

ublas::matrix<double> doubleit(ublas::matrix<double> m)
{
    ublas::matrix<double> r;
    r=2.0*m;
    std::cout << "Temporary pointer r: " << &r(0,0) << std::endl;
    return r;
}
template <class T,size_t N, size_t M>
ublas::bounded_matrix<T,N, M > doubleit(ublas::bounded_matrix<T, N, M> m)
{
    ublas::bounded_matrix<T,N, M> r;
    r=2.0*m;
    std::cout << "Temporary pointer: " <<  &(r(0,0)) << std::endl;
    return r;
}

template <class T,size_t N, size_t M>
ublas::c_matrix<T,N, M > doubleit(ublas::c_matrix<T, N, M> m)
{
    ublas::c_matrix<T,N, M> r;
    r=2.0*m;
    std::cout << "Temporary pointer: " << &(r(0,0)) << std::endl;
    return r;
}


void test1()
{
    std::cout << "vector<double> --------------------------------------------------------------------" << std::endl;
    ublas::vector<double> a(ublas::scalar_vector<double>(2,2.0));
    a = doubleit(a);
    std::cout << "Pointer (must be equal to temp. pointer if move semantics are enabled) : " << &a[0] << std::endl;

    std::cout << a << std::endl;

    std::cout << "bounded_vector<double,2> --------------------------------------------------------------------" << std::endl;
    ublas::bounded_vector<double,2> b(ublas::scalar_vector<double>(2,2.0));
    ublas::bounded_vector<double,2> c;
    noalias(c)=doubleit(b);
    std::cout << "Pointer (bounded_vector swaps by copy this should be different than temp. pointer) : " << &c[0] << std::endl;
    c(1)=0.0;
    std::cout << b << std::endl;
    std::cout << c << std::endl;

    std::cout << "c_vector<double,2> --------------------------------------------------------------------" << std::endl;
    ublas::c_vector<double,2> e=ublas::scalar_vector<double>(2,2.0);
    ublas::c_vector<double,2> f;
    f=doubleit(e);
    std::cout << "Pointer (c_vector swaps by copy this should be different than temp. pointer) : " << &f[0] << std::endl;
    f(1)=0;
    std::cout << e << std::endl;
    std::cout << f << std::endl;

}

void test2() {
    std::cout << "matrix<double> --------------------------------------------------------------------" << std::endl;
    ublas::matrix<double> a(ublas::scalar_matrix<double>(2, 3, 2.0));
    a = doubleit(a);
    std::cout << "Pointer (must be equal to temp. pointer if move semantics are enabled) : " << &(a(0,0)) << std::endl;
    std::cout << a << std::endl;

    std::cout << "bounded_matrix<double,2, 3> --------------------------------------------------------------------" << std::endl;
    ublas::bounded_matrix<double,2, 3> b(ublas::scalar_matrix<double>(2,3, 2.0));
    ublas::bounded_matrix<double,2, 3> c;
    noalias(c)=doubleit(b);
    std::cout << "Pointer (bounded_matrix swaps by copy this should be different than temp. pointer) : " << &(c(0,0)) << std::endl;
    c(1,1)=0.0;
    std::cout << b << std::endl;
    std::cout << c << std::endl;

    std::cout << "c_matrix<double,2 ,3> --------------------------------------------------------------------" << std::endl;
    ublas::c_matrix<double,2, 3> e=ublas::scalar_matrix<double>(2,3, 2.0);
    ublas::c_matrix<double,2, 3> f;
    f=doubleit(e);
    std::cout << "Pointer (c_matrix swaps by copy this should be different than temp. pointer) : " << &(f(0,0)) << std::endl;
    f(1,1)=0;
    std::cout << e << std::endl;
    std::cout << f << std::endl;
}

int main(){
    test1();
    test2();
    return 0;
}

---

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

I haven't studied this in any detail.  Do I understand correctly that this
is an optimization for compilers that don't elide constructors?

I have tested a few times in the past the modern gcc will elide
constructors, and returning containers by value does not cause unneeded
copies.

Is the point of this only to allow containers to be returned by value, or is
there more to it?

_______________________________________________
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.

Neal,
the pattern works as follows:

1. For compilers that elide:
a. Passing by value, the arguments will be either moved inside a function (if the function doesn't modify them) or not (if it does modify them). For assignment operations either is what we would like to happen. And it is unlikely that an assignment will try to change the argument, unless it is the same as the assignee, in which case nothing happens.
b. By employing light swap functions (i.e. like ublas' assign_temporary) there is no copy when "this" accepts the storage.
The above pattern is similar as been passed by reference, but without the need for an extra temporary copy operation, since source and destination are guaranteed to be different.

2. For compilers that do not elide.
a. Passing by value, copies the source object into the function regardless.
b. The passed value is again assigned to a temporary and swaped.
This situation is equivallent as the one currently supported in boost (passing by const reference and assigning through a temporary and a copy). The difference is that the copy happens first and the temporary is assigned afterwords.

To sum up:
For elision enabled compilers, assignment doesn't need a copy.
For no-elision enabled compilers, assignment works as it works now.

With gcc 4.3.3 (it does elision), you can see the benefits of 1, in the pointers outputed before and after the assignment operation for ONLY matrix<T> and vector<T>. (in the test program I provided)
i. With BOOST_UBLAS_MOVE_SEMANTICS, the pointers are the same (i.e. the underlying objects have been swaped and no copy is performed)
ii. Without BOOST_UBLAS_MOVE_SEMANTICS, the pointers are different (i.e. the assignment has been done through a temporary and a copy).

(ii) is the current situation in uBlas and (i) is with the proposed patch.

Hope that answers your questions
Best
Nasos

> To: ublas@...
> From: ndbecker2@...
> Date: Tue, 15 Sep 2009 07:20:30 -0400
> Subject: Re: [ublas] [patch] Move Semantics for uBlas
>
> I haven't studied this in any detail. Do I understand correctly that this
> is an optimization for compilers that don't elide constructors?
>
> I have tested a few times in the past the modern gcc will elide
> constructors, and returning containers by value does not cause unneeded
> copies.
>
> Is the point of this only to allow containers to be returned by value, or is
> there more to it?
>
> _______________________________________________
> ublas mailing list
> ublas@...
> http://lists.boost.org/mailman/listinfo.cgi/ublas
> Sent to: nasos_i@...

---

Ready for Fall shows? Use Bing to find helpful ratings and reviews on digital tv's. Click here.
_______________________________________________
ublas mailing list
ublas@...
http://lists.boost.org/mailman/listinfo.cgi/ublas
Sent to: lists@...

[Jesse Perla]

On Mon, Sep 14, 2009 at 10:59 PM, Nasos Iliopoulos <nasos_i@...> wrote:

Dear all,
An immediate effect of this patch is the elimination of the need for noalias in types vector<T> and matrix<T>, when assigned to the same type. Although this patch implements move semantics for bounded_ and c_ (vector and matrix) types, they don't have any effect at those types, due to their underlying storage. I included it for possible future exploitation.

Nasos:
This is great, I look forward to playing with it.

What is involved for doing this for bounded_ ?  I use them all over the place.  Is it tough to do this with C++03 but easier with rvalue references?  If so, I don't mind requiring the necessary C++0X features (my target compilers already support it).

Thanks,
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.

The problem with bounded_... and c.. is that they allocate space into the stack, so swaping needs to actually copy their elements, hence nullifying the effects of move semantics. I think for the bounded_.... classes changing from ownership of the underlying container to a pointer to them (and necesseary changes in construction, destruction and swap), will do it (We can right? my mind is not looping here?).  For the c_.... we will probably need to introduce boost::array. The important thing is to keep them into the stack.

Also, rvalue reference is not a cure for everything. Even with that, bounded_... and c_... will not be move semantics enabled. Although a first effect of c++0x rvalue references will be that we can enable prod(A,prod(B,prod(C,prod(D,F)))) without unnecesarry copies.
The standard is getting its final wording and hopefully there will be a semi-final edition for all of us to follow soon.

I may post some c++0x code, just for mind feeding.

Best
Nasos

---

From: jesseperla@...
Date: Tue, 15 Sep 2009 08:49:23 -0400
To: ublas@...
Subject: Re: [ublas] [patch] Move Semantics for uBlas

On Mon, Sep 14, 2009 at 10:59 PM, Nasos Iliopoulos <nasos_i@...> wrote:

Dear all,
An immediate effect of this patch is the elimination of the need for noalias in types vector<T> and matrix<T>, when assigned to the same type. Although this patch implements move semantics for bounded_ and c_ (vector and matrix) types, they don't have any effect at those types, due to their underlying storage. I included it for possible future exploitation.

Nasos:
This is great, I look forward to playing with it.

What is involved for doing this for bounded_ ?  I use them all over the place.  Is it tough to do this with C++03 but easier with rvalue references?  If so, I don't mind requiring the necessary C++0X features (my target compilers already support it).

Thanks,
Jesse

---

Ready for Fall shows? Use Bing to find helpful ratings and reviews on digital tv's. Click here.
_______________________________________________
ublas mailing list
ublas@...
http://lists.boost.org/mailman/listinfo.cgi/ublas
Sent to: lists@...

[Jesse Perla]

On Tue, Sep 15, 2009 at 9:49 AM, Nasos Iliopoulos <nasos_i@...> wrote:

The problem with bounded_... and c.. is that they allocate space into the stack, so swaping needs to actually copy their elements, hence nullifying the effects of move semantics. I think for the bounded_.... classes changing from ownership of the underlying container to a pointer to them (and necesseary changes in construction, destruction and swap), will do it (We can right? my mind is not looping here?).  For the c_.... we will probably need to introduce boost::array. The important thing is to keep them into the stack.

But if has a pointer to them, how do we have it statically allocated?  I must be missing something.  On the other hand, if something is created on the stack, the compilers still can do copy elision (e.g. the make_ pattern for object constructor functions), so I am thoroughly confused by this stuff.  Maybe these would already have copy elision with optimizations on?  Is there anyway to check this?  It seems that as soon as we do anything to the pointer in the function to display it, the compiler would stop doing the elision...

I read this a while back, but didn't understand it well enough: http://cpp-next.com/archive/2009/08/want-speed-pass-by-value/

 

Also, rvalue reference is not a cure for everything. Even with that, bounded_... and c_... will not be move semantics enabled. Although a first effect of c++0x rvalue references will be that we can enable prod(A,prod(B,prod(C,prod(D,F)))) without unnecesarry copies.

Well, that is pretty damn useful itself.  People would love to have that prototype, and coupled with operator* overloading, ublas is getting a pretty powerful interface.  Is it hard to implement?

_______________________________________________
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.

>But if has a pointer to them, how do we have it statically allocated?  I must be missing something. 

You are right, my bad, what was I thinking?

> Is it hard to implement?

Move constructor in vector.hpp:
1...................

BOOST_UBLAS_INLINE

vector (vector &&v):

vector_container<self_type> ()

{ data_.swap(v.data());}

2.................
and when you implement a function, you do it somehow like that:

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

{

m*=2.0;

std::cout << "Temporary pointer: " << &m[0] << std::endl;

return std::move(m);

}

If you do those changes in the files I uploaded, you  can get:

a = doubleit(doubleit(doubleit(doubleit(a))));

with absolutely no copy.

Note: I have not invested enough time thinking of the above and any side effects it may have, although it shouldn't.

And again it will work only for matrix and vector types, not bounded and c types.

(compile with -std=gnu++0x)

Cheers
Nasos

---

From: jesseperla@...
Date: Tue, 15 Sep 2009 13:50:07 -0400
To: ublas@...
Subject: Re: [ublas] [patch] Move Semantics for uBlas

On Tue, Sep 15, 2009 at 9:49 AM, Nasos Iliopoulos <nasos_i@...> wrote:

The problem with bounded_... and c.. is that they allocate space into the stack, so swaping needs to actually copy their elements, hence nullifying the effects of move semantics. I think for the bounded_.... classes changing from ownership of the underlying container to a pointer to them (and necesseary changes in construction, destruction and swap), will do it (We can right? my mind is not looping here?).  For the c_.... we will probably need to introduce boost::array. The important thing is to keep them into the stack.

But if has a pointer to them, how do we have it statically allocated?  I must be missing something.  On the other hand, if something is created on the stack, the compilers still can do copy elision (e.g. the make_ pattern for object constructor functions), so I am thoroughly confused by this stuff.  Maybe these would already have copy elision with optimizations on?  Is there anyway to check this?  It seems that as soon as we do anything to the pointer in the function to display it, the compiler would stop doing the elision...

I read this a while back, but didn't understand it well enough: http://cpp-next.com/archive/2009/08/want-speed-pass-by-value/

 

Also, rvalue reference is not a cure for everything. Even with that, bounded_... and c_... will not be move semantics enabled. Although a first effect of c++0x rvalue references will be that we can enable prod(A,prod(B,prod(C,prod(D,F)))) without unnecesarry copies.

Well, that is pretty damn useful itself.  People would love to have that prototype, and coupled with operator* overloading, ublas is getting a pretty powerful interface.  Is it hard to implement?

---

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@...

[Gunter Winkler]

Hello Nasos,

Am Tuesday 15 September 2009 schrieb Nasos Iliopoulos:
> In response to the discussion on move semantics in this list I am
> sending this patch, that implements move semantics in uBlas as
> currently supported by most compilers, along with a test program. As
> you will find out the additions are minimal.

Do you agree that I quote your name and description on the documentation
pages and add the usual boost copyright header?

(see http://www.boost.org/users/license.html)

mfg
Gunter


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

[Gunter Winkler]

Hello Nasos,

Am Tuesday 15 September 2009 schrieb Nasos Iliopoulos:
> In the test example (main.cpp) two tests are defined, one for vectors
> and one for matrices. The aim of this example is to print the
> pointers of the storage of each of the containers, before and after
> the assignment to a temporary object. When move semantics are
> enabled, the vector<T> and matrix<T> storage is moved from the
> temporary and no copy is performed.

Is there any special reason why you set some values of the result
vectors to zero? This way the output is quite surprising (and looks
like a bug.)

mfg
Gunter


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

[Gunter Winkler]

Hello Jesse,

Am Tuesday 15 September 2009 schrieb Jesse Perla:
> Nasos:
> This is great, I look forward to playing with it.

I created a ticket [1] and committed the patch and some documentation.
Please have a look report improvements.

[1] https://svn.boost.org/trac/boost/ticket/3457

@Nasos: thanks for the detailed explanations and useful links.

mfg
Gunter


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

What result should I expect?  If I compile on gcc-4.4.1 with -O3 -std=c++0x
it looks like move semantics are not enabled:
 ./test_move
vector<double>
--------------------------------------------------------------------
Temporary pointer: 0x2561050
Pointer (must be equal to temp. pointer if move semantics are enabled) :
0x2561010
[2](4,4)
[rest of tests similar]

_______________________________________________
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.

Did you try -DBOOST_UBLAS_MOVE_SEMANTICS
?

> To: ublas@...
> From: ndbecker2@...
> Date: Wed, 16 Sep 2009 18:50:06 -0400
> Subject: Re: [ublas] [patch] Move Semantics for uBlas
>
> What result should I expect? If I compile on gcc-4.4.1 with -O3 -std=c++0x
> it looks like move semantics are not enabled:
> ./test_move
> vector<double>
> --------------------------------------------------------------------
> Temporary pointer: 0x2561050
> Pointer (must be equal to temp. pointer if move semantics are enabled) :
> 0x2561010
> [2](4,4)
> [rest of tests similar]
>
> _______________________________________________
> 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@...

[Nasos Iliopoulos]

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

Yes Gutner, sure.

> From: guwi17@...
> To: ublas@...
> Date: Wed, 16 Sep 2009 21:33:58 +0200
> Subject: Re: [ublas] [patch] Move Semantics for uBlas
>
> Hello Nasos,
>
> Am Tuesday 15 September 2009 schrieb Nasos Iliopoulos:
> > In response to the discussion on move semantics in this list I am
> > sending this patch, that implements move semantics in uBlas as
> > currently supported by most compilers, along with a test program. As
> > you will find out the additions are minimal.
>
> Do you agree that I quote your name and description on the documentation
> pages and add the usual boost copyright header?
>
> (see http://www.boost.org/users/license.html)
>
> mfg
> Gunter

---

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@...

[Nasos Iliopoulos]

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

There is no reason, did you try it with other values and get strange output?

> From: guwi17@...
> To: ublas@...
> Date: Wed, 16 Sep 2009 23:42:51 +0200
> Subject: Re: [ublas] [patch] Move Semantics for uBlas
>
> Hello Nasos,
>
> Am Tuesday 15 September 2009 schrieb Nasos Iliopoulos:
> > In the test example (main.cpp) two tests are defined, one for vectors
> > and one for matrices. The aim of this example is to print the
> > pointers of the storage of each of the containers, before and after
> > the assignment to a temporary object. When move semantics are
> > enabled, the vector<T> and matrix<T> storage is moved from the
> > temporary and no copy is performed.
>
> Is there any special reason why you set some values of the result
> vectors to zero? This way the output is quite surprising (and looks
> like a bug.)
>
> mfg
> Gunter

---

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@...

OK, got it working now.

_______________________________________________
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.

Also, you don't need -std=c++0x, since c++0x standard is not used.
Best
Nasos

> To: ublas@...
> From: ndbecker2@...
> Date: Wed, 16 Sep 2009 20:19:40 -0400
> Subject: Re: [ublas] [patch] Move Semantics for uBlas
>
> OK, got it working now.
>
> _______________________________________________
> ublas mailing list
> ublas@...
> http://lists.boost.org/mailman/listinfo.cgi/ublas
> Sent to: nasos_i@...

---

Hotmail: Free, trusted and rich email service. Get it now.
_______________________________________________
ublas mailing list
ublas@...
http://lists.boost.org/mailman/listinfo.cgi/ublas
Sent to: lists@...