[SOLVED]C/C++: Advantages and disadvantages to swap functions?

Google · 2011-05-01 08:39:02

I was reading about some interview questions developers often get asked. One of the questions was writing a simple swap function to swap 2 variables. I assume these questions are for languages like C or C++, because this isn't a problem in Perl or similar languages.

I came up with 3 functions to swap 2 variables.

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

// fails if a == b? 
void bitwise_swap(int *a, int *b){
  *a ^= *b;
  *b ^= *a;
  *a ^= *b;
}

// overhead of creating a new variable?
void swap(int *a, int *b){
  int temp;
  temp = *b;
  *b = *a;
  *a = temp;
}

// feels awkward, adding variables together means reducing max possible size?
void awkward_swap(int *a, int *b){
  *a += *b;
  *b = *a - *b;
  *a = *a - *b;
}

int main(){
  int *a = malloc(sizeof(int));
  int *b = malloc(sizeof(int));
  *a = 10;
  *b = 20;

  // bitwise_swap(a, b);
  // swap(a, b);
  awkward_swap(a, b);
  printf("A:%d\nB:%d\n", *a, *b);

  return 0;
}

It seems to me like the 3 variable swap function is the safest-- it doesn't reduce the max possible size of ints that can be handled. It also doesn't fail if the two variables are equal.

What are your thoughts? Have an alternative?

Last edited by Google (2011-05-06 18:48:23)

Pajaro · 2011-05-01 09:36:04

Unless the context has some special needs I use the 3 variable swap function by default.

Zeist · 2011-05-01 12:00:19

Since the XOR swap needs a check that may cause a branch in your code and the adding swap is only useful if you have extreme memory constraints but aren't worried about overfilling a variable I would say the three variable swap is the most useful one.

There is also std::swap if you are using C++ which at least causes easy to read code, but the assembly efficiency varies a bit depending on compilers.

You could also do this if you are using GCC (found it in a GCC reference book at some point, is faster than anything else I've tried from my benchmarks, not portable to other compilers without some changes):

void asm_swap(int &val1, int &val2)
{
       asm("":"=g"(val1), "=g"(val2):"1"(val1), "0"(val2));
}

draugdel · 2011-05-01 12:01:44

Why should the bitwise_swap fail with equal values?

a = xor(15,15) = 0
b = xor(15,0) = 15
a = xor(0,15) = 15

Zeist · 2011-05-01 14:50:53

draugdel wrote:

Why should the bitwise_swap fail with equal values?
a = xor(15,15) = 0
b = xor(15,0) = 15
a = xor(0,15) = 15

I guess I failed to explain correctly, the problem is not with if the values are the same, but rather that it will fail if you are using two pointers to the same place in memory.

Then the flow would be:
a = xor(a,a);
a = xor(a,a);
a = xor(a,a);

Which will always turn out as 0 after the first row.

I also forgot to add that with modern compilers' assembly generation using the three variable swap is actually faster than the XOR swap due to that the XOR solution has to be sequential.

The thing I would find most interesting as an employer is clean easily readable code though... which the XOR swap definitely isn't.

Google · 2011-05-01 15:03:39

Thanks-- the asm swap is cool. I didn't know about the c++ swap so that's new to me.

I think in the event of a job interview I will use the 3 variable swap and explain there are alternatives with advantages and disadvantages but the 3 variable swap is most readable and fairly efficient.

draugdel · 2011-05-01 15:32:07

Zeist wrote:

draugdel wrote:
Why should the bitwise_swap fail with equal values?
a = xor(15,15) = 0
b = xor(15,0) = 15
a = xor(0,15) = 15
I guess I failed to explain correctly, the problem is not with if the values are the same, but rather that it will fail if you are using two pointers to the same place in memory.
Then the flow would be:
a = xor(a,a);
a = xor(a,a);
a = xor(a,a);
Which will always turn out as 0 after the first row.
I also forgot to add that with modern compilers' assembly generation using the three variable swap is actually faster than the XOR swap due to that the XOR solution has to be sequential.
The thing I would find most interesting as an employer is clean easily readable code though... which the XOR swap definitely isn't.

Ah, that´s of course correct.

tavianator · 2011-05-01 22:06:57

As a general rule, gcc is smarter at optimizing than you are, so just write 3-variable swaps and they'll get converted into an xchg or possibly a no-op if the registers can be renamed. In C++, use std::swap (actually, the pattern is "using std::swap; swap(a, b);").

stqn · 2011-05-02 13:38:58

I wouldn't call malloc() for 4 bytes allocations unless there's no other choice.

Google · 2011-05-02 13:44:22

It was just for testing the functions. I had ran a bunch of different functions earlier.

The 3 variable swap does seem like the best swap for most situations. I hadn't considered how the compiler would optimize it.

akb825 · 2011-05-03 04:20:29

tavianator wrote:

As a general rule, gcc is smarter at optimizing than you are, so just write 3-variable swaps and they'll get converted into an xchg or possibly a no-op if the registers can be renamed. In C++, use std::swap (actually, the pattern is "using std::swap; swap(a, b);").

Why not just do "std::swap(a, b);" instead of writing extra code just to import it into the global namespace?

Using std::swap in C++ is definitely desirable. It is implemented differently for the STL data structures so swapping doesn't allocate extra memory. Otherwise, if you did the naive 3-variable method you would make a total of 3 unnecessary deep copies of the data structures you're swapping. You can overload swap for more efficient implementations for your own data types as well.

stqn wrote:

I wouldn't call malloc() for 4 bytes allocations unless there's no other choice.

To expand on this, your main function should look like this:

int main(){
  int a = 10;
  int b = 20;

  // bitwise_swap(&a, &b);
  // swap(&a, &b);
  awkward_swap(&a, &b);
  printf("A:%d\nB:%d\n", a, b);

  return 0;
}

Also, your original code was leaking both a and b.

stqn · 2011-05-03 14:00:40

akb825 wrote:

Also, your original code was leaking both a and b.

I didn't even notice that... Though to be fair, most (all?) implementations will automatically free malloc()ed memory at exit.

Like the use of malloc() instead of simple local variables, it's not a big deal in a short test program like this, but if the interviewer is a good programmer, he/she will notice this and be afraid to see similar code in bigger projects.

More nitpicking:

In C code one should write "int main(void)".

In C++ code, on the other hand, it might be a good idea to use new instead of malloc(), cout instead of printf(), and references for the parameters of swap(). While none of these suggestions are mandatory, they are more "C++ style" and would show more knowledge about the language.

Google · 2011-05-03 15:44:46

Ahh the interview didn't require any kind of main program. I just threw it in quickly to test my functions when I got home. I wanted to make sure I didn't mess up my swap function logic.

The interview just asked to write the function-- I ran home later and wrote that quickly to test and then got curious what others thought so posted.

I know I should have freed before ending and it's a good idea to void a function argument list in plain C (C++ assumes an empty list is void but C doesn't).

One thing I didn't know is about the C++ swap function-- that is new to me. C++ is a little new to me, I am still learning a lot. I feel like every time I pick up C++ books I learn something new. The language is huge. I am not sure I understand the difference between using a "using" declaration and not using one?

I have always preferred to write the full scope out myself. Is there an actual performance difference while using the using declaration?

edit:

I see using imports the entire namespace-- and thus uses more memory. Besides that is there any difference?

Last edited by Google (2011-05-03 15:46:59)

tavianator · 2011-05-03 15:50:58

akb825 wrote:

tavianator wrote:
As a general rule, gcc is smarter at optimizing than you are, so just write 3-variable swaps and they'll get converted into an xchg or possibly a no-op if the registers can be renamed. In C++, use std::swap (actually, the pattern is "using std::swap; swap(a, b);").
Why not just do "std::swap(a, b);" instead of writing extra code just to import it into the global namespace?

Have a look at Effective C++ by Scott Meyers.

"using std::swap; swap(a, b);" doesn't necessarily call std::swap, especially if the type of a or b exists in a namespace that has its own swap() function.

Cerebral · 2011-05-03 17:45:16

stqn wrote:

I didn't even notice that... Though to be fair, most (all?) implementations will automatically free malloc()ed memory at exit.

This has nothing to do with the compiler/runtime implementation, and everything to do with the operating system. When a program exits, the OS is responsible for cleaning up and releasing its entire memory space.

stqn · 2011-05-03 18:19:05

Cerebral wrote:

This has nothing to do with the compiler/runtime implementation, and everything to do with the operating system. When a program exits, the OS is responsible for cleaning up and releasing its entire memory space.

The C runtime frees memory allocated with malloc() at exit, not the OS.

However if you used an operating system specific function to allocate something, then it would (maybe) be freed by the OS, yes. (Some operating systems don't have resource tracking, e.g. AmigaOS.)

Edit: ok, maybe I'm wrong, and only *some* C runtime implementations free memory allocated with malloc() at exit... I was sure about this, but this dates back to when I was programming on the Amiga/MorphOS. It makes sense that a C runtime shouldn't need to bother freeing memory if the OS is going to do it anyway.

Last edited by stqn (2011-05-03 18:26:08)

akb825 · 2011-05-05 04:42:11

Google wrote:

I see using imports the entire namespace-- and thus uses more memory. Besides that is there any difference?

First, calling "using std;" would import the entire namespace, but calling "using std::swap;" only imports swap.

Second, importing symbols into a namespace does not use any more memory. These are all compile time decisions and make absolutely no runtime difference. The compiler might use more memory when compiling your program, but the difference would be trivial, and it has no effect on your compiled program.

tavianator wrote:

Have a look at Effective C++ by Scott Meyers.
"using std::swap; swap(a, b);" doesn't necessarily call std::swap, especially if the type of a or b exists in a namespace that has its own swap() function."

That is a good point. However, for that I would rather declare or import my free swap functions in the std namespace so it's consistent with all the other swappable types, plus it makes the call site simpler.

stqn wrote:

Like the use of malloc() instead of simple local variables, it's not a big deal in a short test program like this, but if the interviewer is a good programmer, he/she will notice this and be afraid to see similar code in bigger projects.

Agreed. If I were giving the interview, these both would stand out as major strikes against overall code quality. I would also doubt if you truly understand pointers, as to me that code implies you think only memory on the heap can a pointer. Keep in mind that in interviews a lot of the questions will be relatively simple, but all the details of your response will be looked at, so you need to pay attention to details such as these.

As for allocated memory on exit, it is true that the OS should release those resources for you. However, it is still good practice to not have memory leaks on exit, as it makes it more difficult to track true memory leaks in your code.

Google · 2011-05-05 15:06:46

I suppose this is better-- getting rid of malloc alltogether?

#include <stdio.h>

void bitwise_swap(int *a, int *b);

void swap(int *a, int *b);

void awkward_swap(int *a, int *b);


int main(void){
  int a, b;

  a = 10;
  b = 20;

  // bitwise_swap(&a, &b);
  swap(&a, &b);
  // awkward_swap(&a, &b);

  printf("A:%d\nB:%d\n", a, b);

  return 0;
}


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

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

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

tavianator · 2011-05-05 15:34:15

akb825 wrote:

tavianator wrote:
Have a look at Effective C++ by Scott Meyers.
"using std::swap; swap(a, b);" doesn't necessarily call std::swap, especially if the type of a or b exists in a namespace that has its own swap() function."
That is a good point. However, for that I would rather declare or import my free swap functions in the std namespace so it's consistent with all the other swappable types, plus it makes the call site simpler.

Be careful here; adding things to the std namespace technically invokes undefined behaviour. It's okay to specialize std::swap though, but that doesn't work in some cases, like if you want to swap variables of different types.

bnolsen · 2011-05-05 18:56:34

Google wrote:

I was reading about some interview questions developers often get asked. One of the questions was writing a simple swap function to swap 2 variables. I assume these questions are for languages like C or C++, because this isn't a problem in Perl or similar languages.

I guess I might be offended by this sort of question at an interview. I've worked with enough coders that obsess over instruction level optimization and have no friggin clue how to write clear methodical modular code using smart algorithms.

Addiitonally it is important to understand things like "construct in place" (you get this right you dont' have to worry so much about c++0x "move" semantics), etc.

I guess the biggest problem for employers is trying to figure out who's going to contribute positively and who's going ton contrinbute negatively.

akb825 · 2011-05-06 03:17:44

Google wrote:

I suppose this is better-- getting rid of malloc alltogether?

Yes, that is much better.

tavianator wrote:

Be careful here; adding things to the std namespace technically invokes undefined behaviour. It's okay to specialize std::swap though, but that doesn't work in some cases, like if you want to swap variables of different types.

How is it undefined? I suppose that std could have other identifiers in different implementations, so you generally don't want to pollute it with your own, but if you're overloading (or specializing, if you choose) a function like swap for a type that you know won't be in std, it should be perfectly fine.

Last edited by akb825 (2011-05-06 03:18:10)

Cerebral · 2011-05-06 11:38:38

akb825 wrote:

tavianator wrote:
Be careful here; adding things to the std namespace technically invokes undefined behaviour. It's okay to specialize std::swap though, but that doesn't work in some cases, like if you want to swap variables of different types.
How is it undefined? I suppose that std could have other identifiers in different implementations, so you generally don't want to pollute it with your own

Because the C++ standard says so - the std:: namespace is reserved for the implementation, and any user code that puts things in std:: is technically invoking undefined behaviour. I imagine in 99% of cases it'll work fine, but the spec makes no guarantees - compilers are free to do whatever they want to stuff you put in std:: and it'll still be "C++-compliant".

akb825 wrote:

but if you're overloading (or specializing, if you choose) a function like swap for a type that you know won't be in std, it should be perfectly fine.

Again, as he mentioned, specializing std::swap is fine, but std::swap is really only templated over a single param, so you can only specialize it to swap two objects of the same type. If you need to swap two objects of different types, you'll need to write your own 'swap' (which isn't specializing std::swap), and adding this new one to the std namespace is undefined.

Google · 2011-05-06 18:48:51

I marked solved-- but feel free to keep talking about it. It has been an interesting read guys! Thanks~

akb825 · 2011-05-07 03:12:47

Cerebral wrote:

akb825 wrote:
tavianator wrote:
Be careful here; adding things to the std namespace technically invokes undefined behaviour. It's okay to specialize std::swap though, but that doesn't work in some cases, like if you want to swap variables of different types.
How is it undefined? I suppose that std could have other identifiers in different implementations, so you generally don't want to pollute it with your own
Because the C++ standard says so - the std:: namespace is reserved for the implementation, and any user code that puts things in std:: is technically invoking undefined behaviour. I imagine in 99% of cases it'll work fine, but the spec makes no guarantees - compilers are free to do whatever they want to stuff you put in std:: and it'll still be "C++-compliant".

I see. So overloading is out to be 100% complaint, but at least you can still specialize if you don't need to swap two different types.

Cerebral wrote:

akb825 wrote:
but if you're overloading (or specializing, if you choose) a function like swap for a type that you know won't be in std, it should be perfectly fine.
Again, as he mentioned, specializing std::swap is fine, but std::swap is really only templated over a single param, so you can only specialize it to swap two objects of the same type. If you need to swap two objects of different types, you'll need to write your own 'swap' (which isn't specializing std::swap), and adding this new one to the std namespace is undefined.

True, but you could also define a swap function in a separate namespace, and have the default version call std::swap. That way you only use one function, which is overloaded and/or specialized, for all swaps. However, I would imagine that needing to swap two variables of a different type would be very rare.

Arch Linux

#1 2011-05-01 08:39:02

[SOLVED]C/C++: Advantages and disadvantages to swap functions?

#2 2011-05-01 09:36:04

Re: [SOLVED]C/C++: Advantages and disadvantages to swap functions?

#3 2011-05-01 12:00:19

Re: [SOLVED]C/C++: Advantages and disadvantages to swap functions?

#4 2011-05-01 12:01:44

Re: [SOLVED]C/C++: Advantages and disadvantages to swap functions?

#5 2011-05-01 14:50:53

Re: [SOLVED]C/C++: Advantages and disadvantages to swap functions?

#6 2011-05-01 15:03:39

Re: [SOLVED]C/C++: Advantages and disadvantages to swap functions?

#7 2011-05-01 15:32:07

Re: [SOLVED]C/C++: Advantages and disadvantages to swap functions?

#8 2011-05-01 22:06:57

Re: [SOLVED]C/C++: Advantages and disadvantages to swap functions?

#9 2011-05-02 13:38:58

Re: [SOLVED]C/C++: Advantages and disadvantages to swap functions?

#10 2011-05-02 13:44:22

Re: [SOLVED]C/C++: Advantages and disadvantages to swap functions?

#11 2011-05-03 04:20:29

Re: [SOLVED]C/C++: Advantages and disadvantages to swap functions?

#12 2011-05-03 14:00:40

Re: [SOLVED]C/C++: Advantages and disadvantages to swap functions?

#13 2011-05-03 15:44:46

Re: [SOLVED]C/C++: Advantages and disadvantages to swap functions?

#14 2011-05-03 15:50:58

Re: [SOLVED]C/C++: Advantages and disadvantages to swap functions?

#15 2011-05-03 17:45:16

Re: [SOLVED]C/C++: Advantages and disadvantages to swap functions?

#16 2011-05-03 18:19:05

Re: [SOLVED]C/C++: Advantages and disadvantages to swap functions?

#17 2011-05-05 04:42:11

Re: [SOLVED]C/C++: Advantages and disadvantages to swap functions?

#18 2011-05-05 15:06:46

Re: [SOLVED]C/C++: Advantages and disadvantages to swap functions?

#19 2011-05-05 15:34:15

Re: [SOLVED]C/C++: Advantages and disadvantages to swap functions?

#20 2011-05-05 18:56:34

Re: [SOLVED]C/C++: Advantages and disadvantages to swap functions?

#21 2011-05-06 03:17:44

Re: [SOLVED]C/C++: Advantages and disadvantages to swap functions?

#22 2011-05-06 11:38:38

Re: [SOLVED]C/C++: Advantages and disadvantages to swap functions?

#23 2011-05-06 18:48:51

Re: [SOLVED]C/C++: Advantages and disadvantages to swap functions?

#24 2011-05-07 03:12:47

Re: [SOLVED]C/C++: Advantages and disadvantages to swap functions?

Board footer