Faster Swap - XOR or Temporary Variable?

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