Code Challenge

[Raj]

Observe the code snippet:

int a, b;
a = 10;
b = 20;
Console.WriteLine("Before Swapping a="+a+" b="+b);
a = a + b;
b = a - b;
a = a - b;
Console.WriteLine("After Swapping a=" + a + " b=" + b);
Console.Read();

I have written the above piece of code to swap value of variables without
using a third variable to consume less memory.

I would like to have a debate on the above is it really consuming less
memory and improves performance?

Thank you

Regards
Raj

 

[Tom Spink]

Observe the code snippet:

int a, b;
a = 10;
b = 20;
Console.WriteLine("Before Swapping a="+a+" b="+b);
a = a + b;
b = a - b;
a = a - b;
Console.WriteLine("After Swapping a=" + a + " b=" + b);
Console.Read();

I have written the above piece of code to swap value of variables without
using a third variable to consume less memory.

I would like to have a debate on the above is it really consuming less
memory and improves performance?

Thank you

Regards
Raj

Raj, the code you have written for swapping without a temporary
variable is traditionally coded with the XOR operator:

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

This is because additions and subtractions may cause integer overflows,
therefore in some cases will not work. Try your code when:

a = int.MaxValue;
b = int.MinValue;

See this document for more information:
http://en.wikipedia.org/wiki/XOR_swap_algorithm

Pay particular attention to the two sections: "Reasons for use in
practice" and "Reasons for avoidance in practice".

 

[Peter Duniho]

Observe the code snippet:

int a, b;
a = 10;
b = 20;
Console.WriteLine("Before Swapping a="+a+" b="+b);
a = a + b;
b = a - b;
a = a - b;
Console.WriteLine("After Swapping a=" + a + " b=" + b);
Console.Read();

I have written the above piece of code to swap value of variables without
using a third variable to consume less memory.

I would like to have a debate on the above is it really consuming less
memory and improves performance?

I think "debate" might be pushing things a bit. I don't think there's
that much worth debating, or even much controversy available in the
question.

The technique you show is not unheard of, though I think typically one
would use xor rather than addition and subtraction.

Does it consume less memory? I guess that depends on what you mean by
"memory". In an optimized build, the JIT compiler is (I think) very
likely to implement a conventional swap without an actual local variable;
instead, the temporary storage may wind up in a register, or (if at least
one of the operands has already been optimized into a register) the
compiler might even emit an XCHG instruction (on x86...other platforms
might have a similar instruction).

So I'd say, no...your version won't _necessarily_ use less memory. But it
might (and on an unoptimized build, probably would), depending on a
variety of factors.

As for performance, that's even harder to predict. Lots of things can
affect the performance of various implementations of data swapping.
However, it would be highly unlikely for the performance difference, if
any, to be significant enough to justify writing the obfuscated version.
And if anything, optimized output of a conventional swap might actually be
faster.

Also, consider that the conventional swap code, using a temporary storage
location, is a pattern that an optimizing compiler would probably detect,
while the alternatives are not. So, once you code a swap using the
alternative, you're probably locked into whatever performance
characteristics that results in. On the other hand, using the
conventional code your code will take advantage of whatever improvements a
compiler might be able to provide as it or the platform evolves.

Frankly, for swapping values, none of this is likely to matter much at
all, including the question of allowing the compiler to improve over
time. It'd be pretty unusual code where the act of swapping two values is
a large proportion of the total execution time anyway.

But, it's an important lesson to generalize: the kind of
micro-optimization you're asking about is almost never the right way to
write the code. It makes the code harder to maintain and makes it more
difficult (or impossible) for the compiler to generate truly optimized
code.

Remember Knuth's classic statement: "...premature optimization is the root
of all evil". You should write your code in the clearest, simplest, most
easily provably-correct way first. If and when you find a performance
problem, _then_ you can look at potential optimizations, and in that
context you can easily determine empirically whether one version of the
code works better than the other (whether that be with respect to memory
usage, speed of execution, both, or some other metric altogether).

Pete

 

[Tom Spink]

This is because additions and subtractions may cause integer overflows,
therefore in some cases will not work. Try your code when:

a = int.MaxValue;
b = int.MinValue;

I was a little too quick off the mark here. I, of course, meant:

a = int.MaxValue;
b = int.MaxValue;

However, bizarrely, you'll see that the code does work - and this is
because of the runtime's implementation of arithmetic operations.

 

[Peter Duniho]

[...]
This is because additions and subtractions may cause integer overflows,
therefore in some cases will not work. Try your code when:

a = int.MaxValue;
b = int.MinValue;

For what it's worth, as long as the code isn't compiled as "checked",
overflow shouldn't be an issue:

a = int.MaxValue; // a = 0x7ffffffff
b = int.MinValue; // b = 0x800000000
a = a + b; // a = 0xffffffff
b = a - b; // b = 0x7fffffff
a = a - b; // a = 0x80000000

I mean, yes...some of the computations may overflow, resulting in a
carry. But the overflow is ignored and the bit patterns wind up working
out correctly.

Obviously, this is highly dependent on the specific environment. But in
C#, it should be "fine" (ignoring all the other good reasons to not swap
variables that way ).

Pete

 

[Peter Duniho]

I was a little too quick off the mark here. I, of course, meant:

a = int.MaxValue;
b = int.MaxValue;

Your previous example was fine too. The last operation does overflow in
that case.

However, bizarrely, you'll see that the code does work - and this is
because of the runtime's implementation of arithmetic operations.

It's not that bizarre. It's an inherent aspect of the 2's complement
representation.

Pete

 

[Tom Spink]

Hi Pete,

I mean, yes...some of the computations may overflow, resulting in a
carry. But the overflow is ignored and the bit patterns wind up working
out correctly.

Obviously, this is highly dependent on the specific environment. But in
C#, it should be "fine" (ignoring all the other good reasons to not swap
variables that way ).

Absolutely, I totally agree.

I was going to write that, but I got distracted and hit Ctrl+S to save
my message - but that in fact sends the message.

 

[Tim Roberts]

Observe the code snippet:

int a, b;
a = 10;
b = 20;
Console.WriteLine("Before Swapping a="+a+" b="+b);
a = a + b;
b = a - b;
a = a - b;
Console.WriteLine("After Swapping a=" + a + " b=" + b);
Console.Read();

I have written the above piece of code to swap value of variables without
using a third variable to consume less memory.

I would like to have a debate on the above is it really consuming less
memory and improves performance?

I wanted to add one more note to the other very good responses you have
received.

Remember that the compiler is not merely translating your program line by
line. It's looking at the overall structure of your functions, monitoring
the whole data flow. For example, let's say we have this traditional swap
implemention:

int tmp = a;
a = b;
b = tmp;

The compiler does more than just remember that a certain piece of memory is
called "a". The compiler also knows what "a" contains. It is quite likely
that an optimizing compiler will generate no code for this AT ALL. Instead,
in the rest of the function, where you refer to "b", it will simply
generate code to use the register or memory in which the value of "a" had
previously been stored.