Mathias Gaunard wrote:

On 08/20/2011 06:09 PM, Julian Gonggrijp wrote:

...

UNDERLYING_TYPE(T) represents a type which is (conceptually speaking) a POD-type with the same member data (and hence the same alignment) as T.

You mean like boost::aligned_storage<sizeof(T), boost::alignment_of<T>::value> ?

Pretty much. I think it could do the job. (Although of course it's not THE underlying type in a very strict conceptual sense.)

...

template<class T> void swap (T& x, T& y) { UNDERLYING_TYPE(T) temp; move_raw (x, temp); move_raw (y, x); move_raw (temp, y); }

This clearly looks like undefined behaviour.

It isn't. :-) The code is guaranteed to swap x and y and leave them in a valid state. temp will be discarded like any POD object, without any chance for unwanted side effects. For clarity, I have already implemented and tested this and everything works as expected.

You cannot use bitwise copy to implement move semantics. That just doesn't work.

It probably depends on what you mean by 'move semantics' and what you mean by 'implement'. What I'm sure of, is that my library can (unintrusively) simulate move constructors, move destructors and the returning of rvalue references from functions. Of course, it doesn't use *only* bitwise copies for that purpose and the type involved needs to be default-constructible. Why do you think it just cannot work? Note that I'm not claiming to deliver a complete library for move semantics -- to the contrary. The underlying type library doesn't predate on Boost.Move; I only think the underlying type library could be useful in the implementation of Boost.Move. For a more thorough discussion please refer to the lecture notes of Alexander Stepanov. He explains these things much better than I could do. :-) -Julian http://www.stepanovpapers.com/notes.pdf

TONGARI wrote:

Do you have codes? Something that just works may not be guaranteed to work...

Very true. I have a zip archive on dropbox: http://dl.dropbox.com/u/3512486/underlying.zip (7 kB) It's all quite immature and it would need rigorous boostification to eventually become a candidate for a review, but the implementation works and I believe it to be without errors (whether conceptual or practical). My own template metaprogramming solution for the underlying_type might be replaced by boost::aligned_storage. Thanks to Mathias Gaunard for bringing it to my attention.

...

It probably depends on what you mean by 'move semantics' and what you mean by 'implement'. What I'm sure of, is that my library can (unintrusively) simulate move constructors, move destructors and the returning of rvalue references from functions. Of course, it doesn't use *only* bitwise copies for that purpose and the type involved needs to be default-constructible.

What type needs to be default-constructible? Something like underlying_type_traits<T>::underlying_type or T itself?

T itself.

On Sat, Aug 20, 2011 at 6:28 PM, Mathias Gaunard <mathias.gaunard@ens-lyon.org> wrote:

You cannot use bitwise copy to implement move semantics. That just doesn't work.

Hmm, why not? What breaks if you do a bitwise swap? Olaf

Marshall Clow wrote:

On Aug 20, 2011, at 10:45 AM, Olaf van der Spek wrote:

...

On Sat, Aug 20, 2011 at 6:28 PM, Mathias Gaunard <mathias.gaunard@ens-lyon.org> wrote:

...

You cannot use bitwise copy to implement move semantics. That just doesn't work.

Hmm, why not? What breaks if you do a bitwise swap?

Consider a type that looks contains a pointer to one of its member vars.

struct Foo { char *curPos; char buffer [ 8 ]; Foo () : curPos (buffer+4) {} };

Foo a, b;

Let's assume that a is at 0x1000, and b is at 0x2000 (and four byte pointers)

0x1000: 00001008 0x1004: aaaaaaaaa 0x1008: bbbbbbbb

0x2000: 00002008 0x2004: cccccccccc 0x2008: dddddddd

Now we do a (bitwise) swap of a and b:

0x1000: 00002008 0x1004: cccccccccc 0x1008: dddddddd

0x2000: 00001008 0x2004: aaaaaaaaa 0x2008: bbbbbbbb

a's pointer now points into b's buffer.

I see. I'll have to relax my claim that the swap algorithm will work for *any* type. Authors of such a class would have to be warned that they can't use the swap algorithm which applies move_raw. I can think of one other case in which it doesn't work: when the object contains a pointer to something that points back to the object. Though I don't know why someone would want to do that.

El 20/08/2011 20:41, Julian Gonggrijp escribió:

I can think of one other case in which it doesn't work: when the object contains a pointer to something that points back to the object. Though I don't know why someone would want to do that.

It's the typical implementation of a linked list ;-) Best, Ion

On 20.08.2011, at 19:45, Olaf van der Spek wrote:

On Sat, Aug 20, 2011 at 6:28 PM, Mathias Gaunard <mathias.gaunard@ens-lyon.org> wrote:

...

You cannot use bitwise copy to implement move semantics. That just doesn't work.

Hmm, why not? What breaks if you do a bitwise swap?

To begin with, the standard. It disallows this kind of thing, period. No matter that "it works in practice" or anything like that, it's undefined behavior to memcpy over a non-pod type's bytes. I think it's a bad idea to offer an easy way to do this in a Boost library. I imagine, for example, that some implementations of virtual inheritance (that don't store offsets to the vbases in the vtable, but instead store a pointer directly in the object) would yield very interesting results. Also, a slicing swap using this technique would be even more disastrous than usual for anything with a vtable. Concerning internal pointers, something that would be high at risk would be a std::string with SBO that stores the end pointer. Sebastian

Dear all, Thank you for your reactions. I'm glad that so many of you took the effort to think about my proposal. I think the set of types with which bitwise move_raw will yield undefined behaviour can be sharply defined: those types for which the validity of the value depends on the memory address of the object. This is a much more important problem than I thought at first and I stand corrected. Sebastian Redl rightly pointed out that it is dangerous to make the bitwise approach easily accessible from the Boost library. This is especially true if the technique is presented as a 'catch-all', like I did in my first email. However, as Vicente Botet (and Alexander Stepanov) pointed out, there are still valid use cases for the bitwise move_raw mechanism. In fact, that a technique may yield undefined behaviour is not a reason to omit the technique per se; we all know that deleting a pointer twice is unwise. While some of our tools are very safe, it's not unreasonable (or uncommon) to have a tool with known pitfalls. There is a solution for the set of types for which the bitwise mechanism doesn't work: their implementers can override underlying_type_traits and move_raw. In that case there is still an advantage to using the underlying type approach; versions of algorithms other than swap such as rotate, partition and random_permute which are also implemented with move_raw will automatically benefit from the overridden templates. In the current situation the same effect could only be achieved by overriding each of these algorithms for each expensively-copyable type (not to mention the noncopyable types). Another reason to still encapsulate this technique into a library is that it is already used, presumably at least in some cases for valid reasons. Therefore I would like to ask you to reconsider the potential value of this library, under the condition that the following be changed: 1. the library is presented with a big warning sign which indicates its pitfalls; 2. the claims about the library's generality are more modest; 3. (optionally) the library is shipped with more implentations of value-permuting algorithms which take advantage of move_raw, such as rotate, partition and random_permute. Mathias Gaunard wrote:

There is no such thing as an underlying type.

It's impossible to realise in current C++, but conceptually it exists. To be honest I think a built-in underlying type function (and real type functions in general) would make a very interesting addition to C++.

Also I assume move_raw here is memcpy. If it isn't, you have strict aliasing problems as well.

In my current implementation move_raw is the compiler_generated POD assignment (the 'overlying type' is reinterpret_cast to the underlying type to enable this). This might or might not be the same as memcpy (I have no idea about this). I might want to change the implementation to memcpy; could you give me a quick explanation of strict aliasing problems and how they come into being if I don't use memcpy? Best wishes, -Julian

Mathias Gaunard wrote:

On 08/21/2011 09:23 PM, Julian Gonggrijp wrote:

...

However, as Vicente Botet (and Alexander Stepanov) pointed out, there are still valid use cases for the bitwise move_raw mechanism.

Care to point out one that wouldn't be better handled by move constructors?

Any case where the object to move a value into has already been constructed?

The layout of non-PODs is completely implementation-defined. Therefore there couldn't be anything meaningful for "underlying type". All it could be is a sequence of bytes of a certain size with a certain alignment.

The layout may be implementation-dependent but the semantics is not. Since underlying types are defined by their semantics and not by their implementation, I don't see how any implementation issue could affect their existential status.

...

In my current implementation move_raw is the compiler_generated POD assignment (the 'overlying type' is reinterpret_cast to the underlying type to enable this).

Right, this is what I suspected. Your code is therefore invalid, and may very well break when you enable optimizations (or not, depending on what the compiler chooses to do).

Code can be fixed. Thank you for the explanation of the strict aliasing problem.

Mathias Gaunard wrote:

On 08/22/2011 12:53 AM, Julian Gonggrijp wrote:

...

Mathias Gaunard wrote:

...

On 08/21/2011 09:23 PM, Julian Gonggrijp wrote:

...

However, as Vicente Botet (and Alexander Stepanov) pointed out, there are still valid use cases for the bitwise move_raw mechanism.

Care to point out one that wouldn't be better handled by move constructors?

Any case where the object to move a value into has already been constructed?

Well, there is also move assignment.

... which differs from move_raw only in the sense that move assignment guarantees that the source is left in a valid state while move_raw does not. The latter has an obvious potential for being more efficient. Note that move_raw is not inherently required to operate in a bitwise fashion; the bitwise approach is only a default solution to make raw moves available to types which don't define their own raw move.

...

...

The layout of non-PODs is completely implementation-defined. Therefore there couldn't be anything meaningful for "underlying type". All it could be is a sequence of bytes of a certain size with a certain alignment.

The layout may be implementation-dependent but the semantics is not. Since underlying types are defined by their semantics and not by their implementation, I don't see how any implementation issue could affect their existential status.

Data has layout, code has semantics. What you call the "underlying type" is just data, so I don't see how it could have any semantics.

Maybe you mean a POD type that's allowed to alias the original type? The closest thing to this is a union that contains both the POD and the original type, which is possible in C++0x.

The underlying type is the solution to the fact that move_raw does not guarantee the source to be left in a valid state. Because of that it is defined to be a POD type which can store the state of its overlying type. As such, it is not "just data"; it has a very clear, semantic relation with its overlying type. Again, my proposal is just a default solution to fill in for types which don't specify their own underlying type. Perhaps some formal language can illustrate the semantics of move_raw and the underlying type: (semantics of copy assignment, quoted from Alexander Stepanov) assert(b == c); a = b; assert(a == b && b == c) (weaker semantics of move assignment, adapted from Alexander Stepanov) assert(b == c && &b != &c); move(b, a); assert(a == c); assert(valid(b)); (still weaker semantics of move_raw, adapted from Alexander Stepanov) assert(b == c && &b != &c); move(b, a); assert(a == c); UNDERLYING_TYPE(T) is a POD type such that the following code is valid: move_raw(a, u); move_raw(u, a); (where a, b, c are instances of some copyable or moveable type and u is an instance of the underlying type of a.)

Eric Niebler wrote:

[...] However, I might prefer a more conservative approach whereby users must opt-in to the memcpy implementation instead of making it the default.

In fact I arrived at this same conclusion after I realised the bitwise approach was not as general as I thought. The library documentation should contain some lines like the following in its introduction: "In the general case, the user of this library will provide template specializations of underlying_type_traits and move_raw. Their type can then take advantage of algorithms that use the move_raw mechanism. As a special case, if you are sure that your type does not depend on the memory location of an object for the validity of its value (see notes below), you can opt-in for the included bitwise implementation. In that case you get move_raw and the underlying type basically for free." After which the "notes below" would provide a thorough explanation on how to recognize problematic types. Nevin Liber wrote:

How often is this thing needed? The only times you need this is when the compiler generated move constructor/assignment operators either are deleted or are doing the wrong thing. Is that really the time you don't want people thinking about how to correctly write swap (or better, just write the correct move constructor and assignment operator).

How about compilers that don't generate move constructors and move assignments at all because they don't support them? And what about types for which move_raw is more efficient than source-validity- preserving move (i.e. any type with a nontrivial default constructor)?

Even examining the implementation for all your member variables isn't enough. The boost::function which holds a boost::bind(..., this, ...) where the function object is stored inside the boost::function object itself may now exhibit different semantics than when the function object it is holding is in the heap. Ugh.

Users should simply be warned that if their type has member data that were implemented by a third party and which are initialized with a pointer to (a part of) the main object, they should assume their type to depend on the object's memory location for its validity.

Way back when, C++ did bitwise copying for the compiler generated copy operations, and was changed to member wise copying for good reason. I really don't want to go back to that world.

Let me reassure you that move_raw is not inherently about bitwise copying; you can do exactly the same with memberwise copying but that requires the author of the type to provide their own implementation.

The problem is, you are adding in a dependency on the *implementation*, not the interface of objects. Consider:

struct W { X x; Y y; Z z; };

1. What are the requirements on implementations of X, Y and Z? Is trivially copyable enough? How about trivially copyable and isn't moveable (unless you want to second guess the move constructor)? Of course, if it is trivially copyable and not moveable, there is probably a reason...

The requirement is that it would be meaningful for W to be moveable, and hence the same must apply to X, Y an Z. I'm assuming that users are not interested in move_raw if value-permuting algorithms like swap make no sense for their type. Note that copying is a special case of moving; if copying makes sense for a type and the type is mutable, then move_raw also makes sense. I don't see how a type could be mutable and trivially copyable but not moveable, except for a sheer lack of implementation of move operators.

2.. How are you going to enforce that?

I don't feel obliged to enforce this. If users insist on trying to move around values which are immutable or non-movable, they have my blessing. Sebastian Redl wrote:

On 21.08.2011 21:23, Julian Gonggrijp wrote:

...

Dear all,

I think the set of types with which bitwise move_raw will yield undefined behaviour can be sharply defined: The standard already does. Undefined behavior is a notion of the standard, not of a particular implementation. The standard says that this technique works only for PODs (trivially copyable types in 0x), nothing else.

Doesn't the standard say that bitwise copying of non-PODs is undefined behaviour /because there are cases where bitwise copying will give you an invalid result/? Have we not identified the cases for which an invalid result will be obtained? Can we therefore not maintain -- making use of the semantical definition of move_raw and restricting ourselves to the set of unproblematic types -- that bitwise copying is a safe implementation of move_raw even though in a very strict juridical sense it may be undefined behaviour?

...

...

There is no such thing as an underlying type. It's impossible to realise in current C++, but conceptually it exists.

Conceptually, if you think of classes as "aggregates and then some", there is the underlying aggregate.

I'm not thinking of classes in that way. The underlying type is something different from an "underlying aggregate" (although I realise I have given that impression in my first email; my apologies). Instead, the underlying type is defined by its semantic relation to the 'overlying type' as I have also stated in my reply to Mathias Gaunard (http://lists.boost.org/Archives/boost/2011/08/184913.php): The underlying type of T is a POD which can store the state of an instance of T. So far, it seems that those who have read Stepanov's paper are more positive about the possible value of my proposal than those who didn't read it. This seems to confirm that Stepanov is still better at explaining the value of move_raw than I am. Therefore I invite those who haven't read the paper yet to still do so. Only lectures 4 and 5 are required; it's only 11 pages with some trailing source code that you can skip. It's a very enjoyable read and I almost dare to promise you that you'll want to read the rest of the paper as well. :-) The URL: http://www.stepanovpapers.com/notes.pdf (If you happen to find something inside the paper that was missing in my own argumentation so far, please let me know; such feedback would be invaluable for future documentation of an underlying type library.) -Julian

On Aug 22, 2011, at 5:55 AM, Sebastian Redl wrote:

On 22.08.2011 13:04, Julian Gonggrijp wrote:

...

Have we not identified the cases for which an invalid result will be obtained? Can we therefore not maintain -- making use of the semantical definition of move_raw and restricting ourselves to the set of unproblematic types -- that bitwise copying is a safe implementation of move_raw even though in a very strict juridical sense it may be undefined behaviour?

Absolutely not. http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html Undefined behavior isn't just about "a very strict juridical sense" of things. Compilers are allowed to assume that UB doesn't happen. If you memcpy over a non-POD, the compiler is allowed to assume the whole branch containing the memcpy is dead code - it cannot ever be reached, because reaching it would invoke UB. Let's say you have this:

if (x != 42) { memcpy(&nonpod, &source, size); } else { other_code(); } std::cout << x << std::endl;

The behavior of the memcpy is undefined. As such, the compiler can generate any code it wants for this branch - like the code of the second branch, thus eliminating the branching entirely. But not only that. In fact, because the compiler will assume that the program is valid, and entering the memcpy branch would invoke UB, it can deduce that x cannot possibly be anything but 42! That is, the std::cout could output "42" even if you set x to something other than 42, because the optimizer replaced all occurrences of x with the constant 42.

Now, I don't know any compiler that is actually that strict, especially with memcpy, but my point is that *there is no such thing as benign undefined behavior*.

I do (and it's gcc) Consider the following code: void do_something ( int *foo ) { log ( "do_something ( %d )", *foo ); if ( foo == NULL ) { // #1 block of code } else { // #2 block of code } } Under higher optimization levels (-02 and above), gcc will not generate code for the test for NULL (and the associated block #1). It will generate code that looks like this instead: void do_something ( int *foo ) { log ( "do_something ( %d )", *foo ); // #2 block of code } This behavior is enabled by default, and can be disabled with the -fno-delete-null-pointer-checks option. The reasoning behind this (as far as I can tell) is that: * The program indirected the pointer foo on the first line of do_something. * If that pointer is NULL, then the behavior of the program is undefined. ==> Therefore, we can assume that the pointer is != NULL, and omit the test. -- Marshall Marshall Clow Idio Software <mailto:mclow.lists@gmail.com> A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait). -- Yu Suzuki

On 22/08/11 16:20, Julian Gonggrijp wrote:

Touché! I'll have to accept that the bitwise approach is no solution for any type at all. Could you quote the lines from the standard in which memcpy over non-PODs is deemed undefined, just in order for me to know the exact wording?

Well, I can't find it saying that explicitly; indeed there are hardly any mentions on memcpy in the standard at all, but here's a relevant bit for C++0x, from N3290 [basic.types] (3.9) p3: For any trivially copyable type T, if two pointers to T point to distinct T objects obj1 and obj2, where neither obj1 nor obj2 is a base-class subobject, if the underlying bytes (1.7) making up obj1 are copied into obj2,41 obj2 shall subsequently hold the same value as obj1. [ Example: T* t1p; T* t2p; // provided that t2p points to an initialized object ... std::memcpy(t1p, t2p, sizeof(T)); // at this point, every subobject of trivially copyable type in *t1p contains // the same value as the corresponding subobject in *t2p — end example ] John Bytheway

Dear all, Hereby I propose the following additions to Boost. I also volunteer to (help to) implement these additions. I. Default templates for underlying_type_traits and move_raw. II. Implementations of the value-permuting STL algorithms, making use of move_raw. III. Template specializations of underlying_type_traits and move_raw for the STL containers. IV. (if deemed necessary) Matching concepts. Part I. may reside in a Utility header, part II. could be a separate library, part III. should probably be an addition to Boost.Containers, and part IV. could either be an addition to Boost.ConceptCheck or live in the same Utility header as part I. There is also an interesting option which directly involves Boost.Move. I'll discuss this option in more detail under part I. below. Before I discuss each part in more detail, a quick review of the rationale for raw move. There are (at least) three possible operations for having a target object acquire the value of a source object, here presented from the strongest semantics to the weakest: - Copy assignment: the source is guaranteed to be left unchanged. - Move assignment: the source is guaranteed to be left in a valid state. - Raw move: nothing is guaranteed about the source, except that it will be valid again when another value has been raw moved into it. Because of the progressively weaker semantics these operations also have an increasing potential for efficiency. Since raw move may leave objects in an invalid state, in general a chain of raw moves has to begin and end with a POD object. The underlying type of T is hence defined as the POD that can store and restore the state of T instances through raw moves. PART I. I think the default templates header should look like this: template <class T> struct underlying_type_traits { typedef T type; }; #define UNDERLYING_TYPE(T) underlying_type_traits< T >::type template <class T> void move_raw (T& source, T& target) { target = source; } template <class T> void move_raw (T& source, typename UNDERLYING_TYPE(T)& target) { target = source; } template <class T> void move_raw (typename UNDERLYING_TYPE(T)& source, T& target) { target = source; } // Not shown: partial specializations for arrays, like in Boost.Swap. // Possible refinement: partial specializations that disable // compilation for const types. There are many good reasons to default to type identity and copy assignment: 1. it is optimal for PODs; 2. it works and is safe for copyable non-PODs; 3. from 1. and 2.: the algorithms from part II. are automatically guaranteed to work for all types that can currently use the copy- based counterparts from the STL; 4. on top of 3., all algorithms from part II. are guaranteed to be always at least as efficient as their copy-based counterparts; 5. from 3. and 4.: raw_move::swap can directly replace std::swap as the default fallback for Boost.Swap, without drawbacks; 6. there is nothing to discourage programmers from implementing new algorithms with raw moves, since they'll get the copy-based variant of their algorithm for free; 7. from 2: authors of non-POD types are motivated but not required to provide template specializations. The interesting alternative is to use Boost.Move's move assignment as the default implementation for move_raw. This would further improve some of the benefits mentioned above. There are however some concerns that need to be clarified before we can make a choice: - Can a raw move framework that uses Boost.Move as a backbone be as general as the copy-based variant? Most likely, this is true if and only if Boost.Move provides copying as a fallback for types that are not move-aware. - What about exception safety? - What other potential obstacles are there? PART II. The following algorithms from the STL should be re-implemented with raw moves: swap, iter_swap, swap_ranges, reverse, rotate, random_shuffle, partition, stable_partition, sort, stable_sort, partial_sort, inplace_merge, push_heap, pop_heap, make_heap, sort_heap, next_permutation, prev_permutation. Of course, new algorithms can be provided as well. An example: move_raw_ranges, the raw counterpart of std::copy. PART III. Ideally move_raw and the underlying type should be specialized for every STL container. This requires knowledge of the implementation details, as well as the addition of matching friend declarations in each container class template. In other words, it can only be done with STL containers that are shipped with Boost. Boost.Containers seems to be the ideal substrate, since one of its aims is to provide 'new advanced features'. It is also the only option, as it seems like a no-go to provide two alternative implementations of the STL containers. More opinions on this matter would be much appreciated. PART IV. I'm completely open to the question of what should be done with regard to raw move-related concepts. It might also partially depend on whether copy or move assignment is used as the default implementation for move_raw. There is however an observation that I want to share: the (abstract) set of raw-movable types coincides exactly with the set of 'normally- movable' types. That is, if it makes sense for type T to have move assignment then it also makes sense to have raw_move, and if it doesn't make sense for T to have move assignment then move_raw also doesn't make sense. In other words, although the use cases for move assignment and raw move are not the same, their requirements on the type are the same in principle. Fitness of a particular type for usage with move_raw should therefore ideally be tested using the same concept check as its fitness for usage with move assignment (this is probably also an argument in favour of using move assignment as the default backbone). I look forward to your feedback. :-) -Julian

Christopher Jefferson wrote:

Can you first of all give a good example (with source) of where using move_raw would out-perform move assignment / constructors from C++0x, particularly in any standard library function (random_shuffle has a fairly small implementation for example). I don't really see how it will help that much.

There is a very simple reason why move_raw will outperform move assignment for any non-POD type: move assignment = move_raw + fixing up the source object , where 'fixing up the source object' is a cheap default constructor in the best case. In that case move_raw is likely to be cheap as well, which means that move assignment takes about twice as much work as move_raw. Since the implementation of an algorithm with move_raw contains exactly the same steps as when it is implemented with move assigment, except that all move assignments are replaced by raw moves, the implementation with raw moves will always perform strictly fewer operations than the move assignment-based implementation for non-POD types. An excellent explanation is provided by Alexander Stepanov: http://www.stepanovpapers.com/notes.pdf (lectures 4 and 5). For some historical background you may also want to refer to the 'mother thread' of my proposal ('[interest] underlying type library'), in which the efficiency benefits of move_raw have already been discussed. The following post is of particular interest: http://lists.boost.org/Archives/boost/2011/08/184933.php The entire thread starts here (though I don't recommend reading all of it): http://lists.boost.org/Archives/boost/2011/08/184872.php (note that the bitwise approach has been abandoned in the current proposal). HTH, Julian

Christopher Jefferson wrote:

Simple reasons can be misleading. Are you sure the gain is substantial enough?

No, to be honest I'm not sure. I'll write a benchmark. However, I don't really see why you would want to include operations in your code of which you know beforehand that they schould be optimized away by the compiler. Part of the reason to adopt move assigments was exactly that: we don't want to insert operations in our code of which we know beforehand we don't want them executed.

As well as discussing, has anyone else come up with good benchmarks (I couldn't find any in the thread you referred to).

Not that I know of. -Julian

El 23/08/2011 17:17, Christopher Jefferson escribió:

When moving was originally discussed, things like 'destructive' and 'raw' moves were discussed, but it was decided in the end they were too dangerous, without proving substantial benefits. For example, you can rearrange a list of std::vectors with memcpy, but if you get half way through and an exception is thrown and you end up with the same vector left in two places in memory, horrible things will happen as they will refer to the same memory block.

IMHO, destructive move should be required always to be no-throw. Best, Ion

Dave Abrahams wrote:

Destructive move is practically impossible to manage regardless of exceptions:

void f() { SomeType x;

if (some_condition) { something_that_moves(x) } else { x.foo() } // Do we call x's destructor? }

After your email that explained the practical equivalence of destructive moves with raw moves, I find this example illuminating because it shows a problem that doesn't apply to raw moves. Suppose that the example concerns raw moves instead of destructive moves. In that case there is no choice at the end of f(): x' destructor will be called regardless of the truth value of some_condition. Furthermore we can assume that the code is unproblematic because we trust the author of something_that_moves. Either: something_that_moves(x) returns with x being in an invalid state, in which case the author has violated the rule that chains of raw moves bust be closed within the same scope; Or: something_that_moves(x) properly closes its internal chain of raw moves, in which case x is in a destructible state after function exit and there is no problem. So the conceptual difference is that in destructive moves, it is the compiler's responsibility to maintain integrity, while in raw moves it is the programmer's responsibility. For programmers there are clear, strict rules* for avoiding invalid destruction of raw-moved objects. If we treat raw moves as if they are the compiler's responsibility instead, they seem intractible. -Julian * 1) Once a chain of raw moves starts, in has to finish within the same scope; 2) all operations between the start and the end of a chain of raw moves must be non-throwing. I don't think there are more rules, but there might be.

Nevin Liber wrote:

In the C++11 move case, the moved-from object itself doesn't know if it is about to be destroyed or reused, so it has to be put in a state where either can happen.

Excuse me, but that doesn't seem logical. You are saying that since the object doesn't know what is going to happen, the programmer has to prepare it for both scenarios. But in this case the programmer knows what is going to happen (assuming that care is taken to ensure exception-safety). So it can just as well prepare the object only for the scenario that is really going to happen.

The compiler, of course, knows, and I want the optimizer to take advantage of this.

[As a parallel: I still write a correct copy constructor for a copyable object even if all my uses involve RVO and it never gets called; as I'd rather have correct but slower code than incorrect code if a non-RVO case happens to pop up.]

You are giving a valid reason for implementing a copy constructor, but the argument is orthogonal to the point I was trying to make. Suppose you have not only copy constructors at your disposal but also a tool that is guaranteed to do RVO (e.g. something along the line of rvalue references). Then surely every time you use a function that returns a local variable you are going to use the RVO-only tool and not the most-of-the-time-optimized-into-RVO copy constructor?

raw_move is a user optimization over C++11 moves in that it assumes the moved-from object is going to be reused; destruction would be very bad, which is why there is all this worry over exception safety.

So far I understood. What I didn't see was why an exception would be bad if the moved-from object is actually in a valid state because behind the scenes move_raw is implemented as a copy. Eric Niebler has enlightened me: it's not bad for the object itself, but it might be a disaster for another object which has undergone a real raw move before the exception happened. -Julian

On 23 August 2011 13:13, Julian Gonggrijp <j.gonggrijp@gmail.com> wrote:

Nevin Liber wrote:

...

In the C++11 move case, the moved-from object itself doesn't know if it is about to be destroyed or reused, so it has to be put in a state where either can happen.

Excuse me, but that doesn't seem logical. You are saying that since the object doesn't know what is going to happen, the programmer has to prepare it for both scenarios.

C++11 move semantics have a requirement that the source object is left in a valid but unspecified state. Given that T is a MoveConstructible and MoveAssignable type: T a(T_Factory()); T b(T_Factory()); // ... a = std::move(b); 1. At this point, what operations can you perform on a? 2. At this point, what operations can you perform on b? a still has to be destructible and assignable, as a cannot possibly know how it is going to be used past this point. Any other operations on a would have to be documented (for instance, there are stronger requirements on move semantics for standard library types). b has no restrictions on the operations that can be called. My question is, given: T c(T_Factory()); T d(T_Factory()); // ... move_raw(c, d); 3. At this point, what operations can you perform on c? 4. At this point, what operations can you perform on d? --  Nevin ":-)" Liber  <mailto:nevin@eviloverlord.com>  (847) 691-1404

On 8/23/2011 9:44 AM, Julian Gonggrijp wrote:

Christopher Jefferson wrote:

...

Can you first of all give a good example (with source) of where using move_raw would out-perform move assignment / constructors from C++0x, particularly in any standard library function (random_shuffle has a fairly small implementation for example). I don't really see how it will help that much.

There is a very simple reason why move_raw will outperform move assignment for any non-POD type: <snip>

Julian, you'll get more traction if you write and publish a benchmark program that demonstrates the speed-up on some popular compilers. You need to prove that even a smart compiler doesn't optimize away the extra overhead. -- Eric Niebler BoostPro Computing http://www.boostpro.com

On Tue, Aug 23, 2011 at 9:44 AM, Julian Gonggrijp <j.gonggrijp@gmail.com> wrote:

Christopher Jefferson wrote:

...

Can you first of all give a good example (with source) of where using move_raw would out-perform move assignment / constructors from C++0x, particularly in any standard library function (random_shuffle has a fairly small implementation for example). I don't really see how it will help that much.

There is a very simple reason why move_raw will outperform move assignment for any non-POD type:

move assignment = move_raw + fixing up the source object ,

raw_move assumes that later the algorithm will raw_move back into the temporarily invalid source object. So sooner or later we write to that memory. Depending on caching scenarios, it might actually be faster to write to that memory *sooner*. It is very hard to tell - it depends on the amount of data, the locality of the data, the type of CPU/memory/bus/architecture, etc etc etc. But I wouldn't be that surprised if raw_move offered no speed up in most cases. Tony

Gottlob Frege wrote:

On Tue, Aug 23, 2011 at 11:12 PM, Gottlob Frege <gottlobfrege@gmail.com> wrote:

...

raw_move assumes that later the algorithm will raw_move back into the temporarily invalid source object. So sooner or later we write to that memory. Depending on caching scenarios, it might actually be faster to write to that memory *sooner*.

We can write sooner, but that doesn't change anything to our need to write later, does it? So either we write soon with zeros and later with the new value, or we write only later with the new value. Or are you saying that the compiler might be able to predict what value we're going to move later and move that value sooner? Or was your point maybe that reading the source object of a raw move might not be enough to promote it in the cache, and that writing it with zeros instead will therefore improve the speed of retrieval when the object has become the target of a new raw move?

...

[...] But I wouldn't be that surprised if raw_move offered no speed up in most cases.

To be honest, in the meanwhile I wouldn't be surprised about that anymore either. Christopher Jefferson already argued quite convincingly that there might be very little to gain. I'm still going to write a benchmark, but I'm prepared for the possibility that it will be no more than a benchmarking exercise.

Particularly if you are still calling raw_move one container element at a time. If you really want to speed things up, you need to memcpy a whole block of objects at once. ie an array/vector of pods. If 100 elements is 100 memcpy calls, I'm not sure you will get much benefit. If we can get 100 elements to compile into 1 memcpy call, there is a chance at a speed up. A good memcpy is hand optimized for the given architecture to prime the cache as it moves along, etc. That only works if it is one big call.

Yes, I agree that this is a much more powerful way to speed up a program. -Julian

On 8/23/2011 8:06 AM, Julian Gonggrijp wrote: <snip>

PART I. I think the default templates header should look like this:

template <class T> struct underlying_type_traits { typedef T type; };

Only if T is a POD, so BOOST_MPL_ASSERT((is_pod<T>)) would be a useful addition here.

#define UNDERLYING_TYPE(T) underlying_type_traits< T >::type

template <class T> void move_raw (T& source, T& target) { target = source; }

template <class T> void move_raw (T& source, typename UNDERLYING_TYPE(T)& target) { target = source; }

template <class T> void move_raw (typename UNDERLYING_TYPE(T)& source, T& target) { target = source; }

Yikes, no. T's copy constructor can throw. This should be a move, and then only if T's move assign cannot throw. Otherwise, move_raw should probably be undefined. You may decide to provide an easy way for users to opt-in for a memcpy based solution, but that option should only be available only on compilers for which memcpy-ing non-PODs is empirically known to work. And there should be a warning about the non-portability about doing that.

// Not shown: partial specializations for arrays, like in Boost.Swap. // Possible refinement: partial specializations that disable // compilation for const types.

There are many good reasons to default to type identity and copy assignment:

1. it is optimal for PODs; 2. it works and is safe for copyable non-PODs;

No, it's not safe.

3. from 1. and 2.: the algorithms from part II. are automatically guaranteed to work for all types that can currently use the copy- based counterparts from the STL; 4. on top of 3., all algorithms from part II. are guaranteed to be always at least as efficient as their copy-based counterparts; 5. from 3. and 4.: raw_move::swap can directly replace std::swap as

What's raw_move::swap? -- Eric Niebler BoostPro Computing http://www.boostpro.com

On 8/23/2011 11:35 AM, Julian Gonggrijp wrote:

Eric Niebler wrote:

...

On 8/23/2011 8:06 AM, Julian Gonggrijp wrote: <snip>

...

[...] template <class T> void move_raw (typename UNDERLYING_TYPE(T)& source, T& target) { target = source; }

Yikes, no. T's copy constructor can throw. This should be a move, and then only if T's move assign cannot throw. Otherwise, move_raw should probably be undefined.

If move_raw is implemented as a copy, it doesn't really matter if the copy throws because the source object is left in a valid state, right?

No. Imagine: UNDERLYING_TYPE(X) tmp1; UNDERLYING_TYPE(Y) tmp2; move_raw(x, tmp1); // 1 move_raw(y, tmp2); // 2 move_raw(tmp2, y); // 3 move_raw(tmp1, x); // 4 Imagine that X has a move_raw that leaves its source in an invalid state and that Y has a move_raw that can throw. Now also imagine line 2 throws. Oops.

I mean, with the copy-based swap we usually also don't worry about the possibility that one of the copies might throw...

Yes, we do. Read about noexcept.

...

You may decide to provide an easy way for users to opt-in for a memcpy based solution, but that option should only be available only on compilers for which memcpy-ing non-PODs is empirically known to work. And there should be a warning about the non-portability about doing that.

If you are right and using copy as a fallback for raw moves is not an option, it means a significant loss of generality.

Like I said, you need to solve the exception safety issues. Look into noexcept; there may be relief there. -- Eric Niebler BoostPro Computing http://www.boostpro.com

Le 22/08/11 17:23, Eric Niebler a écrit :

(Julian, I'm having a hard time following the discussion because you're replying to multiple people in a single email. Those of us with threaded readers would prefer if you replied to us individually.)

On 8/22/2011 7:04 AM, Julian Gonggrijp wrote:

...

Eric Niebler wrote:

...

[...] However, I might prefer a more conservative approach whereby users must opt-in to the memcpy implementation instead of making it the default. In fact I arrived at this same conclusion after I realised the bitwise approach was not as general as I thought. Thought: the obvious default implementation should be to simply call move, but this gets complicated because move operations can throw. Then during unwinding you'll try to destruct an object that isn't in a destructible state. You would need to find a way to address the exception-safety issues. Perhaps the new noexcept keyword could help here.

Hi, I agree with you Eric that the default implementation of move_raw the library shouldn't promote undefined behavior (memcpy). Instead it should use move when the type is movable, and copy/assign when copyable/assignable. Up to the end user to use memcpy for its own types when she considers that it works for him. Julian, I don't know if you have take a look at the under review Boost.Conversion library. The move_raw function can follows the same design as the conversion::assign_to function. I don't know if the move_raw can be used to move unrelated types, but if this is the case, the issue raised during the Boost.Conversion pre/review, that is, ODR violation promotion will also be present. Maybe you pretend that the move_raw function must be overried only to move from one type to it self and its underlying type, but nothing in the interface prevents from using it to move from unrelated types. In Boost.Enums and Boost.Opaque there is a underlying_type concept that match the one of this proposal. It will be nice if we can add it already on Boost.Utility. The library could define it for POD types as the identity and left the user to provide appropiated instantiations. Best, Vicente

Eric Niebler wrote:

(Julian, I'm having a hard time following the discussion because you're replying to multiple people in a single email. Those of us with threaded readers would prefer if you replied to us individually.)

I'm sorry for the confusion. I'll reply to every email separately from now on. :-)

Thought: the obvious default implementation should be to simply call move, but this gets complicated because move operations can throw. Then during unwinding you'll try to destruct an object that isn't in a destructible state. You would need to find a way to address the exception-safety issues. Perhaps the new noexcept keyword could help here.

Coincidentally I've been thinking along similar lines. Normal copy assignment might be a very interesting fallback option for move_raw as well. I'll use this in my upcoming proposal.

On 21 August 2011 05:10, Vicente J. Botet Escriba <vicente.botet@wanadoo.fr>wrote:

I understand that Boost can not rely on libraries promoting undefined behavior, but sometimes using undefined behavior can be accepted if at the end the function ensures everything is in a state that is consistent.

If you invoke undefined behavior, by definition it is impossible to ensure everything is in a consistent state afterwards. Undefined behavior really means "don't go there". -- Nevin ":-)" Liber <mailto:nevin@eviloverlord.com> (847) 691-1404

On 8/21/2011 5:35 PM, Nevin Liber wrote:

On 21 August 2011 05:10, Vicente J. Botet Escriba <vicente.botet@wanadoo.fr>wrote:

...

I understand that Boost can not rely on libraries promoting undefined behavior, but sometimes using undefined behavior can be accepted if at the end the function ensures everything is in a state that is consistent.

If you invoke undefined behavior, by definition it is impossible to ensure everything is in a consistent state afterwards. Undefined behavior really means "don't go there".

This is the accepted dogma, but having read Stepanov's paper, I think there is value to the technique. However, I might prefer a more conservative approach whereby users must opt-in to the memcpy implementation instead of making it the default. -- Eric Niebler BoostPro Computing http://www.boostpro.com

On 8/22/2011 1:36 AM, Nevin Liber wrote:

On 21 August 2011 21:15, Eric Niebler <eric@boostpro.com> wrote:

...

This is the accepted dogma,

For good reason. These are places that end up getting aggressively optimized, so code that appears to work today suddenly is broken tomorrow when the compiler is revved.

Stepanov argues that things like UNDERLYING_TYPE and move_raw should be part of the Standard Library and guaranteed to work. It could have a home in Boost, too. There is precedent for having code in Boost that is non-compliant -- just under compiler switches. Boost.Typeof is non-compliant. So are parts of Boost.Foreach. And sometimes new compilers come out that break Boost.Foreach and I have to fix the compiler work-arounds. So what? Besides, I think you're getting hung up on the bitwise copy thing. Stepanov is merely making the point that some things can be implemented more efficiently with a move-like operation that makes weaker guarantees than move.

However, I might prefer a more

...

conservative approach whereby users must opt-in to the memcpy implementation instead of making it the default.

How often is this thing needed? The only times you need this is when the compiler generated move constructor/assignment operators either are deleted or are doing the wrong thing.

No. Nevin, at this point its obvious to me you haven't read the paper. Please go read it and then we can talk about the pros and cons. It is needed when implementing an algorithm for which move is *inherently* an inadequate tool for the job because it makes guarantees that are not needed: namely the destructability of the moved-from object. Preserving that invariant is not needed if you will be moving a valid value back into the moved-from object before its lifetime ends. Again, Stepanov does a good job describing all this. Read the paper.

Is that really the time you don't want people thinking about how to correctly write swap (or better, just write the correct move constructor and assignment operator).

Missing the point.

Even examining the implementation for all your member variables isn't enough. The boost::function which holds a boost::bind(..., this, ...) where the function object is stored inside the boost::function object itself may now exhibit different semantics than when the function object it is holding is in the heap. Ugh.

And care would be needed to write the move_raw for such an object. Just as care would be needed to write move contruct/assign and copy construct/assign for that thing.

Way back when, C++ did bitwise copying for the compiler generated copy operations, and was changed to member wise copying for good reason. I really don't want to go back to that world.

Nobody is arguing for that. -- Eric Niebler BoostPro Computing http://www.boostpro.com

On 21 August 2011 21:15, Eric Niebler <eric@boostpro.com> wrote:

However, I might prefer a more conservative approach whereby users must opt-in to the memcpy implementation instead of making it the default.

The problem is, you are adding in a dependency on the *implementation*, not the interface of objects. Consider: struct W { X x; Y y; Z z; }; 1. What are the requirements on implementations of X, Y and Z? Is trivially copyable enough? How about trivially copyable and isn't moveable (unless you want to second guess the move constructor)? Of course, if it is trivially copyable and not moveable, there is probably a reason... 2.. How are you going to enforce that? Maybe you create some type trait with the defaults based upon the requirements you've identified above. Because C++ doesn't have introspection, you still end up having to write code that examines all the member variables to see if they meet that type trait. Do you still think that is easier than writing the move constructor and assignment operator for classes where the compiler generated one is wrong or deleted? -- Nevin ":-)" Liber <mailto:nevin@eviloverlord.com> (847) 691-1404

On 22 August 2011 10:30, Eric Niebler <eric@boostpro.com> wrote:

...

Do you still think that is easier than writing the move constructor and assignment operator for classes where the compiler generated one is wrong or deleted?

I think it fills a different need.

Maybe at this point it would be nice if its proponents came up with a modern (i.e., why this would still be needed in a world with either C++11 or Boost.Move) motivating example or two. The Stepanov paper is a product of its time and no longer as useful for showing why we still need something like this. -- Nevin ":-)" Liber <mailto:nevin@eviloverlord.com> (847) 691-1404

On 22 August 2011 13:06, Vicente J. Botet Escriba <vicente.botet@wanadoo.fr>wrote:

Note that Movable will imply RawMovable if the default implementation uses std::move.

That doesn't seem quite right. Don't the move constructor and move assignment operator have to be noexcept(true) as well for that implication to hold? -- Nevin ":-)" Liber <mailto:nevin@eviloverlord.com> (847) 691-1404

On 8/22/2011 3:50 PM, Ion Gaztañaga wrote:

We still have to explore "destructive move" semantics. We have move semantics. We can even declare a traits like "has_trivial_destructor_after_move" to optimize a bit more vector reallocations once we've moved some value_types (we avoid calling destructors that do nothing useful once moved). Destructive move semantics could be a step further, we need to explore destructive move semantics in containers and algorithms. Some problems with destructive move semantics here:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2002/n1377.htm

Interesting! Thanks for the reference. -- Eric Niebler BoostPro Computing http://www.boostpro.com

on Tue Aug 23 2011, Julian Gonggrijp <j.gonggrijp-AT-gmail.com> wrote:

Ion Gaztañaga wrote:

...

We still have to explore "destructive move" semantics. We have move semantics. We can even declare a traits like "has_trivial_destructor_after_move" to optimize a bit more vector reallocations once we've moved some value_types (we avoid calling destructors that do nothing useful once moved). Destructive move semantics could be a step further, we need to explore destructive move semantics in containers and algorithms. Some problems with destructive move semantics here:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2002/n1377.htm

That's interesting, but after reading that page I think raw_move is not the same as destructive move. The difference: destructive move acts as a destructor and hence makes the source object unavailable for further use.

Well, technically, it makes the source object's storage usable as raw memory.

In move_raw on the other hand, the source object is left in an invalid but non-destructed state which it can only be rescued from by raw moving another value into it (if it is non-POD).

How is an "invalid but non-destructed state" practically different from raw memory? Are you saying I can't default-construct another value of the same type in that memory? -- Dave Abrahams BoostPro Computing http://www.boostpro.com

on Wed Aug 24 2011, Julian Gonggrijp <j.gonggrijp-AT-gmail.com> wrote:

Dave Abrahams wrote:

...

How is an "invalid but non-destructed state" practically different from raw memory? Are you saying I can't default-construct another value of the same type in that memory?

I must admit that you do a good job at making these moves look more similar. :-) And yes, to be fair I must say that you can probably default-construct a new object of the same type in a raw-moved-from object.

But no, they are still not really the same. After a destructive move the source object is in a destructed state (raw memory, as you say), so in principle you should not need to worry about it anymore; i.e. it won't be destructed again at the end of scope.

Do you know how to implement that? (hint: see below)

You're not really expected to store a new value of the moved-from type in the object; if you do want to do so you'll first have to run a constructor again.

The source of a raw move on the other hand is a bomb waiting to explode, because technically speaking it is still storing a value of the moved-from type and it *will* be destructed at the end of scope.

No, it is *not* storing a value. I believe you're saying that the difference is not in the state of the memory, but in what the compiler will try to do with that memory later. That requires you to believe that in general, the compiler can know about the state of a destructively-moved automatic object and avoid destroying it again. But, for all practical purposes, it can't. In general, that requires a bit of storage and a runtime check for each object that might be moved from.

Hence you are forced to give it a new, valid value.

It follows that they also have different use cases. A destructive move seems useful for returning local variables from functions.

But that optimization is almost completely unneeded because of RVO. And when RVO doesn't kick in and a real move is needed, the compiler may be able to detect that it's just fixing up an object that's about to be destroyed.

A raw move on the other hand can only be used if you are reordering values within the same scope.

? I presume that I can do swap(x,y) no matter what x and y's scope are. -- Dave Abrahams BoostPro Computing http://www.boostpro.com

on Wed Aug 24 2011, Julian Gonggrijp <j.gonggrijp-AT-gmail.com> wrote:

So what you are saying is: in practice there is no difference between a raw move and a destructive move. Point taken. But in that case the name 'raw move' seems to cover the semantics much better than 'destructive move'.

Meh. I don't care about the naming much one way or another.

...

...

A raw move on the other hand can only be used if you are reordering values within the same scope.

? I presume that I can do swap(x,y) no matter what x and y's scope are.

Correct. 'Within the same scope' was meant to refer to the reordering, not to the values. That is, once you start a chain of raw moves, you have to close that chain within the same scope in order to provide a validity guarantee to calling clients.

OK, that makes sense.

With hindsight, I should have realised much earlier in this thread that this is also the reason why every operation between the start and the end of a chain of raw moves must be exception-free.

Well, if underlying_type<T> defaults to T and raw_move(x) defaults to move(x), then I suppose we could use this approach to optimize algorithms such as rotate for many types without losing general correctness. It's less clear that algorithms that use swap would benefit, but they might. -- Dave Abrahams BoostPro Computing http://www.boostpro.com