Bubble sort with XOR or a temporary variable

Question

In a scenario of sorting an array using the bubble sort algorithm, which is more effective: Creating a temporary variable inside a nested-loop or using the XOR operator:

#include <iostream>

int main()
{
    int array[5] = {7, 2, 5, 3, 4};

    /* 1: using a temporary variable

    for(int i(0); i < 5; i++)
    {
        for(int j(i + 1); j < 5; j++)
        {
            if(array[i] > array[j])
            {
                int tmp  = array[i];
                array[i] = array[j];
                array[j] = tmp;
            }
        }
    }
    */

    // 2: using the XOR ^ swapper
    for(int i = 0; i < 5; i++)
    {
        for(int j(i + 1); j < 5; j++)
        {
            if(array[i] > array[j])
            {
                array[i] ^= array[j];
                array[j] ^= array[i];
                array[i] ^= array[j];
            }
        }
    }


    for( i = 0; i < 5; i++)
        std::cout << array[i] << ", ";

    std::cout << std::endl;
    return 0;
}

I only want to know which is quicker and more powerful, knowing that the two methods work fine.

Answer 1

As others have already pointed out, the only way to know for sure is to measure it.

"How do I measure it?" would have been the subject of an altogether different question, if such a question was on-topic on Stack Overflow. But it isn't.

Google is your friend. Google it. Look for keywords such as "benchmark" or "profile" together with "C++" and perhaps the name of the IDE you are using.

Aside from that, I can give you some pretty good indication as to which one will be faster by just examining the instructions.

The instruction sequence

  a ^= b;
  b ^= a;
  a ^= b;

translates into the following unoptimized instructions:

  load  register from a            ;memory reference
  xor   register with b            ;memory reference
  store register to a              ;memory reference
  load  register from b            ;memory reference
  xor   register with a            ;memory reference
  store register to b              ;memory reference
  load  register from a            ;memory reference
  xor   register with b            ;memory reference
  store register to a              ;memory reference

which are likely optimizable as follows:

  load  register1 from a           ;memory reference
  load  register2 from b           ;memory reference
  xor register1 with register2
  xor register2 with register1
  xor register1 with register2
  store register1 to a             ;memory reference
  store register2 to b             ;memory reference

The instruction sequence

  int tmp  = a;
  a = b;
  b = tmp;

translates into the following unoptimized instructions:

  load  register from a            ;memory reference
  store register to tmp            ;memory reference
  load  register from b            ;memory reference
  store register to a              ;memory reference
  load  register from tmp          ;memory reference
  store register to b              ;memory reference

which are likely optimizable as follows:

  load register1 from a            ;memory reference
  load register2 from b            ;memory reference
  store register1 to b             ;memory reference
  store register2 to a             ;memory reference

As you can see, both optimized fragments only involve four memory references, so the two approaches are roughly equal, but the XOR approach involves three extra instructions, so it cannot possibly perform better.

Don't believe me? Well then, don't take my word for it! I cannot even be sure what kinds of additional optimizations your compiler may be capable of performing. So, besides running a benchmark or profiling the code, try also seeing the assembly produced by your compiler for the above fragments of code. (With all optimizations enabled, of course.)