Is this XOR value swap algorithm still in use or useful

When I first started working a mainframe assembler programmer showed me how they swap two values without using the traditional algorithm of:

a = 0xBABE
b = 0xFADE

temp = a
a = b
b = temp

What they used to swap two values – from a bit to a large buffer – was:

a = 0xBABE
b = 0xFADE

a = a XOR b
b = b XOR a
a = a XOR b

now

b == 0xBABE
a == 0xFADE

which swapped the contents of 2 objects without the need for a third temp holding space.

My question is: Is this XOR swap algorithm still in use and where is it still applicable?

When using xorswap there’s a danger of supplying same variable (same memory address, not same value) as both arguments to the function which zeroes out the said variable due to it being xor‘d with itself which turns all the bits to zero. Of course this itself would result in unwanted behavior regardless of algorithm used, but the behavior might be surprising and not obvious at first glance.

Traditionally xorswap has been used for low-level implementations for swapping data between registers. In practice there are better alternatives for swapping variables in registers. For example Intel’s x86 has a XCHG instruction which swaps the contents of two registers. Many times a compiler will figure out the semantics of a such function (it swaps contents of the values passed to it) and can make its own optimizations if needed, so trying to optimize something as trivial as a swap function does not really buy you anything in practice. It’s best to use the obvious method unless there’s a proven reason why it would be inferior to say xorswap within the problem domain.

The key to the answer is in the question – “working a mainframe assembler programmer” – in the days before the compiler. When humans hunkered down with assembly instructions and hand crafted exact solutions for a particular piece of hardware (that may or may not work on another model of the same computer – issues such as the timing of hard drives and drum memory had impact on how code was written – read The Story of Mel if one feels the need to be nostalgic).

Back in these bygone days, registers and memory were both scarce and any trick to not have to beg for another byte or word of memory from the lead architect was time saved – both in writing the code and execution time.

Those days are gone. The trick of swapping two things without using a third is a trick. Memory and registers are both plentiful in modern computing and humans don’t write assembly anymore. We’ve taught all of our tricks to our compilers, and they do a better job of it than we do. Chances are the compiler did something even better than what we would have done. In most cases, sometimes we need to write assembly in some inner bit of a tight loop for some reason… but it isn’t to save a register or a word of memory.

It might be useful again if one is working in a particularly limited microcontroller, but optimizing a swap isn’t likely the source of one’s problem then – trying to be too clever is more likely a problem.

Will it work? Yes.

Should you use it? No.

This sort of micro-optimization would make sense if:

you have looked at the code the compiler generates for the straightforward way of doing this (assignment and a temporary) and decided that the XOR approach generates faster code
you have profiled your app, and found the cost of the straightforward approach outweighs the clarity of the code (and resulting savings in maintainability)

To the first point, unless you’ve done this measurement, you should be trusting the compiler. When the semantics of what you’re trying to do are clear, there are a lot of tricks the compiler can do, including rearranging variable access so that the swap is not needed at all, or in-lining whatever machine level instructions provide the fastest swap for a given data type. “Tricks” such as the XOR swap make it harder for the compiler to see what you are trying to do, and thus make it less able to apply such optimizations.

To the second point, what are you gaining for the added complexity? Even if you’ve measured and found the XOR approach faster, is this having enough impact to justify a less clear approach? How do you know?

Finally, you should look into whether there is a standard swap function for your platform/language — the C++ STL, for instance, provides a template swap function which will tend to be highly optimized for your compiler/platform.

My colleague reported that this is a base trick he has taught in university studying for a programmer of automated systems. Many such systems are embedded ones with limited resources and they could lack a free register to keep the temporary value; in that case, such tricky exchange (or its analog with adding and subtracting) is getting vital so still being used.

But one shall care using it that these two locations can’t be identical because in the latter case it will effectively zero both values. So usually it’s being limited to obvious cases like exchanging a register and a memory location.

With x86, the xchg and cmpxchg instructions satisfy the need in most cases, but RISCs generally aren’t covered with them (except Sparc).

If it makes sense to do that, then any decent compiler will be smart enough to recognise the situation and do the xor trick for you. If it doesn’t make sense, then the compiler won’t.

You will get the best results by swapping the two numbers. And it will also work for exchanging two pointers, two doubles, two arrays with 8 chars and so on, when the xor trick will be hard to use.

If you are working with distributed systems, it is plausible (although unlikely) that you may run into a memory constraint somewhere and still need to swap a variable value with another variable’s value without pointing at a third location in memory.

These days, I’d bet this is the only time where this knowledge would be useful beyond an interview question.

It will be relevant only if you

are writing in assembler
using an instruction set that does not have a native swap operation
need to be economical with registers, and the code is performance-critical enough that you can’t just push a value on the stack.

The only plausible scenario I can imagine is in code generation in a compiler backend. Compiler output is performance-critical and you want to utilize all available registers to avoid more expensive stack or memory operations.

In a high level language, the xor-swap is not useful, since you use local variables stored in memory rather than registers. Introducing a temp variable does not have notable cost, and the xor swap is likely to be slower because the xor operations would be in addition to the memory reads or writes.

In a modern language, you would just write

[a, b] = [b, a]

and let the compiler figure it out.

Filed under: softwareengineering - @ 00:31

Thẻ: algorithms

Thiết kế website giá rẻ

Danh mục

Is this XOR value swap algorithm still in use or useful