foonathan::blog()

Thoughts from a C++ library developer.

Thoughts on destructive move

C++11 introduced move semantics. With it, you can encode transfer of ownership and allow to put types in a container where you can’t copy them.

This clearly is powerful.

But the current move system isn’t perfect, there are a couple of issues. There is an arguably cleaner approach: destructive move.

In this post we’ll explore a purely theoretical alternative C++ with destructive move.


Advertisement

C++ move semantics

A constructor that takes an rvalue reference is a move constructor. A move constructor is similar to a copy constructor, it just allows stealing the resource from the other object. The idea is that the other object isn’t used anymore and so the “copy” can change its state.

This is simple enough, however the mechanism has three problems:

1. Move operations are allowed to throw

The move constructor or assignment operator is allowed to throw. Throwing move makes a lot of generic code harder.

Let’s consider the growth operation of std::vector. Pre-C++11 it had to allocate a new bigger buffer, copy the elements over and destroy the old one. But as the copied elements are immediately destroyed afterwards, it is a prime candidate for moving.

However, throwing move ruins that: If the move construction of the ith element failed, some elements are already moved away, and it is not in the same state as before. A rollback isn’t possible either, because that move could fail again!

The solution is to copy the elements when the move constructor is not noexcept. Copy doesn’t modify the original object so if a copy operation fails, the vector is unmodified. But if the move constructor doesn’t throw, they can safely be moved.

This is done by std::move_if_noexcept.

Furthermore, the whole valueless_by_exception() state of std::variant is caused by potentially throwing move: A variant has a buffer where it stores the currently active object. If you want to change a variant so that an object of a different type is active, it has to destroy the current one and move the new one into the buffer. If the move throws, the variant is not in a valid state anymore. And unlike std::vector there is no fallback besides using a bigger buffer that can store two objects, or using heap allocation. So the variant enters an invalid state - it is valueless by exception.

If move operations didn’t throw, such problems wouldn’t exist. However, there are throwing move constructors in at least MSVC’s implementation of the node-based STL containers, so this is an actual, common problem.

2. Move operations are potentially expensive

If you want to write a constructor that initializes a member of some type T, you could write it like this:

foo(T obj)
: member(std::move(obj)) {}

You take the parameter by-value to allow both lvalues and rvalues, and then move it into the final place. The cost of this operation is a copy for lvalues and a move for rvalues, followed by the additional move into the member. The idea here is that move is cheap, so that the additional move is acceptable.

However, move isn’t necessarily cheap: MSVC’s node-based STL containers need to allocate memory in their move constructor - that’s why they can throw! And memory allocation isn’t cheap.

So in generic code you should write two constructors to deal with that:

foo(const T& obj)
: member(obj) {}

foo(T&& obj)
: member(std::move(obj)) {}

Remember to use std::move in the second constructor!

Inside the constructor, obj is an lvalue, so writing member(obj) would copy it, not move it.

Now the cost for an lvalue is a copy and the cost for an rvalue is a move. However, this leads to 2^n overloads.

An alternative would be to use forwarding references. But they lead to a whole other category of problems.

3. Moved-from state

I’ve already talked about it in the past, but I keep saying it. If you add move operations to a type, you create an additional state: the moved-from state.

Consider the case of writing a non-null std::unique_ptr:

template <typename T>
class owning_ptr
{
public:
    template <typename ... Args>
    explicit owning_ptr(Args&&... args)
    : ptr_(new T(std::forward<Args>(args...))) {}

    ~owning_ptr() { delete ptr_; }

    owning_ptr(const owning_ptr&)            = delete;
    owning_ptr& operator=(const owning_ptr&) = delete;

    T& operator* () { return *ptr_; }
    T* operator->() { return  ptr_; }
};

This smart pointer always owns a valid object. You have a constructor that creates the object, a destructor that destroys the object and access operators. You can call operator* on every owning_ptr object as there is no null state.

This isn’t strictly true: You can call it on an already destroyed smart pointer object, so the ptr_ is already deleted. However accessing an object after its freed is always wrong and always undefined behavior, so it doesn’t really count.

But what if you wanted to make it moveable:

owning_ptr(owning_ptr&& other)
: ptr_(other.ptr_)
{
    // need to reset, so other won't delete ptr_ as well
    other.ptr_ = nullptr;
}

Now we have to introduce a moved-from state. And unlike the destroyed state, that state needs to be valid, at least the destructor will run. And suddenly operator* and operator-> have a precondition: The object must not be in a moved-from state.

There are various opinions on the subject. And yes, each object has such an implicit state anyway - the destroyed one. But I’d argue that the difference between a moved-from state and a destroyed one is that it is easier to access a moved-from state than a destroyed one. And accessing a destroyed object is always undefined behavior, so compilers/static analyzers/sanitizers can help you.

But whether or not you agree with that problem, let’s analyze all three of them.

Why do these problems exist?

These problems are all caused by the fact that the destructor of a moved-from object will run. Furthermore, the standard mandates that moving a standard library object leaves it in a valid, but unspecified-state. See my move safety post for a discussion about it. What this means is that you are allowed to call any operations on an object that doesn’t have a precondition. You can, for example push_back() something in a moved-from vector or clear() a moved-from string.

Consider an implementation of std::list that uses a sentinel node. As such, a list object is never empty which eliminates some branches in the implementation. But due to STL iterator invalidity requirements, the sentinel node has to be dynamically allocated.

And then you want to implement a move constructor.

As the moved-from object can safely be used, you have to make sure that the moved-from object still has a sentinel node. So you need to dynamically allocate one. That’s - as far as I know - the reason for MSVC’s possibly expensive, throwing move constructors.

But there’s a fix for all these problems: Don’t allow the usage of a moved-from object. In fact, don’t even call the destructor of a moved-from object. This is called a destructive move.

So let’s enter a magical world where std::move() does a destructive move instead.

Destructive move: the basics

Instead of leaving a moved-from object in a valid, yet unspecified state, lets leave it in a destroyed state - just like after a destructor is run. Nobody is allowed to do anything with this variable, it is practically destroyed.

This has lots of consequences.

For one, we don’t actually need destructive move constructors for most types. Consider the move constructor of the owning_ptr again:

owning_ptr(owning_ptr&& other)
: ptr_(other.ptr_)
{
    // need to reset, so other won't delete ptr_ as well
    other.ptr_ = nullptr;
}

As the comment explains: the destructor of other will run, so it needs to make sure that it won’t delete the object as well. But if the destructor doesn’t run, all it needs to do is copy the pointer over. Both objects will now own the same memory, but that doesn’t matter as no one is allowed to do anything with other afterwards anyway!

How does a destructive move for std::vector work? Simple: copy over the pointer to memory plus size and capacity. There’s no need to reset the original object.

And what about the problematic sentinel nodes before? As the original object doesn’t need to keep them, its again a simple copy of the pointers.

In fact, a destructive move is just a std::memcpy! It doesn’t need to do anything fancy.

Well, not quite - there’s a problem:

Destructive move: pointers pointing inside the moved-from object

Consider a singly-linked list implementation with sentinel node again. But this time, the sentinel is stored in the object itself, pointing to the first node. And the list implementation is also circular, so the last node points back to the sentinel.

Then run into a problem: our memcpy-based destructive move will simply copy the original object, including the sentinel node, but excluding all heap allocated nodes. This means that the last node will be left unchanged: it will still point to the sentinel of the original list! When the original object is destroyed - as in: it’s memory freed, remember: no destructor will run - we have a dangling pointer.

So what would be a correct destructive move operation here?

The initial std::memcpy isn’t a problem, it’s just not enough. After the memcpy we have to adjust the pointer of the last node, so that it points to the new proxy.

We need a post-destructive move callback. It is called after the memcpy operation at a point where both objects are bitwise identical. It can then adjust pointers:

void list::post_destructive_move(list&& old)
{
    // find last node
    auto cur = &old.proxy_;
    while (cur->next != &old.proxy_)
        cur = cur->next;

    // last node points to old.proxy,
    // so adjust
    cur->next = &proxy_;
}

Such a function would also be called for all members - either implicitly or explicitly. However, most types who would need it operator on a level where the members have a trivial post_destructive_move().

I can’t imagine a situation where a post destructive move needs more than to adjust pointers, so destructive move is always going to be noexcept.

However, now it isn’t necessarily cheap. In the given example, the list doesn’t store a pointer to the last node, so we have to loop and find it. A destructive move that isn’t cheap means that we can’t pass things by value in generic code and have to deal with the forwarding reference madness.

Or do we? Let’s take a closer look at the situation when we pass an object by value to a function:

void consume(T param) // (2)
{
    target = std::move(param); // (3)
}



T var;
consume(std::move(var)); // (1)

First, we move the variable (1) into the space for the function parameter (2), then we move it from (2) to the final location (3). What this means is a memcpy() from var to param, calling param.post_destructive_move(var), then a memcpy() from param to target and calling target.post_destructive_move(param).

But note that we don’t do anything with the parameter - except move it again. So a compiler could employ an optimization where the two post_destructive_move() calls are combined into one: calling target.post_destructive_move(var).

With this optimization, the only additional to cost to pass by value is an unnecessary memcpy(), and unless you have a really big object that is probably acceptable. This means that destructive move doesn’t suffer from problem 1 - throwing move - and 2 - expensive move. But what about problem 3: moved-from state?

Destructive move: moved-from state

A destructive move - by its very nature - destroys the object that is being moved from.

This means that code like this is dangerous:

T obj;
T other_obj = std::move(obj);
do_sth(obj);

There is no actual object anymore, you’re using a destroyed variable. But even worse: obj hasn’t been changed by the destructive move, so the error will not be noticed necessarily.

This can be improved if the compiler memsets a moved-from object to some magic value in debug mode, like MSVC already does with freed memory.

However, this isn’t an entirely new problem: Replace T with std::unique_ptr and do_sth() with operator* - the plain move alone is dangerous. The only difference is that a destructive moved-from object cannot be assigned a new value, as the assignment operator will try and destroy it.

So have we really solved the problem 3 - moved-from state?

The situation is better than with non-destructive move. Now the compiler knows that using a moved-from object is always going to be undefined behavior. And if the compiler knows something, it can help us. It’s the same problem with accessing an already destroyed object, except that it is easier to get a moved-from variable.

In that particular case there could even be an additional rule that destructive moving a local variable will “undeclare” the identifier: After it is moved-from the name, there simply is no variable anymore and any usage is a compiler error.

But this doesn’t solve every situation, pointer arithmetic ruins everything:

T array[N];
auto ptr = &array[0];
consume(std::move(*ptr));
ptr += n;
--ptr;
consume(std::move(*ptr));

Depending on the value of n, the final usage might use a moved-from variable. And if you try to statically detect such situations, you end up with Rust.

This is also the reason that re-assigning a moved-from variable must not be allowed: It cannot statically be determined whether the assignment operator needs to destroy the object.


Advertisement

Conclusion

Destructive move, as I have discussed here, is a move operation that completely destroys the original object. The semantics for a destructive move from a to b are as follows: first, memcpy() a’s memory to b, then invoke a post_destructive_move() function for pointer adjustments. This move is always nothrow and - assuming elimination of unnecessary post_destructive_move() calls - always cheap.

Such a move operation means simpler generic code and could have been done without the addition of rvalue references, complicating an already complicated language even more. However, the downside is that it is easier to access destroyed variables, so such issues would be more common. A smart lifetime analysis system would help there, but is most likely impossible for C++ and more suited to languages like Rust, which have destructive move.

Destructive move would have been a great addition to pre-C++11 and it can be argued that it is better - albeit less save - than our current moving model, however now it is probably too late to implement it for C++.

This post was made possible by my Patreon supporters. If you'd like to support me as well, please head over to my Patreon and do so! One dollar per month can make all the difference.