tags:

views:

2416

answers:

18

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.

+57  A: 

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

caramelcarrot
Spot on. In general, it's best to state your aim to the compiler, rather than trying to trick it into doing what you want. A swap-with-temporary-variable is such a common operation that any decent compiler can optimize it ruthlessly.
Dan
I completely agree. Furthermore, if value swapping is really a bottleneck (proven by measurement), and can't be avoided, implement every way to do it you can think of and measure which is faster _for_ _you_ (your machine, OS, compiler, and app). There is no generic answer for low level stuff.
Lars Wirzenius
I was under the impression that `swap`, at least on x86, was really just calling three successive `xor`s
warren
+5  A: 

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

Sander
+3  A: 

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.

17 of 26
+9  A: 

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

DrPizza
He's obviously writing a program to cheat his local casino ;)
Bobby Jack
sorting algorithms do many swaps, maybe he is profiling one :)
vilaca
+32  A: 

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.

Ant
It's pretty easy to prevent aliasing by adding a conditon *a != *b.
Then your swap function has a branch. As much as it's a silly question to begin with, if the OP is after speed then introducing a branch is probably a bad idea.
Matt Curtis
@mamama, also, it should be a != b and not *a != *b; the fail is if the address is the same, not the value.
configurator
It could be either - you don't need to swap if the values are already the same. But checking (a != b) makes more sense.
Greg Rogers
+1  A: 

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.

Tim Ring
watch out: vc++ wont allow inline asm in 64bit mode. hope its relevant or understood as so :)
vilaca
+5  A: 

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.

Nir
+2  A: 

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.

Andrew O'Reilly
A: 
paperhorse
I like that evaluation! "It was faster, but it did corrupt the data." Classic.
unwind
+20  A: 

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

Skizz
+1 for the unnecessary optimization mention. If you've actually profiled your code and the biggest thing you have to worry about is which of these two ways of swapping a pair of ints is faster, you've written a very fast app. Until then, who cares about the swap?
Ken White
+1 for the Ferrari metaphor.
Mehrdad Afshari
@Ken White: I agree and moreover, if profiling shows that most time is spent in swapping it is most probably because you are swapping too many times (bubble sort anyone?), rather than swapping slowly.
David Rodríguez - dribeas
+6  A: 

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)
Harry
+1. This is the way to do it in C, when you require speed. The macro can even be made type-flexible if you use the typeof() extension offered by GNU C.
Dan
+1 . not only the function call but also the aliasing is important. the compiler cannot be sure the pointers point to different objects so it cannot cache either value
Johannes Schaub - litb
Err... Why would you use a compiler that can't do it's own inlining? Use functions when you can, macros when you must. Functions are type safe is easier to understand.Will this macro do the right thing with "swap(a++,b++)"?, will a functions?
John Nilsson
+5  A: 

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

Skizz
Your side-effect code is C++, not C (there are no references in C). C programmers don't have templated functions... which may have some type-safety but are an absolutely nightmare to parse and otherwise implement. C++ != C. They have different types and degrees of abstraction and convention.
Dan
Why do you say inlining functions result in bigger code? I learned the exact opposite in college.
Leahn Novash
+2  A: 

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.

Dan
i like your answer. it was the first thing that came to my mind. you might want to add use of "register" for c99 code, which also tells the compiler they don't alias (can be used if the programmer knows the arguments are not the same objects)
Johannes Schaub - litb
A: 

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.

Dan Cristoloveanu
+3  A: 

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.

Trevor Boyd Smith
It looks like you didn't enable optimization -- the local variables are getting loaded/stored many times in each function. Also, in modern processors, you can't easily count cycles, because anything that touches memory takes a variable number of cycles, depending on whether the cache hits or not.
Adam Rosenfield
I did enable optimization with "-o3" and I even used "restrict" keyword to ensure that the compiler will optimized. What else am I missing?---Lets say the number of cycles I counted isn't an absolute count. But I at least think it would be a relative count? So the trad. method still wins?
Trevor Boyd Smith
-o3 says "name the output file 3". You need -O3 (with a capital O).
Adam Rosenfield
On a pipelined superscalar (i.e. conteporary) CPU, you can't just count the number of instructions in the assembly code and call it "cycles".
bendin
Yes I am wrong about saying "each line is a cycle" but the intent of my post was to determine which code is "faster relative to the other" and comparing the line count of each asm listing will still show which code is faster ( even though each line is not actually "how many cycles" ).
Trevor Boyd Smith
As people have already noted in other answers, look at the numbers of memory accesses in both codes. Two `move (%edx)` and two `move (%ecx)` in the first, but three of each in the second. They are not costly (in 1st level cache) but cannot be removed in this case (pointer aliasing rule).
tristopia
A: 

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;
}
jheriko
A: 
void swap(int* a, int* b)
{
    *a = (*b - *a) + (*b = *a);
}

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

Theofanis Pantelides
-1 undefined behavior.
R..
A: 

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.

Vadakkumpadath
-1 undefined behavior
R..