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.)

Nikko

Just an assumption: at least x86 CPUs have XCHG instruction, which is faster than three XORs. – Carousal

Did you run your test with optimizations enabled? – Renatarenate

@Joulukuusi The XCHG instruction on x86 was never be meant to be a swap replacement. It has an implicit lock prefix if used on memory operands, it is used as a tool for synchronization. XCHG reg, reg could be used possibly, though I doubt it is ever needed - renaming the registers is even faster. I have written a few k lines of assembly, I have never felt the urge to use xchg for swapping values. – Pix

@phresnel o god, i find I've never accept an answer cause i don't know how to accept it. – Nikko

@drhirsch, thank you! It turned out that gcc optimises the second swap function out to few movs on my machine. – Carousal

A related question Weird XOR swap behavior while zeroing out data – Punnet

Related: Why is the XOR swap optimized into a normal swap using the MOV instruction? - GCC / clang will disentangle xor-swap in the source into just plain swap using a temporary. – Argentite

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';

Sjoberg

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.

Girardo

With a modern SSA compiler the first is even simpler: Rename(a1,b2), Rename(b1,a2) - not a single CPU instruction, but just a bookkeeping thing for the compiler. Which variable went in which register? – Organist

Answer 3

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

Renatarenate

You could always offer overloads/specialisations for suitable types though. – Strigil

You could do evil casts, though. – Hellebore

@phresnel not in the standard, I'd hope :) – Renatarenate

You can add the specialization yourself though, so there's no need for the standard library to do it. They could of course, but it's not clear that it's really worth the effort. – Shih

@Shih no, you can't. You can only specialize for user-defined types. Only the standard library implementors can, though. – Renatarenate

@R.MartinhoFernandes im loving it... just loving it :)) – Spokane

@R.MartinhoFernandes: Prolly nothing portable, but I am sure you (as a library implementor) can do it in a an implementation defined fashion though. (classy dubious union-pun trick) – Hellebore

Wrapping it in a "namespace std {}" block has always appeared to work, but admittedly, that doesn't seem to be explicitly allowed by the standard. It's a weird limitation though. The obvious implementation that allows specialization for user-defined types also allows built-in types -- template specialization doesn't generally recognize a distinction. So vendors would need to go out of their way to prevent it, unless of course I'm missing something obvious. – Shih

@R.MartinhoFernandes, I am really curious why can't users add specializations?? Can you please explain? – Lumberjack

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?

Alric

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.

Hellebore