Analysis of a "technique" for swapping 2 variables without a third temp variable

Question

I have come across a "technique" for swapping 2 variables (ints, chars or pointers) without a third temp variable , like this :

int a = Something ;  
int b = SomethingElse ;  
a ^= b ;  
b ^= a ;  
a ^= b ;

Normal way would be :

int a = Something ;  
int b = SomethingElse ;  
int temp = a ;  
a = b ;  
b = temp ;

All this is fine, but the folks who share this "technique" usually state it as without using extra space.

(A) Is this true that there is no extra space ? I think, "memory to memory copy" would require fewer instructions (machine code) compared to "memory to memory XOR operation".

int temp = a <==> move content of memory location a to memory location temp **(1 instruction)**, possibly via a register **(2 instructions)**

a ^= b <==> move contents of memory location a to register1, move contents of memory location b to register2, xor register1 and register2 (store results in register1) , move register1 to memory location a **(about 4 instructions)**

It seems that the "technique" will result in longer code and longer runtime.

(B) Is the "technique" faster (or better) in some way or in some cases ?

It seems like the "technique" is slower, uses more memory, and not really suitable for floating points.

EDIT:
It seems that there may be some Potential Duplicates :
Why don't people use xor swaps?

But this question is obviously Different:
(A) That question was closed as "Not Constructive" , where it "will likely solicit debate, arguments, polling, or extended discussion", whereas this question is looking for factual references, eg "Is something true ?" & "Is this better ?"
(B) That question is about why people do not use the "technique", while this question is about the analysis of the "technique", without looking onto why people use it or do not use it.

Answer 1

There's no definitive answer: it depends too much on:

1. the architecture of the machine (number of processors, memory cache size, etc); and
2. the quality of the compiler's optimisation.

If all the operations are performed within registers, there is unlikely to be a performance penalty of XOR compared with copy.

If you use a third variable you could help the compiler by declaring:

register int temp;

The use of the XOR technique (or addition and subtraction, as in a-=b; b+=a; a=b-a;) dates back to when memory was a crucial resource and saving a stack entry could be very important. These days the only value of this is code obfuscation.

I have absolutely no idea what the effect of XOR would be on floating-point values, but I suspect they might be converted to integers first: you will need to try it, but there is no guarantee that all compilers will give the same result.

Answer 2

For lower level (e.g. assembly) "variables" no longer have a permanent location. Sometimes a variable will be in memory, but sometimes the same variable will be in one register, and sometimes in a different register.

When generating code, the compiler has to keep track of where each variable happens to be at each point. For an operation like a = b, if b is in register1 then the compiler just decides that a is now also in register1. Nothing needs to be moved or copied.

Now consider this:

// r0 contains variable a
// r1 contains variable b

    temp = a

// r0 contains variable a and variable temp
// r1 contains variable b

    a = b

// r0 contains variable temp
// r1 contains variable b and variable a

    b = temp

// r0 contains variable temp and variable b
// r1 contains variable a

If you think about this you'll realise that no data needs to be moved or copied, and no code needs to be generated. Modern CPUs are able to do "nothing" extremely quickly.

Note: If a variable is a local variable (on the stack) and isn't in a register, then the compiler should be able to do the same "renaming" to avoid moving anything. If the variable is a global variable then things get more complicated - most likely causing a load from memory and a store to memory for each global variable (e.g. 2 loads and 2 stores if both variables are global).

For XOR (and addition/subtraction) the compiler might be able to optimise it so that it becomes nothing; but I wouldn't count on it. The temporary variable moves are much more likely to be optimised well.

Of course not everything is small enough to fit in a register. For example, maybe you're swapping structures and they're 1234 bytes each. In this case the programmer might use memcpy() and the compiler has to do the copies; or the programmer might do one field at a time with XOR (or addition/subtraction) and the compiler has to do that. For these the memcpy() is much more likely to be better optimised. However, maybe the programmer is smarter, and doesn't swap the 1234 bytes of data and only swaps pointers to the data. Pointers fit in registers (even when the data they point to doesn't), so maybe no code is generated for that.

Answer 3

If you are manipulating ints or doubles (or more generally, any type that hold addition and subtraction operators), you can do it like this :

int a = 5;
int b = 7;
a += b;    // a == 12, b == 7
b = a - b; // a == 12, b == 5
a -= b;    // a == 7,  b == 5