Making swap faster, easier to use and exception-safe

Question

I could not sleep last night and started thinking about std::swap. Here is the familiar C++98 version:

template <typename T>
void swap(T& a, T& b)
{
    T c(a);
    a = b;
    b = c;
}

If a user-defined class Foo uses external ressources, this is inefficient. The common idiom is to provide a method void Foo::swap(Foo& other) and a specialization of std::swap<Foo>. Note that this does not work with class templates since you cannot partially specialize a function template, and overloading names in the std namespace is illegal. The solution is to write a template function in one's own namespace and rely on argument dependent lookup to find it. This depends critically on the client to follow the "using std::swap idiom" instead of calling std::swap directly. Very brittle.

In C++0x, if Foo has a user-defined move constructor and a move assignment operator, providing a custom swap method and a std::swap<Foo> specialization has little to no performance benefit, because the C++0x version of std::swap uses efficient moves instead of copies:

#include <utility>

template <typename T>
void swap(T& a, T& b)
{
    T c(std::move(a));
    a = std::move(b);
    b = std::move(c);
}

Not having to fiddle with swap anymore already takes a lot of burden away from the programmer. Current compilers do not generate move constructors and move assignment operators automatically yet, but as far as I know, this will change. The only problem left then is exception-safety, because in general, move operations are allowed to throw, and this opens up a whole can of worms. The question "What exactly is the state of a moved-from object?" complicates things further.

Then I was thinking, what exactly are the semantics of std::swap in C++0x if everything goes fine? What is the state of the objects before and after the swap? Typically, swapping via move operations does not touch external resources, only the "flat" object representations themselves.

So why not simply write a swap template that does exactly that: swap the object representations?

#include <cstring>

template <typename T>
void swap(T& a, T& b)
{
    unsigned char c[sizeof(T)];

    memcpy( c, &a, sizeof(T));
    memcpy(&a, &b, sizeof(T));
    memcpy(&b,  c, sizeof(T));
}

This is as efficient as it gets: it simply blasts through raw memory. It does not require any intervention from the user: no special swap methods or move operations have to be defined. This means that it even works in C++98 (which does not have rvalue references, mind you). But even more importantly, we can now forget about the exception-safety issues, because memcpy never throws.

I can see two potential problems with this approach:

First, not all objects are meant to be swapped. If a class designer hides the copy constructor or the copy assignment operator, trying to swap objects of the class should fail at compile-time. We can simply introduce some dead code that checks whether copying and assignment are legal on the type:

template <typename T>
void swap(T& a, T& b)
{
    if (false)    // dead code, never executed
    {
        T c(a);   // copy-constructible?
        a = b;    // assignable?
    }

    unsigned char c[sizeof(T)];

    std::memcpy( c, &a, sizeof(T));
    std::memcpy(&a, &b, sizeof(T));
    std::memcpy(&b,  c, sizeof(T));
}

Any decent compiler can trivially get rid of the dead code. (There are probably better ways to check the "swap conformance", but that is not the point. What matters is that it's possible).

Second, some types might perform "unusual" actions in the copy constructor and copy assignment operator. For example, they might notify observers of their change. I deem this a minor issue, because such kinds of objects probably should not have provided copy operations in the first place.

Please let me know what you think of this approach to swapping. Would it work in practice? Would you use it? Can you identify library types where this would break? Do you see additional problems? Discuss!

Answer 1

So why not simply write a swap template that does exactly that: swap the object representations*?

There's many ways in which an object, once being constructed, can break when you copy the bytes it resides in. In fact, one could come up with a seemingly endless number of cases where this would not do the right thing - even though in practice it might work in 98% of all cases.

That's because the underlying problem to all this is that, other than in C, in C++ we must not treat objects as if they are mere raw bytes. That's why we have construction and destruction, after all: to turn raw storage into objects and objects back into raw storage. Once a constructor has run, the memory where the object resides is more than only raw storage. If you treat it as if it weren't, you will break some types.

However, essentially, moving objects shouldn't perform that much worse than your idea, because, once you start to recursively inline the calls to std::move(), you usually ultimately arrive at where built-ins are moved. (And if there's more to moving for some types, you'd better not fiddle with the memory of those yourself!) Granted, moving memory en bloc is usually faster than single moves (and it's unlikely that a compiler might find out that it could optimize the individual moves to one all-encompassing std::memcpy()), but that's the price we pay for the abstraction opaque objects offer us. And it's quite small, especially when you compare it to the copying we used to do.

You could, however, have an optimized swap() using std::memcpy() for aggregate types.

Answer 2

This will break class instances that have pointers to their own members. For example:

class SomeClassWithBuffer {
  private:
    enum {
      BUFSIZE = 4096,
    };
    char buffer[BUFSIZE];
    char *currentPos; // meant to point to the current position in the buffer
  public:
    SomeClassWithBuffer();
    SomeClassWithBuffer(const SomeClassWithBuffer &that);
};

SomeClassWithBuffer::SomeClassWithBuffer():
  currentPos(buffer)
{
}

SomeClassWithBuffer::SomeClassWithBuffer(const SomeClassWithBuffer &that)
{
  memcpy(buffer, that.buffer, BUFSIZE);
  currentPos = buffer + (that.currentPos - that.buffer);
}

Now, if you just do memcpy(), where would currentPos point? To the old location, obviously. This will lead to very funny bugs where each instance actually uses another's buffer.

Answer 3

Some types can be swapped but cannot be copied. Unique smart pointers are probably the best example. Checking for copyability and assignability is wrong.

If T isn't a POD type, using memcpy to copy/move is undefined behavior.

---

The common idiom is to provide a method void Foo::swap(Foo& other) and a specialization of std::swap<Foo>. Note that this does not work with class templates, …

A better idiom is a non-member swap and requiring users to call swap unqualified, so ADL applies. This also works with templates:

struct NonTemplate {};
void swap(NonTemplate&, NonTemplate&);

template<class T>
struct Template {
  friend void swap(Template &a, Template &b) {
    using std::swap;
#define S(N) swap(a.N, b.N);
    S(each)
    S(data)
    S(member)
#undef S
  }
};

The key is the using declaration for std::swap as a fallback. The friendship for Template's swap is nice for simplifying the definition; the swap for NonTemplate might also be a friend, but that's an implementation detail.

Answer 4

I deem this a minor issue, because such kinds of objects probably should not have provided copy operations in the first place.

That is, quite simply, a load of wrong. Classes that notify observers and classes that shouldn't be copied are completely unrelated. How about shared_ptr? It obviously should be copyable, but it also obviously notifies an observer- the reference count. Now it's true that in this case, the reference count is the same after the swap, but that's definitely not true for all types and it's especially not true if multi-threading is involved, it's not true in the case of a regular copy instead of a swap, etc. This is especially wrong for classes that can be moved or swapped but not copied.

because in general, move operations are allowed to throw

They are most assuredly not. It is virtually impossible to guarantee strong exception safety in pretty much any circumstance involving moves when the move might throw. The C++0x definition of the Standard library, from memory, explicitly states any type usable in any Standard container must not throw when moving.

This is as efficient as it gets

That is also wrong. You're assuming that the move of any object is purely it's member variables- but it might not be all of them. I might have an implementation-based cache and I might decide that within my class, I should not move this cache. As an implementation detail it is entirely within my rights not to move any member variables that I deem are not necessary to be moved. You, however, want to move all of them.

Now, it's true that your sample code should be valid for a lot of classes. However, it's extremely very definitely not valid for many classes that are completely and totally legitimate, and more importantly, it's going to compile down to that operation anyway if the operation can be reduced to that. This is breaking perfectly good classes for absolutely no benefit.

Answer 5

your swap version will cause havoc if someone uses it with polymorphic types.

consider:

Base *b_ptr = new Base();    // Base and Derived contain definitions
Base *d_ptr = new Derived(); // of a virtual function called vfunc()
yourmemcpyswap( *b_ptr, *d_ptr );
b_ptr->vfunc(); //now calls Derived::vfunc, while it should call Base::vfunc
d_ptr->vfunc(); //now calls Base::vfunc while it should call Derived::vfunc
//...

this is wrong, because now b contains the vtable of the Derived type, so Derived::vfunc is invoked on a object which isnt of type Derived.

The normal std::swap only swaps the data members of Base, so this is OK with std::swap