Jerry Pisk asks -- Which is faster for swapping integer values – the old XOR “trick” or just using a temp variable?
Jerry opines that the temp var method should be faster - I agreed, but thought it might be interesting to dig into this a little.
There’s a fair amount of anecdotal evidence on the internets about this topic already, but I wanted to test the theory out in both C# and in C++ (MSVC) for myself.
The algorithm I used to compare went like this: create two large-ish arrays, fill them with random, unsigned 32-bit ints and then reverse the arrays in place – one using temp storage and the other using XOR.
The crux of the code looks like this:
Swap
while (i < j) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
XOR
while (i < j) {
array[i] ^= array[j];
array[j] ^= array[i];
array[i] ^= array[j];
}
My mean timings over a few thousand iterations were identical for both languages on my machine – ~11ms for Temp and ~17ms for XOR for 5 million swap operations.
I was interested to see what the compilers did to the high-level XORs and, in the end, they did essentially the same thing:
.Net
xor dword ptr [edx],eax
C++
xor DWORD PTR [eax+edx*4], esi
Note: I didn’t see the XCHG instruction in either language for either algorithm.
So we see that the temp variable swap technique is significantly faster than the XOR swap technique (in these languages on my machine, etc.).
