Re: "moveable data type" in comparison with "r-value reference"

[Apologies if this has been sent twice]

Grizlyk wrote:


I dispute this. Let me demonstrate.

Let's invent a trivially simple algorithm that might gain from a movable
data type: an algorithm that removes the first n elements from a
sequence (defined by a pair of iterators in the usual way), shifts the
remaining iterators forward, and returns the new end iterator. Once the
algorithm has finished, the contents of the last n elements are in valid
but undefined state; assigning to or destroying these elements is
guaranteed to work (much like std::remove).

Here's my implementation in the current language (i.e. without rvalue
references or movable data types).

   template <typename ForwardIterator, typename Size>
   ForwardIterator
   shift_n( ForwardIterator first, ForwardIterator last, Size n)
   {
     ForwardIterator dest(first);
     for ( ; n && first != last; ++first, --n )
       ;
     for ( ; first != last; ++dest, ++first )
       *dest = *first;
     return dest;
   }

Obviously there are improvements that I would make before putting
putting this for production use -- for example, I would check that n is
positive, optimise for random access iterators (much as std::advance
does), and perhaps even consider a memmove optimisation for raw pointers
to PODs. Nevertheless it serves to illustrate the point.

And here's an example of it being used:

   int main() {
     int init[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
     std::vector<int> v( init, init + sizeof(init) / sizeof(*init) );

     v.erase( shift_n( v.begin(), v.end(), 5 ), v.end() );

     // Should print "5 6 7 8 9"
     std::copy( v.begin(), v.end(),
                std::ostream_iterator<int>( std::cout, " " ) );
     std::cout << "\n";
   }

This works fine, and in this implementation the last n elements (i.e.
the elements being erased) are untouched. However, my algorithm was
permitted to leave this elements in *any* convenient state (see
paragraph preceding the implementation), and this potentially allows me
to use a move optimisation. In the syntax of the rvalue reference
proposal, I can write this:

   template <typename ForwardIterator, typename Size>
   ForwardIterator
   shift_n( ForwardIterator first, ForwardIterator last, Size n)
   {
     ForwardIterator dest(first);
     for ( ; n && first != last; ++first, --n )
       ;
     for ( ; first != last; ++dest, ++first )
       *dest = std::move(*first);
     return dest;
   }

The only difference is that I've changed the line line *dest = *first to
use std::move. [The std::move() is a simple library helper function
defined in n1856. Compiler support beyond rvalue references is not
required to implement it.] This tells the compiler that, instead of
copying a value from *first to *dest, it should attempt to move it, and
only fall back to copying if a suitable move assignment operator doesn't
exist. This fall back behaviour is extremely important because it means
that I get the benefit of "movability" where it is supported, but
doesn't require all classes to support it.

So, for example, there is no proposal to make std::complex<> have any
"move constructors" as it wouldn't benefit from one. Basically, it's a
little struct with two POD data members -- it wouldn't be possible to
make a move constructor that was any more efficient than the (trivial)
copy constructor. So if I apply my move-enabled shift_n algorithm to a
std::vector< std::complex<double> >, it will just call the ordinary copy
assignment operator.

On the other hand, let's consider std::string. It is currently proposed
[see n1857] that this will have a move-assignment operator, as, in the
absence of copy-on-write, the copy assignment operator can be quite
expensive and a move assignment operator can do much better. Let's
imagine how the a simple string class might be written.

   class string {
   public:
     string( char const* s = NULL )
       : sz( s ? strlen(s) : 0u ), str( s ? new char[sz+1] : NULL )
       { if (s) strncpy( str, o.str, sz+1 ); }

     // Copy constructor -- does dynamic allocation
     string( string const& o )
       : sz( o.sz ), str( new char[sz+1] )
       { strncpy( str, o.str, sz+1 ); }

     // Move constructor -- does a move
     string( string&& o )
       : sz( o.sz ), str( o.str )
       { o.str = NULL; o.sz = 0u; }

     // Swap, and copy and move assignment operators
     void swap( string const& o )
       { std::swap(sz, o.sz); std::swap(str, o.str); }
     string& operator=( string const& o )
       { string(o).swap(*this); return *this; }
     string& operator=( string&& o )
       { string(o).swap(*this); return *this; }

     // And to access the string:
     char const* c_str() const { return str ? str : "\0"; }

   private:
     size_t sz;
     char* str;
   };

We can see that the move assignment operator is much more efficient than
the copy assignment operator as it doesn't need to do dynamic memory
allocation, or even any string copying. Move constructors, in general,
are supposed to leave their argument in an undefined but valid state.
In this case, it leaves the argument indistinguishable from a default
constructed string. If I apply my shift_n algorithm to a
std::vector<string>, I will get the benefit of this. (Try it! Download
ConceptGCC 4.3.0 alpha 6, which supports rvalue references, and try the
code. I've made sure that, modulo #includes, the examples are all
complete enough to compile. Put some logging in the different
constructors and try it.)

So how does this work? All of the "magic" occurs in the line

   *dest = std::move(*first);

of my shift_n algorithm... so let's look at this in detail. We know
that for a (sane) mutable input iterator, operator*() will return by
non-const reference, so *first is an lvalue of type V (the value_type of
the iterator). The std::move function is a trivial little helper
declared in <utility> [see n1856], and is typically implemented as:

   namespace std {
     template <typename T>
     typename tr1::remove_reference<T>::type&& move(T&& t) {
       return t;
     }
   }

(Where remove_reference is the TR1 metafunction declared in <type_traits>.)

Under the modified rules of template argument decuction [14.8.2.1/3 in
the working draft, n2135], when passed an lvalue of type V (still the
value_type of the iterator), the template parameter, T, of std::move
will be deduced as V&. And under the rules for template argument
substitution [14.3.1/4], this results in the instantiation of the
specialistion:

   V&& std::move<V&>( V& ) { return t; }

That is, the std::move function takes an lvalue reference argument and
changes it to an rvalue reference. No copy constructors / move
constructors are called.

The remaining thing is to find a assignment operator to accept the
result of std::move(*first). In the case of std::complex<double> (which
doesn't support move construction), we have just one assignment operator
-- the standard copy assignment operator:

  complex<double>&
  complex<double>::operator=( complex<double> const& );

The expression std::move(*first) is an rvalue of type
std::complex<double>. (Note it is not an expression of type
std::complex& as the type of an expression is never a reference type.)
In the rvalue reference proposal, just as in the current language,
rvalues can bind to constant references, and so this operator is called.
  In this case the introduction of std::move to my shift_n algorithm has
been minimal -- no extra copies or temporaries have been made, and any
decent compiler (with inlining enabled) will totally optimise the call
to std::move away. (Try it!)

What about a class with both copy and move constructors (such as my
naive string class, above). This time, the compiler finds too overloads:

     string& string::operator=( string const& o ); // copy
     string& string::operator=( string&& o ); // move

Overload resolution (as modified by the rvalue reference proposal) kicks
in, and an binding an rvalue to an rvalue reference is better than
binding it to a lvalue reference [13.3.3.2/3, bullet 1, sub-bullet 4] --
and so the move constructor is chosen.

So back to your original statement:


I have demonstrated in considerable detail how you can use rvalue
references to implement an algorithm (my shift_n function) that will
work nicely with a movable data type (my string class). Not only that,
but my algorithm will play nicely with existing types that are "merely"
copy constructible, and it required a minimal change to the existing
code. And if I have an older algorithm than isn't move-aware (such as
my original shift_n function: the one without the std::move), it will
work just fine with classes that have dual move/copy semantics (such as
my string class).

You've raised lots of other points in your post, but let's focus on this
one point. (I'm sorry to say I don't have time to deal individually
with each point in this degree of specificity.) Do you now accept that
it is in fact possible to implement "even the simplest kind of algorithm
with movable data types [...] with the help of rvalue references"? If
not, perhaps you can find a fault in my argument?

Note -- I'm not claiming that there's anything wrong with your suggested
approach using additional compile-time attributes. I suspect that in
fact it is very similar in its power and expressiveness, though, to be
quite honest, I haven't studied it in enough detail to be sure. But the
rvalue reference proposal has detailed technical documentation, it's
included in the current working draft, it's becoming increasingly
familiar to people, and it even has an implementation (ConceptGCC).

If you think your way is better than rvalue references, you need to do
more than just demonstrate that your approach is viable, or even good --
you need to demonstrate, with specificity, what is wrong with the
current (rvalue reference) proposal. You've indicated that implementing
algorithms on movable data is one such example; I've shown this doesn't
seem to be a problem by implementing an algorithm. Now it's your turn.
  Where is my argument wrong?

--
Richard Smith

---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]