Stupid Coding Tricks



Stupid Coding Tricks

During a lunch interview, my interviewer wrote the following
line of C/C++ code on a napkin:

 

a ^= b ^= a ^= b; style='font-family:Garamond'>

 

He then asked me what it does.  It was a bad question.  While we might expect it to swap the contents of class=code>a and class=code>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 style='font-style:normal'> as opposed to implementation defined style='font-style:normal'>, 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 class=code>a refer to the
location that had originally been allocated for variable style='font-family:"Courier New"'>b, and vice-versa. style="mso-spacerun: yes">  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 class=code>XOR version of
the Swap
macro is in C programs where we don’t have the benefit of templates. style="mso-spacerun: yes">  The style='font-family:"Courier New"'>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 (16)

  1. rentzsch says:

    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().

  2. Don says:

    I read this post just before going to bed, and I found I was so irritated by the question that I had to get back up and respond to it.

    I’m teaching my son about gun safety using a BB gun. We don’t spend a lot of time covering topics like "What is the difference between getting shot in the eye when you are wearing polycarbonate safety goggles vs. getting shot in the eye when you are wearing conventional tempered lenses." The point is to understand that your primary responsibility when you hold a gun is to control when and at what it fires. If questions about the subtleties of eyewear matter, you have already failed.

    I don’t want to know the answer to the interviewer’s question, nor do I want anyone who works for me to know the answer. Anyone who knows the answer might be tempted to try to make use of the technique at some point in their career. There is no reason why that line of code ever needs to come near a compiler. Don’t write it. Ever. Don’t even think about writing it. If you see it in legacy code, fire the person who wrote it (because it probably doesn’t do what they thought it did anyway), research the behavior (if you need to match it), and most importantly get it out of your code base.

    Every interview works in two directions. If someone asked me your interviewer’s question, it is unlikely that they could ever convince me to work for them. The type of person who believes that knowing the answer to that question is a useful measure of engineering ability has no understanding of what engineering is or why it matters. While it is always important to understand the limits of validity of the standard solutions to any problem, and to understand how the systems behave as you exceed those limits, the purpose is not to understand what happens when you get shot in the eye while wearing polycarbonate safety glasses. The purpose is to understand how to not shoot someone in the eye.

  3. Frans Bouma says:

    "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 🙂

  4. Richard Schaut writes about an appallingly stupid interview question — asking the candidate to explain what this line of code…

  5. Roi says:

    The rule you quote about subexpressions does not apply to assignments. Assignments always associate right to left. (It’s already on p. 21 of K&R).

    I find it a perfectly fine interview question for a hardcore C programmer. It might be less relevant for other types of programmers.

  6. Dima Volodin says:

    The code example is invalid as it is in a direct violation of [expr], paragraph 4:

    Between the previous

    and next sequence point a scalar object shall have its stored value modified at most once by the evaluation

    of an expression.

  7. Dennis Atkins says:

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

  8. 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….

  9. Steve says:

    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.

  10. The question of whether the interviewer’s Question is bad / good is irrelavent when you are trying to answer a Question in an Interview. Like Steve said, there will be a place for arguers and business ppl to spend on even a single line of code like this.

    You must practice in any of the two ways in answering a interview question. One is to frame out the answer that is very convincing to the expectation of the interviewer (you must try to figure out how the question has been framed, and try to read the mind of the interviewer). The other is not to openly convey whatever you just found something stressy to you. You should rather convey the normal answer that 80% or more would tell at first. (This is becuase most questions are not made by single ppl, rather atleast discussed with one person. There will be a temptation for the asker to refer to atleast one person as to how this question is. He would have got critisism or a good/bad remark or even an answer that will makes any questioner to accept more than one possible answers).

    As said, intelligence doesnt gets its merit. It also depends on what type of interview you were attending. Its not at all neccessary for you to critisize / publish a question (stupid enough for you) and make an arguement with other ppl. I bet you still havent figured out whats the expectation of the interviewer. Its not neccessary that you should show your programming skills in a question thats asked by some one else. I good programmer knows what is required when and where.

    Anyway Best of luck to all those who would get benefitted with this article. Just remember you have to convince the asker for the time and show your skills and argue to him back ( humbly 🙂 ) after you were a staff there, not as a job-seeker.

  11. Rob Terrell says:

    This must have been fifteen years ago, but…I had a job interview at Davinci (remember them? Of Davinci Email, king of all email until Microsoft decided email mattered?) as a Mac programmer for a new Mac email client. I’d developed a couple of then-shipping Mac apps. The first couple of interviews went well, but after lunch, my interviewer pulled out the previous years’ winners in the obfuscated C contest and asked me to tell him what each line would do.

    Since I’m not a C compiler, I was completely unable to do more than a "well, it deferences a pointer here, it increments here, prints a value here…hmmm…" kind of answer.

    I could not believe they were making hiring decisions in this way. Did they *want* obfusctaed C in their code? That sounds like fun to maintain. Let alone debug. Every line of code, a new puzzle! Every new compiler, a new result!

    I didn’t get the job. Presumably they hired someone who could figure out the obfuscated C better than me, but I was happy to note that they never shipped their Mac client. However, I developed and shipped plenty of Mac software in the job I got in my next interview.

  12. AMSR says:

    Hah, funny you should mention this question. I got this question recently on an interview with Intel. The interviewer seemed thoroughly pissed that I couldn’t quite articulate what the line did. Needless to say, I answered all the other technical questions right, but couldn’t quite figure out what the point of this one was….

  13. Richard Schaut writes about an appallingly stupid interview question — asking the candidate to explain what this line of code…