Post-Conditions on Self-Move

UPDATE April 8, 2016 This post has been edited since publication to reflect my evolving understanding. As a result of the issues raised in this post, it’s possible that the committee decides to strengthen the post-conditions on move, so the recommendations made here may evolve further. Stay tuned.

TL;DR: In addition to the usual rule about move operations leaving the source object in a valid but unspecified state, we can add an additional rule:

Self-move assignment should “work” and at the very least leave the object in a valid but unspecified state.

Discussion

What do you think the following code should do?

X x = {/*something*/};
x = std::move(x);

Yes, it’s dumb, but with our alias-happy language, it can happen. So what does the standard say about this? For that we turn to [res.on.arguments]/p1.3 taken from the library introduction (emphasis mine):

If a function argument binds to an rvalue reference parameter, the implementation may assume that this parameter is a unique reference to this argument. […] If a program casts an lvalue to an xvalue while passing that lvalue to a library function (e.g. by calling the function with the argument std::move(x)), the program is effectively asking that function to treat that lvalue as a temporary. The implementation is free to optimize away aliasing checks which might be needed if the argument waswere an lvalue.

(I fixed the grammar mistake because I am a Huge Dork.) The above seems to say that std::swap(x, x) is playing with fire, because std::swap is implemented as follows:

template <class T>
void swap(T& a, T& b) {
  auto x(std::move(a));
  a = std::move(b); // Here be dragons
  b = std::move(x);
}

If a and b refer to the same object, the second line of std::swap does a self-move assign. Blamo! Undefined behavior, right?

Such was what I thought when I first wrote this post until Howard Hinnant drew my attention to the requirements table for the MoveAssignable concept, which says that for the expression t = rv (emphasis mine):

If t and rv do not refer to the same object, t is equivalent to the value of rv before the assignment […] rv’s state is unspecified. [ Note: rv must still meet the requirements of the library component that is using it, whether or not t and rv refer to the same object. […] –end note]

Ah, ha! So here we have it. After a self-move, the object is required to be in a valid-but-unspecified state.

My attention we drawn to this issue during a code review of a change I wanted to make to Folly‘s Function class template. I wanted to change this:

Function& operator=(Function&& that) noexcept {
  if (this != &that) {
    // do the move
  }
  return *this;
}

to this:

Function& operator=(Function&& that) noexcept {
  assert(this != &that);
  // do the move
  return *this;
}

The reason: let’s make moves as fast as possible and take advantage of the fact that Self-Moves Shouldn’t Happen. We assert, fix up the places that get it wrong, and make our programs an iota faster. Right?

Not so fast, said one clued-in reviewer. Self-swaps can happen quite easily in generic algorithms, and they shouldn’t trash the state of the object or the state of the program. This rang true, and so begin my investigation.

A few Google searches later turned up this StackOverflow gem from Howard Hinnant. C++ wonks know Howard Hinnant. He’s the author of libc++, and an old time C++ library developer. (Remember Metrowerks CodeWarrior? No? Get off my lawn.) He also happens to be the person who wrote the proposal to add rvalue references to the language, so you know, Howard’s given this some thought. First Howard says this:

Some will argue that swap(x, x) is a good idea, or just a necessary evil. And this, if the swap goes to the default swap, can cause a self-move-assignment.

I disagree that swap(x, x) is ever a good idea. If found in my own code, I will consider it a performance bug and fix it.

But then in an Update, he backtracks:

I’ve given this issue some more thought, and changed my position somewhat. I now believe that assignment should be tolerant of self assignment, but that the post conditions on copy assignment and move assignment are different:

For copy assignment:

x = y;

one should have a post-condition that the value of y should not be altered. When &x == &y then this postcondition translates into: self copy assignment should have no impact on the value of x.

For move assignment:

x = std::move(y);

one should have a post-condition that y has a valid but unspecified state. When &x == &y then this postcondition translates into: x has a valid but unspecified state. I.e. self move assignment does not have to be a no-op. But it should not crash. This post-condition is consistent with allowing swap(x, x) to just work […]

When Howard Hinnant changes his mind about something having to do with library design, I sit up and take note, because it means that something very deep and subtle is going on. In this case, it means I’ve been writing bad move assignment operators for years.

By Howard’s yardstick — and by the requirements for the MoveAssignable concept in the standard, thanks Howard! — this move assignment operator is wrong:

Function& operator=(Function&& that) noexcept {
  assert(this != &that); // No! Bad C++ programmer!
  // do the move
  return *this;
}

Move assignment operators should accept self-moves and do no evil; indeed for std::swap(f, f) to work it must.

That’s not the same as saying it needs to preserve the object’s value, though, and not preserving the object’s value can be a performance win. It can save a branch, for instance. Here is how I reformulated folly::Function’s move assignment operator[*]:

Function& operator=(Function&& that) noexcept {
  clear_();        // Free all of the resources owned by *this
  moveFrom_(that); // Move that's guts into *this.
  return *this;
}

[*] Well, not exactly, but that’s the gist.

Of note is that clear_() leaves *this in a state such that it is still OK to moveFrom_(*this), which is what happens when that and *this are the same object. In the case of Function, it just so happens that the effect of this code is to put the Function object back into the default-constructed state, obliterating the previous value. The particular final state of the object isn’t important though, so long as it is still valid.

Summary

So, as always we have the rule about moves:

Move operations should leave the source object in a valid but unspecified state.

And to that we can add an additional rule:

Self-moves should do no evil and leave the object in a valid but unspecified state.

If you want to go further and leave the object unmodified, that’s not wrong per se, but it’s not required by the standard as it is today. Changing the value is perfectly OK (Howard and the standard say so!), and doing that might save you some cycles.

TIL

"\e"

22 Replies to “Post-Conditions on Self-Move”

    • … which enshrines in the standard that the guideline I set out in this blog post (self-moves should leave the object in a valid but undefined state) applies to types in the Standard Library, too. Thanks, Casey.

  1. Totally agree – Howard is always right, never wrong.

    And when Howard corrects himself, it just means he was right, and now he is more right.

    (it is very tempting to sign my name as Howard, but for once, humour doesn’t get the final say…)

  2. I learned that self-move-assignment must leave the object in a valid state when I was burned by std::shuffle not working with objects of my type. std::shuffle in every implementation I know of can perform the equivalent of std::swap(x, x). There may be other algorithms that do the same thing. So, de facto, all decent types, including all types in the standard library implementations, already follow this rule.

  3. The standard explicitly states that swap swaps the values referred to by a and b and doesn’t explicitly exclude those values being the same. It seems to me that the only requirement of swap is that when the operation completes a₂ == b₁ and b₂ == a₁. How swap achieves this is implementation defined but an implementation must guarantee it. My reading is that it is not undefined behaviour to call it with two values which are the same. Whether it’s a good idea or not an implementation must support it.

    Taking that to be true it is an implementation of swap that binds an rvalue reference to one of it’s parameters and passes it to a member function of the other without checking that they are the same is the one invoking the undefined behaviour. Whether we like it or not the wording of the swap definition means it has to do an equality comparison to avoid invoking undefined behaviour and be standard compliant.

  4. I saw an interesting observation on the Reddit thread for this post.

    mcmcc said:
    “If [self move is a well-defined operation], and we view move as simply an optimization over copy, then it should assert the same post-conditions as copy.”

    I recall several talks from prominent C++ community members that sold move semantics as a copy-optimization. Why shouldn’t that apply for self-move?

    • It’s a legitimate question. This same question is being discussed right now in relation to the Core Guidelines. Some argue for non-modifying self-move, others for valid-but-unspecified, and there are good reasons on both sides. Interestingly, the problem is not just about self-move. Any time a part is moved (or copied!) into the whole, there is potential for data loss unless the [copy/move]-and-swap idiom is used. This issue could lead to a change in the Standard, in Standard Library implementations, in the Core Guidelines, and books and articles about how to write copy/move assignment operators! I’ll write another blog post once the dust has settled.

  5. What’s the benefit? It does preclude implementing move assignment as destruction followed by in-place construction, which is defined behavior as long as the class has no reference or const members, AFAIK.

      • You can always write a move-assignment operator that works and preserves the value in the case of self-move (or more generally anytime a part is moved into the whole). It comes at the cost of move-constructing a temporary and (nothrow) swapping with it. That can be expensive. The question is: is it OK to avoid making the temporary to optimize the common case if move-assign becomes mutating on self-move? The standard currently says yes, that’s OK. Some are saying no, and they have a point. Stay tuned.

  6. I don’t buy the performance argument for a value-changing self-move assignment. Given the classic use case for move semantics (a class holding a single resource), its assignment operator would probably look something like this:

    
    MyClass& MyClass::operator=(MyClass&& rhs) {
      delete this->resource;
      this->resource = rhs.resource;
      rhs.resource = nullptr;
      return *this;
    }
    

    In contrast, an alias-proof value-preserving implementation could be:

    
    MyClass& MyClass::operator=(MyClass&& rhs) {
      Resource *tmp = rhs.resource;
      rhs.resource = nullptr;
      delete this->resource;
      this->resource = tmp;
      return *this;
    }
    

    All it takes is a single extra assignment.

    • In this case, yes, it only takes one extra assignment. As I’ve learned over the past week or so, this problem (assigning a part into the whole) comes up in many other places and in other guises, and the bulletproof solution is not always cheap. When the dust settles a bit, I hope to write a follow-up post about what we’ve learned and what we’re going to do about it.

    • This solution does not actually save you. If this == std::addressof(rhs), then tmp == this->resource. When you assign from it on line 5, you are invoking implementation-defined behavior by reading from an invalid pointer. See http://eel.is/c++draft/basic.stc#4

      “When the end of the duration of a region of storage is reached, the values of all pointers representing the address of any part of that region of storage become invalid pointer values. Indirection through an invalid pointer value and passing an invalid pointer value to a deallocation function have undefined behavior. Any other use of an invalid pointer value has implementation-defined behavior.”

      “Some implementations might define that copying an invalid pointer value causes a system-generated runtime fault.”

      Unless you are willing to accept this behavior on some platforms (which is to say, you do not support those platforms), I do not believe you can get away without a branch in the value-preserving case. Of course, this also effects your original version, as written. To be safe, your first version should look something like

      delete this->resource;
      this->resource = nullptr;
      this->resource = rhs.resource;
      rhs.resource = nullptr;

      Or, if you want to get fancy

      delete std::exchange(this->resource, nullptr);
      this->resource = std::exchange(rhs.resource, nullptr);

      If we look at the implementation of vector in some standard libraries, clang’s standard library (libc++) does the moral equivalent of this. gcc’s standard library, libstdc++, implements move assignment as constructing an empty temporary and swapping with it, then swapping with rhs, so it is also safe. At first it looks like gcc has avoided a branch, from a straightforward reading of the code, but it is still there in the destructor of the temporary. Note that both implementations have a destructive self-move (it leaves the object in the empty state).

      The code Eric outlined should also be safe, assuming that his clear_ function sets the value of the pointer to something safe before it returns.

      • I don’t think your claim is correct. If this == &rhs, then line 3 sets this->resource to nullptr. Therefore line 4 does not invaldate tmp (it has no effect), and the assignment in line 5 still copies a valid pointer.

  7. Mmh. Not sure I am getting the gist here.

    Motivation: Self-move may – accidentally – happen in generic algorithms.
    Assertion: A modifying self-move is beneficial over a fail-fast self-move.

    It would seem then, that an accidental self-move introduces a silent bug by destroying information (and replacing it with a blank, almost by definition not useful data). As the resulting state is still valid, there will be no indication that anything is wrong.
    … This is much worse than a performance penalty, is it not? An exception or an error flag should be employed.

    (On fuzzy and/or big data I could see the argument that losing the odd value would not meaningfully impact the outcome and may thus be accepted. I do not think this can be treated as the general case, though.)

    Am I missing something?

    • It’s that generic code would accidentally self-swap. The problem is more that some generic algorithms, such as std::shuffle, need an explicit check to avoid it. If the type being passed to the algorithm can handle a self-swap, then the algorithm does not need that “extra” branch.

      That being said, I do not know if any generic algorithms that do not rely on randomness have this property. I can’t think of a sorting algorithm that would cause this, for instance.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.