What is the fastest way to swap values in C?

Question

I want to swap two integers, and I want to know which of these two implementations will be faster: The obvious way with a temp variable:

void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

Or the xor version that I'm sure most people have seen:

void swap(int* a, int* b)
{
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

It seems like the first uses an extra register, but the second one is doing three loads and stores while the first only does two of each. Can someone tell me which is faster and why? The why being more important.

Answer 1

Number 2 is often quoted as being the "clever" way of doing it. It is in fact most likely slower as it obscures the explicit aim of the programmer - swapping two variables. This means that a compiler can't optimize it to use the actual assembler ops to swap. It also assumes the ability to do a bitwsie xor on the objects.

Stick to number 1, it's the most generic and most understandable swap and can be easily templated/genericed.

This wikipedia section explains the issues quite well: http://en.wikipedia.org/wiki/XOR_swap_algorithm#Reasons_for_avoidance_in_practice

Answer 2

The first is faster because bitwise operations such as xor are usually very hard to visualize for the reader.

Faster to understand of course, which is the most important part ;)

Answer 3

The only way to really know is to test it, and the answer may even vary depending on what compiler and platform you are on. Modern compilers are really good at optimizing code these days, and you should never try to outsmart the compiler unless you can prove that your way is really faster.

With that said, you'd better have a damn good reason to choose #2 over #1. The code in #1 is far more readable and because of that should always be chosen first. Only switch to #2 if you can prove that you need to make that change, and if you do - comment it to explain what's happening and why you did it the non-obvious way.

As an anecdote, I work with a couple of people that love to optimize prematurely and it makes for really hideous, unmaintainable code. I'm also willing to bet that more often than not they're shooting themselves in the foot because they've hamstrung the ability of the compiler to optimize the code by writing it in a non-straightforward way.

Answer 4

I'd be fascinated to see the profiler output that shows this operation to be the bottleneck in your code.

Answer 5

The XOR method fails if a and b point to the same address. The first XOR will clear all of the bits at the memory address pointed to by both variables, so once the function returns (*a == *b == 0), regardless of the initial value.

More info on the Wiki page: XOR swap algorithm

Although it's not likely that this issue would come up, I'd always prefer to use the method that's guaranteed to work, not the clever method that fails at unexpected moments.

Answer 6

If you can use some inline assembler and do the following (psuedo assembler):

PUSH A A=B POP B

You will save a lot of parameter passing and stack fix up code etc.

Answer 7

You are optimizing the wrong thing, both of those should be so fast that you'll have to run them billions of times just to get any measurable difference.

And just about anything will have much greater effect on your performance, for example, if the values you are swapping are close in memory to the last value you touched they are lily to be in the processor cache, otherwise you'll have to access the memory - and that is several orders of magnitude slower then any operation you do inside the processor.

Anyway, your bottleneck is much more likely to be an inefficient algorithm or inappropriate data structure (or communication overhead) then how you swap numbers.

Answer 8

To answer your question as stated would require digging into the instruction timings of the particular CPU that this code will be running on which therefore require me to make a bunch of assumptions around the state of the caches in the system and the assembly code emitted by the compiler. It would be an interesting and useful exercise from the perspective of understanding how your processor of choice actually works but in the real world the difference will be negligible.

Answer 9

On a modern processor, you could use the following when sorting large arrays and see no difference in speed:

void swap (int *a, int *b)
{
  for (int i = 1 ; i ; i <<= 1)
  {
    if ((*a & i) != (*b & i))
    {
      *a ^= i;
      *b ^= i;
    }
  }
}

The really important part of your question is the 'why?' part. Now, going back 20 years to the 8086 days, the above would have been a real performance killer, but on the latest Pentium it would be a match speed wise to the two you posted.

The reason is purely down to memory and has nothing to do with the CPU.

CPU speeds compared to memory speeds have risen astronomically. Accessing memory has become the major bottleneck in application performance. All the swap algorithms will be spending most of thier time waiting for data to be fetched from memory. Modern OS's can have up to 5 levels of memory:

• Cache Level 1 - runs at the same speed as the CPU, has negligible access time, but is small
• Cache Level 2 - runs a bit slower than L1 but is larger and has a bigger overhead to access (usually, data needs to be moved to L1 first)
• Cache Level 3 - (not always present) Often external to the CPU, slower and bigger than L2
• RAM - the main system memory, usually implements a pipeline so there's latency in read requests (CPU requests data, message sent to RAM, RAM gets data, RAM sends data to CPU)
• Hard Disk - when there's not enough RAM, data is paged to HD which is really slow, not really under CPU control as such.

Sorting algorithms will make memory access worse since they usually access the memory in a very unordered way, thus incurring the inefficent overhead of fetching data from L2, RAM or HD.

So, optimising the swap method is really pointless - if it's only called a few times then any inefficency is hidden due to the small number of calls, if it's called a lot then any inefficency is hidden due to the number of cache misses (where the CPU needs to get data from L2 (1's of cycles), L3 (10's of cycles), RAM (100's of cycles), HD (!)).

What you really need to do is look at the algorithm that calls the swap method. This is not a trivial exercise. Although the Big-O notation is useful, an O(n) can be significantly faster than a O(log n) for small n. (I'm sure there's a CodingHorror article about this.) Also, many algorithms have degenerate cases where the code does more than is necessary (using qsort on nearly ordered data could be slower than a bubble sort with an early-out check). So, you need to analyse your algorithm and the data it's using.

Which leads to how to analyse the code. Profilers are useful but you do need to know how to interpret the results. Never use a single run to gather results, always average results over many executions - because your test application could have been paged to hard disk by the OS halfway through. Always profile release, optimised builds, profiling debug code is pointless.

As to the original question - which is faster? - it's like trying to figure out if a Ferrari is faster than a Lambourgini by looking at the size and shape of the wing mirror.

Skizz

Answer 10

For those to stumble upon this question and decide to use the XOR method. You should consider inlining your function or using a macro to avoid the overhead of a function call:

#define swap(a, b)   \
do {                 \
    int temp = a;    \
    a = b;           \
    b = temp;        \
} while(0)

Answer 11

@Harry: Go stand in the corner and think about what you've suggested. Come back when you've realised the error of your ways.

Never implement functions as macros for the following reasons:

1. Type safety. There is none. The following only generates a warning when compiling but fails at run time:

   float a=1.5f,b=4.2f;
   swap (a,b);
   

   A templated function will always be of the correct type (and why aren't you treating warnings as errors?).

   EDIT: As there's no templates in C, you need to write a separate swap for each type or use some hacky memory access.

2. It's a text substitution. The following fails at run time (this time, without compiler warnings):

   int a=1,temp=3;
   swap (a,temp);
   

3. It's not a function. So, it can't be used as an argument to something like qsort.

4. Compilers are clever. I mean really clever. Made by really clever people. They can do inlining of functions. Even at link time (which is even more clever). Don't forget that inlining increases code size. Big code means more chance of cache miss when fetching instructions, which means slower code.

5. Side effects. Macros have side effects! Consider:

   int &f1 ();
   int &f2 ();
   void func ()
   {
     swap (f1 (), f2 ());
   }
   

   Here, f1 and f2 will be called twice.

   EDIT: A C version with nasty side effects:

   int a[10], b[10], i=0, j=0;
   swap (a[i++], b[j++]);
   

Macros: Just say no!

Skizz

EDIT: This is why I prefer to define macro names in UPPERCASE so that they stand out in the code as a warning to use with care.

EDIT2: To answer Leahn Novash's comment:

Suppose we have a non-inlined function, f, that is converted by the compiler into a sequence of bytes then we can define the number of bytes thus:

bytes = C(p) + C(f)

where C() gives the number of bytes produced, C(f) is the bytes for the function and C(p) is the bytes for the 'housekeeping' code, the preamble and post-amble the compiler adds to the function (creating and destroying the function's stack frame and so on). Now, to call function f requires C(c) bytes. If the function is called n times then the total code size is:

size = C(p) + C(f) + n.C(c)

Now let's inline the function. C(p), the function's 'housekeeping', becomes zero since the function can use the stack frame of the caller. C(c) is also zero since there is now no call opcode. But, f is replicated wherever there was a call. So, the total code size is now:

size = n.C(f)

Now, if C(f) is less than C(c) then the overall executable size will be reduced. But, if C(f) is greater than C(c) then the code size is going to increase. If C(f) and C(c) are similar then you need to consider C(p) as well.

So, how many bytes do C(f) and C(c) produce. Well, the simplest C++ function would be a getter:

void GetValue () { return m_value; }

which would probably generate the four byte instruction:

mov eax,[ecx + offsetof (m_value)]

which is four bytes. A call instuction is five bytes. So, there is an overall size saving. If the function is more complex, say an indexer ("return m_value [index];") or a calculation ("return m_value_a + m_value_b;") then the code will be bigger.

Answer 12

I would not do it with pointers unless you have to. The compiler cannot optimize them very well because of the possibility of pointer aliasing (although if you can GUARANTEE that the pointers point to non-overlapping locations, GCC at least has extensions to optimize this).

And I would not do it with functions at all, since it's a very simple operation and the function call overhead is significant.

The best way to do it is with macros if raw speed and the possibility of optimization is what you require. In GCC you can use the typeof() builtin to make a flexible version that works on any built-in type.

Something like this:

#define swap(a,b) \
  do { \
    typeof(a) temp; \
    temp = a; \
    a = b; \
    b = temp; \
  } while (0)

...    
{
  int a, b;
  swap(a, b);
  unsigned char x, y;
  swap(x, y);                 /* works with any type */
}

With other compilers, or if you require strict compliance with standard C89/99, you would have to make a separate macro for each type.

A good compiler will optimize this as aggressively as possible, given the context, if called with local/global variables as arguments.

Answer 13

In my opinion local optimizations like this should only be considered tightly related to the platform. It makes a huge difference if you are compiling this on a 16 bit uC compiler or on gcc with x64 as target.

If you have a specific target in mind then just try both of them and look at the generated asm code or profile your applciation with both methods and see which is actually faster on your platform.

Answer 14

All the top rated answers are not actually definitive "facts"... they are people who are speculating!

You can definitively know for a fact which code takes less assembly instructions to execute because you can look at the output assembly generated by the compiler and see which executes in less assembly instructions!

Here is the c code I compiled with flags "gcc -std=c99 -S -O3 lookingAtAsmOutput.c":

#include <stdio.h>
#include <stdlib.h>

void swap_traditional(int * restrict a, int * restrict b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void swap_xor(int * restrict a, int * restrict b)
{
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

int main() {
    int a = 5;
    int b = 6;
    swap_traditional(&a,&b);
    swap_xor(&a,&b);
}

ASM output for swap_traditional() takes >>> 11 <<< instructions ( not including "leave", "ret", "size"):

.globl swap_traditional
    .type swap_traditional, @function
swap_traditional:
    pushl %ebp
    movl %esp, %ebp
    movl 8(%ebp), %edx
    movl 12(%ebp), %ecx
    pushl %ebx
    movl (%edx), %ebx
    movl (%ecx), %eax
    movl %ebx, (%ecx)
    movl %eax, (%edx)
    popl %ebx
    popl %ebp
    ret
    .size swap_traditional, .-swap_traditional
    .p2align 4,,15

ASM output for swap_xor() takes >>> 11 <<< instructions not including "leave" and "ret":

.globl swap_xor
    .type swap_xor, @function
swap_xor:
    pushl %ebp
    movl %esp, %ebp
    movl 8(%ebp), %ecx
    movl 12(%ebp), %edx
    movl (%ecx), %eax
    xorl (%edx), %eax
    movl %eax, (%ecx)
    xorl (%edx), %eax
    xorl %eax, (%ecx)
    movl %eax, (%edx)
    popl %ebp
    ret
    .size swap_xor, .-swap_xor
    .p2align 4,,15

Summary of assembly output:
swap_traditional() takes 11 instructions
swap_xor() takes 11 instructions

Conclusion:
Both methods use the same amount of instructions to execute and therefore are approximately the same speed on this hardware platform.

Lesson learned:
When you have small code snippets, looking at the asm output is helpful to rapidly iterate your code and come up with the fastest ( i.e. least instructions ) code. And you can save time even because you don't have to run the program for each code change. You only need to run the code change at the end with a profiler to show that your code changes are faster.

I use this method a lot for heavy DSP code that needs speed.

Answer 15

If your compiler supports inline assembler and your target is 32-bit x86 then the XCHG instruction is probably the best way to do this... if you really do care that much about performance.

Here is a method which works with MSVC++:

#include <stdio.h>

#define exchange(a,b)   __asm mov eax, a \
                        __asm xchg eax, b \
                        __asm mov a, eax               

int main(int arg, char** argv)
{
    int a = 1, b = 2;
    printf("%d %d --> ", a, b);
    exchange(a,b)
    printf("%d %d\r\n", a, b);
    return 0;
}

Answer 16

void swap(int* a, int* b)
{
    *a = (*b - *a) + (*b = *a);
}

// My C is a little rusty, so I hope I got the * right :)

Answer 17

Another beautiful way.

#define Swap( a, b ) (a)^=(b)^=(a)^=(b)

Advantage

No need of function call and handy.

Drawback:

This fails when both inputs are same variable. It can be used only on integer variables.