Swapping two numbers - Processor behavior

Question

I was looking for alternate options to swap two numbers and came across the link How to swap two numbers

In the comments section its been mentioned that using temporary variable is better. Below is the comment I copied form the link

If we look at the problem at the CPU instructions perspective, use tmp will be better than all above 3 method, i have run a benchmark agains all those 4 method (including the 4th by ?using temp variable). without surprise, the 4th way beats all above 3 method. And the reason is how CPU move the variable into register and how many register we need to use.

But I am not able to find a clue on how it works. Can someone explain me how it works at the processor level and why temp variable is better (if it is)?

Answer 1

The only way to see what kind of optimisation happens at this level is to compile and disassemble. It turns out that the compiler is already very good at removing or reinterpreting your code to make it faster.

I compiled this code using the MS C compiler:

int main() 
{
        int a = 1;
        int b = 2;
        int c;

        // Force use of the variables so they aren't optimized away
        printf("a = %d, b = %d\n", a, b);

        c = b;
        b = a;
        a = c;

        // Force use again
        printf("a = %d, b = %d\n", a, b);

        return 0;
}

This is the actual output after optimisations, edited for brevity:

; 4    :    int a = 1;
; 5    :    int b = 2;
; 6    :    int c;

; OPTIMISED AWAY

; 8    :    printf("a = %d, b = %d\n", a, b);

    push    2
    push    1
    push    pointer_to_string_constant
    call    DWORD PTR __imp__printf

; 10   :    c = b;
; 11   :    b = a;
; 12   :    a = c;

; OPTIMISED AWAY

; 14   :    printf("a = %d, b = %d\n", a, b);

    push    1
    push    2
    push    pointer_to_string_constant
    call    DWORD PTR __imp__printf

; 16   :    return 0;

    xor eax, eax ; Just a faster way of saying "eax = 0;"

; 17   : }

    ret 0

So you see, the compiler decided in this case not to use any variables at all and just push the integers directly to the stack (this is the same as passing arguments to a function in C).

The moral of this story is not to second guess the compiler when it comes to micro-optimisations.

Answer 2

Thanks everyone for your valuable inputs. I wrote a simple program and viewed the assembly output (it's a C program compiled in Xcode). Looks like XOR operation is twice as costly than using a temporary variable. Attached both the generated assembly code images. When I use temporary variable each operation (a = b & so) takes two instructions. But when I use XOR each operation (a ^= b & so) takes 4 instructions. Below is my program for reference. The screenshot only contains the assembly code for lines within main (except return 0)

#include <stdio.h>

int main(int argc, const char * argv[])
{

int a = 100;
int b = 200;
int c;

c = a;
a = b;
b = c;

return 0;
}

#include <stdio.h>

int main(int argc, const char * argv[])
{

int a = 100;
int b = 200;

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

return 0;
}

These results may be specific to MAC runtime and/or the way Xcode compiles. If you think I missed something during this process do post your comment.

Answer 3

The "without temp variable" solutions have an arithmetic or logical operation per each statement apart from the assignment. For example,

      x = x + y;  
      y = x - y; 
      x = x - y; 

The temporary variable solution will simply have assignments.

temp = a;
a    = b;
b    = temp;

So the temporary variable solution will obviously have better performance in terms of CPU.

Answer 4

If we use below method

x = x + y;  
y = x - y; 
x = x - y; 

These instructions includes arithmetic operations along with assignments. It requires more cpu cycles to complete swapping.

If you use a temporary variable to swap two values, it don't need any arithmetic operations. It just do it by assigning values. This requires less CPU cycles as compared to above solution.