2

I read on a site that using xor swaps is fast because it doesn't use a temporary variable. Here's an example:

#include <stdio.h>

int main(void)
{        
    int a=234,b=789;
    b=b^a;
    a=b^a;
    b=b^a;
    printf("a=%d,b=%d",a,b);
    return 0;
}

Why don't people use this technique in real life code? Is it just poor style? Is there something not well defined about it? Is it an optimisation that my compiler might produce from more clear code, automatically?

Wooble
  • 87,717
  • 12
  • 108
  • 131
autistic
  • 1
  • 3
  • 35
  • 80
  • 3
    I doubt there's much evidence that it's faster very often (if ever). – Michael Burr May 14 '13 at 05:08
  • http://stackoverflow.com/faq#dontask – xaxxon May 14 '13 at 05:30
  • 1
    @xaxxon Which part of that page are you trying to alert me to? – autistic May 14 '13 at 05:48
  • 1
    Chatty, open-ended questions diminish the usefulness of our site and push other questions off the front page. – xaxxon May 14 '13 at 05:49
  • 1
    All of the questions I asked have straight-forward answers, and most of them are closed questions that only require "yes" or "no" answers. This question **is** constructive because it may very well encourage future visitors to use more portable approaches than the xor swap. I don't think you'll get this question closed on those grounds. Even if you do, I'll have it reopened quite quickly ;) – autistic May 14 '13 at 05:56
  • @PaulR How can I improve this question? – autistic May 14 '13 at 06:45
  • @talonmies Please explain why a question that confronts undefined behaviour, a question that could discourage students from using non-portable code (such as xor swaps) if it gets enough focus, is deemed as *not constructive*. – autistic May 14 '13 at 06:51
  • 2
    I think as soon as you said "Why don't people..." you're offtopic for stackoverflow. Also, asking about style trends you outside stack overflow's core mission. This type of question belongs on a blog somewhere, and I'm pretty sure it's not really a question. You already know the answer, you're semi-trolling to get answers to what you think are common issues answered on stackoverflow, but stackoverflow specifically doesn't believe they belong here. I really think you should start a programming blog and post this kind of stuff there. – xaxxon May 14 '13 at 06:54
  • 1
    Again, stack overflow has a clearly defined purpose and it's written specifically as something different than what you seem to want it to be. According to the FAQ, "Chatty, open-ended questions diminish the usefulness of our site and push other questions off the front page." Stack overflow wants technical, objectively-answerable questions to get the attentino they deserve, and as you can see, based on what's going on right now, this kind of question detracts from that. – xaxxon May 14 '13 at 06:54
  • Ways you could ask semi-related questions that would be a better fit are: How does gcc vX.Y.Z on x86 Linux optimize a variable swap using a temporary variable? Or "Does this specific code guarantee defined behavior across all platforms to the C99 spec?" But I don't think that's going to make you happy. – xaxxon May 14 '13 at 06:58
  • @xaxxon Have you learnt about undefined behaviour, yet? Style is only a minor factor here. You can't preach in favour of C99 if you don't know what undefined behaviour is. Do you see how I mentioned "not well defined" in my question? Find out what that means, and then tell me this is "open-ended" or "non-constructive". Tell me that nobody values portability! I dare you! – autistic May 14 '13 at 11:10

4 Answers4

23

Using a tmp variable is both faster and more readable with modern compilers and CPUs. 2x loads into registers, then 2x stores back into the original locations.

Or if one or both variables were already in registers, the compiler might completely optimize anyway the temporary. If xor-swapping was faster on some hypothetical machine, a good compiler would use it for you when optimizing tmp = a; a = b; b = tmp; So you don't need to write it explicitly. This is why you're using C, not writing by hand in asm.

Also, xor-swap works for integers only. What if you want to swap floating-point numbers? Strings? Custom objects? etc.

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
  • That just about covers it. To expand upon this: The compiler will do a better job at optimising the swap in point 2 than a xor swap; Often that'll be translated to just one instruction (or sometimes zero, because the order instructions might be swapped instead) while the xor swap is still three. Furthermore, there are poorly defined aspects of xor swaps; They might produce the wrong result or trap representations, particularly when negative numbers are used... Not to mention focusing on this *optimisation* is silly; There will probably be far more significant ones identified by profiling. – autistic May 14 '13 at 05:27
  • It doesn't only work for integers. It has no concept of the data you're swapping, unless you say that all binary data is an integer. XOR swap trick works for any two things of the same size. For example, this works just fine for swapping floating point numbers. – xaxxon May 14 '13 at 05:28
  • @undefinedbehaviour For that, [this SO question and answer](http://stackoverflow.com/questions/11644362/bitwise-operation-on-signed-integer) is a good read. –  May 14 '13 at 05:29
  • @xaxxon But type punning is UB, no matter what. –  May 14 '13 at 05:29
  • I don't know what type punning or UB mean – xaxxon May 14 '13 at 05:30
  • 1
    @xaxxon Yet you are insisting that my answer's wrong. That's the problem. –  May 14 '13 at 05:32
  • 1
    @xaxxon Consider what might happen if there are padding bits, or a negative zero trap representation. Section 6.5p5 of n1570.pdf (the C11 standard draft) says: If an exceptional condition occurs during the evaluation of an expression (that is, if the result is not mathematically defined or not in the range of representable values for its type), the behavior is undefined. – autistic May 14 '13 at 05:33
  • @xaxxon Those are not "made up words". [Type punning](http://en.wikipedia.org/wiki/Type_punning), [Undefined Behavior](http://en.wikipedia.org/wiki/Undefined_behavior#Examples_in_C_and_C.2B.2B). –  May 14 '13 at 05:34
  • 1
    Anyhow, it's in no way limited to any particular type of data. It will swap any two equal length binary representations. – xaxxon May 14 '13 at 05:36
  • @xaxxon ...causing undefined behavior in certain situations, for sure it will. –  May 14 '13 at 05:37
  • Is it undefined for floats? If so, why? (serious question) – xaxxon May 14 '13 at 05:39
  • 2
    @xaxxon As far as I know, `^` can only operate on integral types, `floatA & floatB` is a compiler error, so you would have to do something like `*(int *)&floatA ^ *(int *)&floatB`, which breaks the [strict aliasing rule](http://stackoverflow.com/questions/98650/what-is-the-strict-aliasing-rule). –  May 14 '13 at 05:41
  • http://msdn.microsoft.com/en-us/library/3akey979.aspx it appears that ^ is only for integral types. Now to look at strict aliasing rule. – xaxxon May 14 '13 at 05:46
6

All answers are already there consider it just an addition-

->if both values goes for same memory address-result will be zero

->compilers can optimize away the temporary variable in the naive swap

->modern CPUs strive to execute instructions in parallel via instruction pipelines but with XOR technique is considerably slower than using a temporary variable to do swapping because each operation depends on the result of previous

->x+Y may go for integer overflow

Dayal rai
  • 6,548
  • 22
  • 29
3

  1. While there is no explicit temporary variable, the results are actually stored in an implicit temp variable before being written to the register.

  2. With xor swap, you need to ensure that the variables being swapped aren't same. Else both shall be evaluated to 0.

xaxxon
  • 19,189
  • 5
  • 50
  • 80
devnull
  • 118,548
  • 33
  • 236
  • 227
  • For #2: good point. For #1: How do you know? Have you looked at the code generated by every compiler in the world? –  May 14 '13 at 05:12
  • Is `a ^ a` supposed to be compiler dependent? – devnull May 14 '13 at 05:18
  • No. Look at the ordinal numbers in my comment - they are not #1 and #2 but #2 and #1. –  May 14 '13 at 05:20
  • 6
    #2 is incorrect. If a == b, the values will remain the same. – Mike Woolf May 14 '13 at 05:20
  • @MikeWoolf: You've made an incomplete point. If `a=b` to begin with, then you'll end up with `a=b=0`. – devnull May 14 '13 at 05:29
  • 1
    @devnull: nope. b will be set to 0. Then a will be set to 0^a, which is a. Then b will be set to b^a, which is still a. – Mike Woolf May 14 '13 at 05:34
  • 5
    I think #2 is referring to the exact same memory space, not just the same value, but I'm not sure. – xaxxon May 14 '13 at 05:53
  • 3
    if, as @xaxxon suggests, in the exceptional situation where `a` and `b` somehow exists at the same address (not readily do-able in standard C as `ints`), the result is that `b` will become 0 after the first `b=b^a;` and at the end `a` and `b` will be 0. This exceptional situation applies for the `tmp = a; a = b; b = tmp;` too should addresses be shared. But in this code example, a & b and in separate locations and `a` and `b` will swap just fine given any initial values. – chux - Reinstate Monica May 29 '13 at 17:28
  • 2
    The #2 scenario is more likely to occur in a function where pointed-to objects are being swapped. – M.M Nov 26 '15 at 01:48
1

The performance gain is typically so small that the cost to "understandable code" is higher than the speed benefit obtained.

John3136
  • 28,809
  • 4
  • 51
  • 69
  • The performance gained is actually non-existent. The compiler will take care of all this for you -- in fact the more "normal" your code works, the better job the compiler can do. And the compiler is better at optimizing for your platform than you are. – xaxxon May 14 '13 at 05:32
  • 1
    The compiler is only better at optimizing if you don't know assembly. – Devolus May 14 '13 at 06:41
  • Even so, chances are the compiler will beat you more often than not. These things are pretty damn smart. – tangrs May 14 '13 at 07:14
  • 1
    In most cases little "optimisations" like this won't save you a noticable amount of time. Stick with readable code over trying to be smarter than the compiler. – John3136 May 14 '13 at 07:20
  • @John3136: I agree that the gain in such a small sequence is non-existent. For longer sequences well-written (not too different from readable) code serves up an optimization scenario that the compiler can do a really good job with. There isn't much the compiler can do with poor code (garbage in=garbage out) and the result is slow code. Consequently good code means good speed. – Olof Forshell Sep 03 '13 at 21:49
  • 1
    @Devolus It's as simple as knowing assembly; you also need to know intricate details regarding the implementation, and have an eye for detail that is outrageously fine. Compilers can eliminate dead code at the drop of a pin, millions of lines of it per second. Humans can't. Compilers can integrate with profilers to produce more cache-friendly code, and though humans can (and will achieve better optimisation as a result), it takes a lot longer... – autistic Jul 29 '15 at 01:08