Compiling swap()

"How do I swap two variables without using a temporary variable?" is one of the dumber programming questions. Please tell me you don't use this in interviews. There's the sensible way, the way using XOR that everybody "clever" knows, and an even worse implementation that relies upon undefined behavior.

Standalone compilation

What do these versions actually compile to? Let's use the Compiler Explorer to find out.

Source code, using C++ references:

void swap( int &a, int &b ) {
    int t = a;
    a = b;
    b = t;
}

void farTooCleverSwap( int &a, int &b ) {
    a ^= b;
    b ^= a;
    a ^= b;
}

void stupidSwap( int &a, int &b) {
    a = a + b;
    b = a - b;
    a = a - b;
}

When we compile these under GCC 8.2 with the -O3 flag, we get

As promised, the versions without temporaries use one fewer register. The downside is that they now have less instruction-level parallelism, because each instruction depends on the one immediately before... and the code is larger, too. That edx register is caller-saved, so the calling function can't make use of the fact that it's unused anyway.

In-place compilation

OK, you might argue, what about when the function is inlined? Then register pressure might be relevant, and the XORs could be more efficient than spilling a register to memory.

Good luck finding such a case. In fact, both GCC and clang are smart enough to know that all three functions are swaps and eliminate them altogether if possible.

Here's a test function:

int testFunc( int a, int b ) {
    printf( "%d %d\n", a, b );
    swap( a, b );
    printf( "%d %d\n", a, b );
    farTooCleverSwap( a, b );
    printf( "%d %d\n", a, b );
    stupidSwap( a, b );
    printf( "%d %d\n", a, b );
}

and the compiler output from clang 6.0.0, with -O3

testFunc(int, int):                          # testFunc(int, int)
        push    rbp
        push    rbx
        push    rax
        mov     ebx, esi
        mov     ebp, edi
        mov     edi, offset .L.str
        xor     eax, eax
        mov     esi, ebp
        mov     edx, ebx
        call    printf
        mov     edi, offset .L.str
        xor     eax, eax
        mov     esi, ebx
        mov     edx, ebp
        call    printf
        mov     edi, offset .L.str
        xor     eax, eax
        mov     esi, ebp
        mov     edx, ebx
        call    printf
        mov     edi, offset .L.str
        xor     eax, eax
        mov     esi, ebx
        mov     edx, ebp
        call    printf
.L.str:
        .asciz  "%d %d\n"

What happened here? The compiler stashed a and b in the ebx and ebp registers. Then it just pulls them out in whatever order are necessary to call printf. All your clever work to avoid introducing an extra register use, and the compiler went with two temporaries! Well, they were probably necessary anyway to save the arguments across the function call, but that just shows how useless trying to optimize away register usage is, when we're starting from C. Let the compiler worry about its register usage.

In fact, an earlier attempt to do a demonstration failed because I used constants to initialize a and b and the compiler just chose to load them new each time:

testFunc():                           # @testFunc()
        push    rax
        mov     edi, offset .L.str
        mov     esi, 3
        mov     edx, 5
        xor     eax, eax
        call    printf
        mov     edi, offset .L.str
        mov     esi, 5
        mov     edx, 3
        xor     eax, eax
        call    printf
        ...

Inspiration: https://www.quora.com/Can-I-swap-without-any-extra-variable-in-C/answer/Sergey-Zubkov-1 (and a later answer of his which did more or less the same thing.)

Addendum

In Python (or other languages with decent tuple support) the matter doesn't arise. Simply do

x,y = y,x

Is there a C++ version of this? std::pair has an inline swap method and of course the function template std::swap is better than writing your own--- it has specializations for all the containers you might think of swapping. Let's look at an example of that, here's a C++ function that swaps two vectors:

and here's the compiled version (color-coded so you can see that the green part is the 'if' statement and the white part is the swap.