Re: [boost] [non-instrusive move] interest in new library?
Jeffrey Lee Hellrung, Jr. wrote
On Wed, Jan 9, 2013 at 3:35 AM, THOMAS JORDAN <tomjordan766@gmail.com>wrote:
Apologies, my previous email I sent incomplete by mistake, please ignore that in favour of the following: Hi, Would there be interest for Boost in a small library providing a simple, non-instrusive emulation of basic move semantics for C++03 (though one which could also be used without harm in a C++11 environment)?
The library currently consists of a small number of 'move' function overloads, plus a trait class. It can be used to facilitate move semantics/efficient value-orientated software design in environments which lack, or forbid C++11 or other, more intrusive C++03-aware move libraries (e.g., old/buggy compiler, learning curve prohibitive, etc.). In conjunction it facilitates/forces copy-elision and return-value (RVO) optimisations in certain situations where they might otherwise not be feasible.
It works as follows: it detects at compile-time if the type of the argument(s) has a member swap function, and if so, it performs a swap, otherwise it calls the regular assignment operator ('move if possible, copy otherwise').
It can be used to provide an emulation of: - move-assignment between lvalues - moving an rvalue to an lvalue - moving an lvalue to a temporary It also supports moving between built-in arrays.
Example use-cases are (ignoring namespace):
#include "non_intrusive_move.h"
//returning a value
std::string foo(std::string s) { //e.g., append something to s //... //compiler can perform rvo (compiler would likely not perform nrvo if just used 'return s;') return move(s); }
//moving a value to a function/ctor, when the value is not required by the calling code after the //function/ctor call
std::string s("hello"); void bar(std::string s){...} bar(s); //copy bar(move(s)); //move
//moving a value into place
void MyClass::MyClass(std::string s) { //move value from s into default constructed member s_ move(s, s_); }
Note that the combination of both moving a value to a function/ctor and then moving it into place
e.g., std::string lv; //... MyClass mc(move(lv)); //lv no longer needed
effectively results in a zero-copy invocation, with just a small number of fixed size swap, default ctor and shallow dtor calls, so this is pretty efficient.
//moving a temporary into an lvalue std:: string lv; move(foo(), lv); //nicer than foo().swap(lv)
The moved-from value is left in a 'valid' but undefined state, i.e., it can be destructed, assigned/moved to, swapped, etc.
The library is non-intrusive and generic, it will perform an efficient move in terms of swap for any type providing a member swap operation, e.g, std::vector, boost::array, user-defined types etc.
You didn't really expound on the implementation, but, if I had to guess, you'd also require your types to be default constructible, and it would perform suboptimally (worse than leaving the move call out) if the swap member function was equivalent to std::swap. I think this might preclude its use in generic contexts and limit its use to situations where you *know* the type is std::vector-like. Let me know if I'm presuming incorrectly :)
Yes, it certainly requires the types to be default constructible. For a type with an expensive swap, performance would be suboptimal. The library checks at compile-time whether the element type of the boost array has a swap member, and calls array.swap if true, and copies otherwise (recursively if the element type is also a boost array). However, the user would need to write an overload for a type with an expensive member swap, which precludes the true generic context. So yes, it is more aimed at situations where you have pretty firm knowledge of the types you will be using. This would either require a really strong caveat emptor or may not be acceptable for release into the wild? The alternative would be to have just the single, default, template move function: //pseudo-code move(T& left, T& right) plus a pair of template functions to move to and from temporaries respectively: T move(T& x) void move(const T& from, T& to) then have optimised move functions defined on a per-type basis, e.g., MyClass { void swap(MyClass& other){} friend void swap(MyClass& a, MyClass& b) { //efficient swap member } friend void move(MyClass& lhs, MyClass& rhs) { lhs.swap(rhs); } } as well as overloads defined for any cheap-to-swap library types interested in: void move(std::vector& lhs, std::vector& rhs){} void move(boost::function& lhs, boost::function& rhs){} etc. Although this is safer in that it should ensure optimality - and is actually where I started - it requires more boilerplate to be written, though there may be way(s) to automate the generation of the the user-type's move function. Also, with the library move functions implemented like this, you could still write algorithms like move()/move_backwards() (and helper functions such as iter_move() to move the values between two iterators) generically. So I guess the new question is, would this even smaller library be of any interest? Its use-cases would be the same as described in my original post, just to reiterate: //use-case: returning a argument directly from a function std::string foo(std::string s) { //e.g., append something to s //... //compiler can perform rvo (compiler would likely not //perform nrvo if just used 'return s;') return move(s); } //use-case: moving a value to a function/ctor, when the value is not //required by the calling code after the function/ctor call std::string s("hello"); void bar(std::string s){...} bar(s); //copy bar(move(s)); //move //s has now been moved out of //use-case: moving a value into place void MyClass::MyClass(std::string s) { //move value from s into default constructed member s_ move(s, s_); } Note that the combination of both moving a value to a function/ctor and then moving it into place, e.g., std::string lv; //... MyClass mc(move(lv)); effectively results in a zero-copy invocation, with just a small number of fixed size swap, default ctor and shallow dtor calls, so this is pretty efficient. //use-case: moving a temporary into an lvalue std:: string lv; move(foo(), lv);
- Jeff Tom
On 11/01/2013 09:58, Thomas Jordan wrote:
Jeffrey Lee Hellrung, Jr. wrote
You didn't really expound on the implementation, but, if I had to guess, you'd also require your types to be default constructible, and it would perform suboptimally (worse than leaving the move call out) if the swap member function was equivalent to std::swap. I think this might preclude its use in generic contexts and limit its use to situations where you *know* the type is std::vector-like. Let me know if I'm presuming incorrectly :)
Yes, it certainly requires the types to be default constructible.
For a type with an expensive swap, performance would be suboptimal. The library checks at compile-time whether the element type of the boost array has a swap member, and calls array.swap if true, and copies otherwise (recursively if the element type is also a boost array). However, the user would need to write an overload for a type with an expensive member swap, which precludes the true generic context. So yes, it is more aimed at situations where you have pretty firm knowledge of the types you will be using. This would either require a really strong caveat emptor or may not be acceptable for release into the wild?
The alternative would be to have just the single, default, template move function:
//pseudo-code move(T& left, T& right)
plus a pair of template functions to move to and from temporaries respectively:
T move(T& x) void move(const T& from, T& to)
then have optimised move functions defined on a per-type basis, e.g.,
MyClass { void swap(MyClass& other){} friend void swap(MyClass& a, MyClass& b) { //efficient swap member } friend void move(MyClass& lhs, MyClass& rhs) { lhs.swap(rhs); } }
as well as overloads defined for any cheap-to-swap library types interested in:
void move(std::vector& lhs, std::vector& rhs){} void move(boost::function& lhs, boost::function& rhs){} etc.
Although this is safer in that it should ensure optimality - and is actually where I started - Here is the code for the safer version:
//SimpleMove.h #include <boost/type_traits/integral_constant.hpp> #include <boost/type_traits/is_scalar.hpp> #include <iterator> #include <algorithm> //namespace for overloads of move() function namespace Overloads { //Default - move as copy template <typename T> inline void move(T& from, T& to) { T tmp(from); from = to; to = tmp; } } //namespace for implementation functions namespace SimpleMove_Impl { template <typename T> inline void move_impl(T& from, T& to) { using ::Overloads::move; //bring this into scope move(from, to); } template<typename I, typename O> inline O move_impl(I f, I l, O result, ::boost::true_type) { return std::copy(f,l,result); } template<typename I, typename O> inline O move_impl(I f, I l, O result, ::boost::false_type) { while (f != l) { ::SimpleMove::iter_move(f, result); ++f; ++result; } return result; } } //Namespace for interface functions namespace SimpleMove { //move a value between two temporaries template <typename T> inline void move(T& from, T& to) { ::SimpleMove_Impl::move_impl(from, to); } //move an lvalue to a temporary template <typename T> inline T move(T& x) { T tmp; ::SimpleMove_Impl::move_impl(x,tmp); return tmp; } //convenience function to more between iterators template<typename T> inline void iter_move(T it1, T it2) { ::SimpleMove_Impl::move_impl(*it1, *it2); } //move algorithm - could also have move_backward similarly template<typename I, typename O> inline O move(I f, I l, O result) { //dispatches to std::copy for scalar return ::SimpleMove_Impl::move_impl(f, l, result, ::boost::is_scalar<std::iterator_traits<I>::value_type>::type()); } //overload for built-in array template<class T, std::size_t N> inline void move(T (& left)[N], T (& right)[N]) { ::SimpleMove::move(left, (left + N), right); } } //utility to quickly define move functions for user-defined type in //terms of swap #define MAKE_MOVEABLE_USING_SWAP(X) \ inline void move(X& from)\ {\ this->swap(from);\ }\ inline friend void move(X& from, X& to)\ {\ to.move(from);\ } //MoveOverloads.h #include <vector> #include <string> #include <boost/array.hpp> //Add additional overloads you require, for e.g., types in std:: or boost::, to //Overloads namespace in the examples of std:: containers below, //implemented in terms of swap namespace Overloads { template<typename T> inline void move(std::vector<T>& left, std::vector<T>& right) { left.swap(right); } inline void move(std::string& left, std::string& right) { left.swap(right); } template<typename T, size_t N> inline void move(boost::array<T,N>& left, boost::array<T,N>& right) { SimpleMove::move(left.begin(), left.end(), right.begin()); } } This could be useful as it provides a support for basic move semantics via a very small library, enabling 'moving' of your own types via custom move functions and e.g., of C++03 std:: containers via their swap functions, in conjunction with (N)RVO and copy-elision. Tom.
On Jan 15, 2013, at 2:13 PM, Thomas Jordan <tomjordan766@gmail.com> wrote: [Please don't overquote.]
Here is the code for the safer version: [snip] //namespace for overloads of move() function namespace Overloads { //Default - move as copy template <typename T> inline void move(T& from, T& to) { T tmp(from); from = to; to = tmp; } }
//namespace for implementation functions namespace SimpleMove_Impl { template <typename T> inline void move_impl(T& from, T& to) { using ::Overloads::move; //bring this into scope move(from, to); } [snip] //convenience function to more between iterators template<typename T> inline void iter_move(T it1, T it2) { ::SimpleMove_Impl::move_impl(*it1, *it2); }
//move algorithm - could also have move_backward similarly template<typename I, typename O> inline O move(I f, I l, O result) { //dispatches to std::copy for scalar return ::SimpleMove_Impl::move_impl(f, l, result, ::boost::is_scalar<std::iterator_traits<I>::value_type>::type()); }
//overload for built-in array template<class T, std::size_t N> inline void move(T (& left)[N], T (& right)[N]) { ::SimpleMove::move(left, (left + N), right); } }
//utility to quickly define move functions for user-defined type in //terms of swap #define MAKE_MOVEABLE_USING_SWAP(X) \ inline void move(X& from)\ {\ this->swap(from);\ }\ inline friend void move(X& from, X& to)\ {\ to.move(from);\ }
//MoveOverloads.h #include <vector> #include <string> #include <boost/array.hpp>
//Add additional overloads you require, for e.g., types in std:: or boost::, to //Overloads namespace in the examples of std:: containers below, //implemented in terms of swap namespace Overloads { template<typename T> inline void move(std::vector<T>& left, std::vector<T>& right) { left.swap(right); }
inline void move(std::string& left, std::string& right) { left.swap(right); }
template<typename T, size_t N> inline void move(boost::array<T,N>& left, boost::array<T,N>& right) { SimpleMove::move(left.begin(), left.end(), right.begin()); } }
This could be useful as it provides a support for basic move semantics via a very small library, enabling 'moving' of your own types via custom move functions and e.g., of C++03 std:: containers via their swap functions, in conjunction with (N)RVO and copy-elision.
Using this for types not *always* "overloaded" by this library means ODR violations. Any type that is sometimes "overloaded", because the right header was included, and other times not leads to different instantiations of the function templates. ___ Rob
On 15/01/2013 19:13, Thomas Jordan wrote:
On 11/01/2013 09:58, Thomas Jordan wrote:
Jeffrey Lee Hellrung, Jr. wrote
You didn't really expound on the implementation, but, if I had to guess, you'd also require your types to be default constructible, and it would perform suboptimally (worse than leaving the move call out) if the swap member function was equivalent to std::swap. I think this might preclude its use in generic contexts and limit its use to situations where you *know* the type is std::vector-like. Let me know if I'm presuming incorrectly :)
Yes, it certainly requires the types to be default constructible.
For a type with an expensive swap, performance would be suboptimal. The library checks at compile-time whether the element type of the boost array has a swap member, and calls array.swap if true, and copies otherwise (recursively if the element type is also a boost array). However, the user would need to write an overload for a type with an expensive member swap, which precludes the true generic context. So yes, it is more aimed at situations where you have pretty firm knowledge of the types you will be using. This would either require a really strong caveat emptor or may not be acceptable for release into the wild?
The alternative would be to have just the single, default, template move function:
//pseudo-code move(T& left, T& right)
plus a pair of template functions to move to and from temporaries respectively:
T move(T& x) void move(const T& from, T& to)
then have optimised move functions defined on a per-type basis, e.g.,
MyClass { void swap(MyClass& other){} friend void swap(MyClass& a, MyClass& b) { //efficient swap member } friend void move(MyClass& lhs, MyClass& rhs) { lhs.swap(rhs); } }
as well as overloads defined for any cheap-to-swap library types interested in:
void move(std::vector& lhs, std::vector& rhs){} void move(boost::function& lhs, boost::function& rhs){} etc.
Although this is safer in that it should ensure optimality - and is actually where I started - Here is the code for the safer version:
//SimpleMove.h #include <boost/type_traits/integral_constant.hpp> #include <boost/type_traits/is_scalar.hpp> #include <iterator> #include <algorithm>
//namespace for overloads of move() function namespace Overloads { //Default - move as copy template <typename T> inline void move(T& from, T& to) { T tmp(from); from = to; to = tmp; } }
//namespace for implementation functions namespace SimpleMove_Impl { template <typename T> inline void move_impl(T& from, T& to) { using ::Overloads::move; //bring this into scope move(from, to); }
template<typename I, typename O> inline O move_impl(I f, I l, O result, ::boost::true_type) { return std::copy(f,l,result); }
template<typename I, typename O> inline O move_impl(I f, I l, O result, ::boost::false_type) { while (f != l) { ::SimpleMove::iter_move(f, result); ++f; ++result; } return result; } }
//Namespace for interface functions namespace SimpleMove { //move a value between two temporaries template <typename T> inline void move(T& from, T& to) { ::SimpleMove_Impl::move_impl(from, to); }
//move an lvalue to a temporary template <typename T> inline T move(T& x) { T tmp; ::SimpleMove_Impl::move_impl(x,tmp); return tmp; }
//convenience function to more between iterators template<typename T> inline void iter_move(T it1, T it2) { ::SimpleMove_Impl::move_impl(*it1, *it2); }
//move algorithm - could also have move_backward similarly template<typename I, typename O> inline O move(I f, I l, O result) { //dispatches to std::copy for scalar return ::SimpleMove_Impl::move_impl(f, l, result, ::boost::is_scalar<std::iterator_traits<I>::value_type>::type()); }
//overload for built-in array template<class T, std::size_t N> inline void move(T (& left)[N], T (& right)[N]) { ::SimpleMove::move(left, (left + N), right); } }
//utility to quickly define move functions for user-defined type in //terms of swap #define MAKE_MOVEABLE_USING_SWAP(X) \ inline void move(X& from)\ {\ this->swap(from);\ }\ inline friend void move(X& from, X& to)\ {\ to.move(from);\ }
//MoveOverloads.h #include <vector> #include <string> #include <boost/array.hpp>
//Add additional overloads you require, for e.g., types in std:: or boost::, to //Overloads namespace in the examples of std:: containers below, //implemented in terms of swap namespace Overloads { template<typename T> inline void move(std::vector<T>& left, std::vector<T>& right) { left.swap(right); }
inline void move(std::string& left, std::string& right) { left.swap(right); }
template<typename T, size_t N> inline void move(boost::array<T,N>& left, boost::array<T,N>& right) { SimpleMove::move(left.begin(), left.end(), right.begin()); } }
This could be useful as it provides a support for basic move semantics via a very small library, enabling 'moving' of your own types via custom move functions and e.g., of C++03 std:: containers via their swap functions, in conjunction with (N)RVO and copy-elision.
Tom. Here's a newer version of the code, which uses trait 'has_move' to make some optimisations, e.g., ensuring that move(T&) is 'optimal' for a type without an optimised move function. This library is intended as a simple set of utilities to help support some of the techniques discussed in, e.g., http://cpp-next.com/archive/2009/08/want-speed-pass-by-value/ (in particular for C++03-restricted environments).
//MoveFunctions.h #include "MoveOverloads.h" #include <boost/utility/enable_if.hpp> #include <boost/type_traits/integral_constant.hpp> #include <iterator> #include <algorithm> //Type traits to determine whether a type has a move function defined in Overloads namespace or in class namespace. //This trait class uses SFINAE and "sizeof trick" from the book "C++ Template Metaprogramming" by Abrahams and //Gurtovoy namespace friend_move_trait { template<typename T> struct has_move { typedef char yes; typedef char (&no)[2]; //SFINAE eliminates this when the type is invalid template <typename U, U> struct Check; template <typename U> static yes Tester(Check<void(*)(U&, U&), &move>*); //overload resolution prefers anything at all over ... template <typename U> static no Tester(...); static bool const value = sizeof(Tester<T>(0)) == sizeof(yes); }; } namespace overload_move_trait { template<typename T> struct has_move { typedef char yes; typedef char (&no)[2]; //SFINAE eliminates this when the type is invalid template <typename U, U> struct Check; template <typename U> static yes Tester(Check<void(*)(U&, U&), &Overloads::move>*); //overload resolution prefers anything at all over ... template <typename U> static no Tester(...); static bool const value = sizeof(Tester<T>(0)) == sizeof(yes); }; } namespace move_trait { template<typename T> struct has_move { static bool const value = overload_move_trait::has_move<T>::value || friend_move_trait::has_move<T>::value; }; } namespace Default { template <typename T> inline void move(T& from, T& to) { T tmp(from); from = to; to = tmp; } } namespace SimpleMove_Impl { template <typename T> inline void move_impl(T& from, T& to) { using ::Default::move; using ::Overloads::move; move(from, to); } //move iteratees if an optimal move function exists for I template<typename I, typename O> inline O move_impl(I f, I l, O result, ::boost::true_type) { while (f != l) { ::SimpleMove::iter_move(f, result); ++f; ++result; } return result; } //std::copy iteratees if no optimal move function exists for I template<typename I, typename O> inline O move_impl(I f, I l, O result, ::boost::false_type) { return std::copy(f,l,result); } } namespace SimpleMove { template <typename T> inline void move(T& from, T& to) { ::SimpleMove_Impl::move_impl(from, to); } //move an lvalue to a temporary if T has a move function defined template <typename T> inline T move(T& x, typename boost::enable_if<::move_trait::has_move<T>>::type* = 0) { T tmp; ::SimpleMove_Impl::move_impl(x,tmp); return tmp; } //pass lvalue through if no move function is defined for T template <typename T> inline T& move(T& x, typename boost::disable_if<::move_trait::has_move<T>>::type* = 0) { return x; } template<typename T> inline void iter_move(T it1, T it2) { ::SimpleMove_Impl::move_impl(*it1, *it2); } template<typename I, typename O> inline O move(I f, I l, O result) { return ::SimpleMove_Impl::move_impl(f, l, result, ::boost::integral_constant<bool, ::move_trait::has_move<std::iterator_traits<I>::value_type>::value>::type()); } template<class T, std::size_t N> inline void move(T (& left)[N], T (& right)[N]) { ::SimpleMove::move(left, (left + N), right); } } //utility to define move function in terms of swap #define MAKE_MOVEABLE_USING_SWAP(X) \ inline void move(X& from)\ {\ this->swap(from);\ }\ inline friend void move(X& from, X& to)\ {\ to.move(from);\ } //MoveOverloads.h // //This file is just a collection of #includes #include "SomeProvidedOverloads.h" //SomeProvidedOverloads.h // #include <boost/array.hpp> #include <vector> #include <string> #include <deque> namespace Overloads { template<typename T, size_t N> inline void move(boost::array<T,N>& left, boost::array<T,N>& right) { SimpleMove::move(left.begin(), left.end(), right.begin()); } inline void move(std::string& left, std::string& right) { left.swap(right); } template<typename T> inline void move(std::vector<T>& left, std::vector<T>& right) { left.swap(right); } template<typename T> inline void move(std::deque<T>& left, std::deque<T>& right) { left.swap(right); } } T.
participants (2)
-
Rob Stewart -
Thomas Jordan