From 4007238284411367029 X-Google-Thread: f78e5,516d54c6ff652958 X-Google-Attributes: gidf78e5,public X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news1.google.com!news3.google.com!out03a.usenetserver.com!news.usenetserver.com!in02.usenetserver.com!news.usenetserver.com!pd7cy1no!shaw.ca!news.alt.net!comp-std-cpp-robomod!not-for-mail From: Richard Smith Newsgroups: comp.std.c++ Subject: Re: "moveable data type" in comparison with "r-value reference" Date: Wed, 11 Apr 2007 17:39:50 CST Organization: NTL Lines: 251 Approved: Fergus Henderson , moderator of comp.std.c++ Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Trace: newsfe2-gui.ntli.net 1176330017 81.101.133.85 (Wed, 11 Apr 2007 23:20:17 BST) NNTP-Posting-Date: Wed, 11 Apr 2007 23:20:17 BST Return-Path: X-Authentication-Warning: mulga.csse.unimelb.edu.au: fjh set sender to devnull@stump.algebra.com using -f X-Robomod: STUMP, ichudov@algebra.com (Igor Chudov) X-Original-To: std-c++@mailman.ucar.edu Delivered-To: std-c++@mailman.ucar.edu User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.7.13) Gecko/20060717 Debian/1.7.13-0.2ubuntu1 X-Accept-Language: en X-Virus-Scanned: amavisd-new at ucar.edu X-Virus-Scanned: amavisd-new at csse.unimelb.edu.au X-Virus-Scanned: amavisd-new at csse.unimelb.edu.au Xref: g2news1.google.com comp.std.c++:8421 [Apologies if this has been sent twice] Grizlyk wrote: > I will try to continue to show differences between "moveable data type" and > "r-value reference", in order to project, that even simplest kind of > algorithms with moveable data type could not be implemented with the help of > "r-value reference". 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 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 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( 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 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 >, 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, 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 [see n1856], and is typically implemented as: namespace std { template typename tr1::remove_reference::type&& move(T&& t) { return t; } } (Where remove_reference is the TR1 metafunction declared in .) 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& ) { 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 (which doesn't support move construction), we have just one assignment operator -- the standard copy assignment operator: complex& complex::operator=( complex const& ); The expression std::move(*first) is an rvalue of type std::complex. (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 will try to continue to show differences between "moveable data type" and > "r-value reference", in order to project, that even simplest kind of > algorithms with moveable data type could not be implemented with the help of > "r-value reference". 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 ]