Why swap doesn't use Xor operation in C++

Question

I've learned that Xor operation can be used to implement effective swap function. like this:

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

But the implementation of swap all i can found on the internet is essentially like this:

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

It seems that the compiler didn't generate the same code for the two form above because I tested it on VC++ 2010 and the first one is done the job more quickly than std::swap. Is there portable or any other problem with first one? Feel free to correct any of my mistake cause i'm not an English native and not good at C++.

(Editor's note: likely that test was done with a non-optimized debug build, not a release build where std::swap could inline. Benchmarking debug builds is meaningless. Compilers generally don't optimize away xor-swap into something more efficient.)

Answer 1

I've learned that Xor operation can be used to implement effective swap function

You learned wrong, I'm afraid. XOR swap is outdated: if it was ever reliably faster than using a temporary value then it shouldn't be on modern compilers and processors (where by "modern" I mean roughly the last 20 years or more). You say it was faster for you, possibly you should show your benchmark code and see whether others get the same results.

Aside from the fact that your code only works at all on integer types, it has a fundamental bug. Try this with your version of swap:

int a = 1;
swap(a,a);
std::cout << a << '\n';

Answer 2

And the effectiveness depends on where you use it.

On a normal cpu, the normal swap for two integer variable looks like

$1 <- a
$2 <- b
a <- $2
b <- $1

4 ops, 2 loads, 2 stores, and longest dependency is 2

In the xor way:

$1 <- a
$2 <- b
$3 <- $1 ^ $2
$4 <- $3 ^ $2
$5 <- $3 ^ $4
a <- $5
b <- $4

7 ops, 2 loads, 2 stores, 3 logics, and longest dependency is 4

So at least normally swap with xor is slower even when applicable.

Answer 3

I think the most obvious reason is that the XOR operator only makes sense for integral types.

Answer 4

Of course, because the xor trick works for POD types.

If you wanted to swap two user-defined, complex types, xor wouldn't work. You'd need a deep-copy, not a direct copy of the raw memory, which is kind of what xor does.

EDIT:

I tested it on VC++ 2010 and the first one is done the job more quickly(and is more quickly than std::swap).

Really? Did you compile in debug mode? What are your results?

Answer 5

Firstly, the XOR operator is only defined for integral types.

Secondly, you could use casting tricks to bring non-integral types into integral form.

But thirdly, for all but POD types this results in undefined behavior,

and fourthly for types that do not have a well supported size/alignment for the XOR operation, more twiddling would be required (loops being the least evil).

You could overload the operator^, but that would mean that each specialization of swap() must ensure it exists, or define one, and this might yield more confusion upon name-lookup than what would be worth it. And of course, if such operator already exists, it does not necessarily have the right behavior, and you might end up with worse performance because such overload is not necessarily inline or constexpr.