Stupid Coding Tricks
During a lunch interview, my interviewer wrote the following
line of C/C++ code on a napkin:
a ^= b ^= a ^= b;
He then asked me what it does. It was a bad question. While we might expect it to swap the contents of a and b, the code
relies on the results of intermediate subexpressions. According to Stroustrup,
The C++ Programming Language (2nd
Ed.), section 6.2.2, “The order of evaluation of subexpressions within an
expression is undefined.” This is,
in fact, a hold-over from Kernighan & Ritchie’s original definition in The
C Programming Language (of which I don’t
have a copy on hand, or I’d look it up—so the exercise is left for the
reader).
It’s important to note that the compiler’s behavior is undefined as opposed to implementation defined, which means that you may well get the behavior you
expect some times, yet there will be times when the behavior is something
else. For example, Metrowerks’
compilers give the expected results when both variables are allocated in
registers, but produce a different result when the variables are allocated on the
stack.
You’ll have to ask a compiler writer to get the details of the
underlying reason for this, but it has to do with modern compiler issues like
instruction scheduling, pipelining and attempting to get two processor
instructions to execute simultaneously.
The important thing for programmers to understand is that different
behaviors for the same line of code is not
a compiler bug when the behavior is undefined.
We can resolve the undefined issue by using the comma
operator:
a
^= b, b ^= a, a ^= b;
But that doesn’t completely remove the stupidity of this
programming trick. It’s still
obscure. We could comment it
whenever we use it, but that gets tedious. One way to remove the obscurity is to use a macro:
#define
Swap(a, b) (a ^= b, b ^= a, a ^= b)
While that removes the obscurity of the code, there’s still
one more problem with it.
Compilers have advanced to the point where the use of inline functions
and global optimizations render this kind of programming trick completely
unnecessary. Worse yet, it can
actually result in slower code than if you’d been more direct in your intent.
For example, consider the C++ way of doing this:
template <typename T>
inline void Swap (T &a, T &b)
{
T
c = b;
b
= a;
a
= c;
}
The actual code generated by the Metrowerks PowerPC compiler
completely optimizes out both the call semantics and the use of any temporary
variable. In fact, the compiler
merely makes any subsequent references to the location for variable a refer to the
location that had originally been allocated for variable b, and vice-versa. As far as the generated code is
concerned, the call to the inline Swap function becomes a complete no-op.
So, not only is the XOR swap stupid because it’s obscure, it’s stupid
because, with modern optimizing compilers, the eventual result often ends up
being contrary to the intended result of using the coding trick in the first
place. The only benefit of the XOR version of
the Swap
macro is in C programs where we don’t have the benefit of templates. The Swap macro provides a type-independent
way of expressing the idea. The
price, however, would suggest that writing separate inline routines for each
integral type for which it is needed would result in smaller, and faster, code.
The moral is, before you consider using some obscure coding
trick for the sake of performance, write up some sample code, and take a look
at the actual code your compiler generates. More often than not, you’ll find that the less obscure
method results in better code.
Rick
Comments
Anonymous
March 06, 2004
You bet it's a bad question if it's C++ code, as you could have redefined operator^= to mean almost anything at all. Great tip about Metrowerks' compiler, concerning how it optimizes away the Swap().Anonymous
March 06, 2004
The comment has been removedAnonymous
March 06, 2004
"This is, in fact, a hold-over from Kernighan & Ritchie’s original definition in The C Programming Language (of which I don’t have a copy on hand, or I’d look it up—so the exercise is left for the reader)."
I have a copy at hand here, but I couldn't find it using the index. (and it's been a long time since I read in that book on a daily basis ;)).
great article btw :)Anonymous
March 06, 2004
The comment has been removedAnonymous
March 07, 2004
The comment has been removedAnonymous
March 08, 2004
The comment has been removedAnonymous
March 08, 2004
K&R2
A7.17 (p208) - All assignment operators group right-to-left.
A7 (p200) - Unless the definition of an operator guarantees that its operands are evaluated in a particular order, the implementation is free to evaluate operands in any order.
Post on subexpressions is not valid - there are no subexpressions involved. Comment on sequence points in C++ is correct, see http://www.zib.de/benger/C++/clause5.htmlAnonymous
March 08, 2004
Rick Schaut writes about stupidity of the XOR trick these days: So, not only is the XOR swap stupid because it's obscure, it's stupid because, with modern optimizing compilers, the eventual result often ends up being contrary to the intended result of using the coding trick in the first place....Anonymous
March 08, 2004
I completely and heartily agree with Don that to try and answer this question means you have missed the point. In the business arena, cleverness like that gets 20 demerits and no dessert after dinner.
Were the question posed in an academic context rather than a business one, it would be interesting to know the answer. There is a place in the world for language lawyers as well as business people.
But practical programmers have enough to worry about without trying to differentiate between compiler bug, undefined and implementation defined. Write clearly. Document concisely. Make it maintainable.Anonymous
March 14, 2004
The comment has been removedAnonymous
April 14, 2004
The comment has been removedAnonymous
June 18, 2004
The comment has been removedAnonymous
March 05, 2006
The comment has been removedAnonymous
June 13, 2009
PingBack from http://quickdietsite.info/story.php?id=4491Anonymous
June 13, 2009
PingBack from http://wheelbarrowstyle.info/story.php?id=1154