Xor swap trick and add/sub swap trick (2010) | Hacker News Reader

Xor swap trick and add/sub swap trick (2010)

cottonvibes.blogspot.com

29 pointssillysaurusx54 comments

Article is from 2010 so not going to quibble about there having been a lot of history since then, but from the end:

> especially since floating point operations are generally compiled to use the x87 fpu (so the floats will be moved back into gprs, and end up being slower than a regular swap)

gcc, at least, will use SSE rather than x87 by default on 64-bit x86. Looking at godbolt there's still a bunch of conversions that come out to about the same number of instructions, although I suspect doing it with SSE is probably faster than doing it with x87. Doing it with a temporary variable instead rather than coercing through a series of casts is probably even faster, though.

Also probably excusable because 2010, but from that same part of the article:

    void swap(int& x, int& y);

    void swap(float& x, float& y) {
        swap((int&)x, (int&)y);
    }

This is UB and may explode. Probably the only portable way to do it is a memcpy() [1].

[1] https://blog.regehr.org/archives/959

C compilers should really refuse to compile code that does blatant type punning like this. Is there a book out there that is teaching people this is okay? Everything I’ve ever learned about C/C++ has explicitly warned against type punning.

Well, reality is many real world projects depend on it. Eg linux, disables strict aliasing. IMO the strict aliasing rule is a mistake, people know how the code should behave, so it should behave as expected.

> MO the strict aliasing rule is a mistake, people know how the code should behave, so it should behave as expected.

The strict aliasing rule exists because without it a C compiler has to second guess every load and store, which would have been horribly slow in the 80s and would be even worse now. It still ends up doing that for distinct pointers with the same type, which is why you can explicitly restrict them in newer language versions so the compiler can assume that those pointers wont alias.

Well the linux ptoject does just fine without strict aliasing based optimisations. Pretty much everything on windows is built with msvc, which doesn't depend on strict aliasing for optimisation either.

Linux also depends on GCC or compilers that share its behavior w.r.t. type aliasing.

Low level embedded begs to differ

EDIT: the example below is valid, but it neither swaps the pointers, nor does it avoid extra registers/stack usage; and there is no way to use Unions to achieve this, even in C, as calling `swapI(&(((union swappable*)x)->i), &(((union swappable*)y)->i))` is UB.

The best way to do this in C (NOT C++) would be with unions, assuming you know the size of int and float for your platform.

The following would be valid C:

  union swappable{
    float f;
    int i;
  }

  void swapF(float* x, float* y) {
    swappable xs, ys;
    xs.f = *x;
    ys.f = *y;
    swapI(&xs.i, &ys.i);
  }

Given that they are using overloaded functions though, we're in C++ land where there is no correct way to achieve it (or maybe you could with char*, as that is allowed to alias?).

The best way to do this in C++ is using std::bit_cast, which unfortunately only became available in C++20. Before that, you have to memcpy. That works just fine, but the syntax is a bit clunky and it doesn’t work in constexpr contexts, which is why std::bit_cast was introduced.

Compilers will optimize all of this to the same machine code.

Interesting... I thought for sure that would be undefined behaviour like in C++, but apparently it has been defined since C99: https://en.cppreference.com/w/c/language/union

That code doesn't even swap the floats.

Apparently you can do it with xnor too, which I didn't actually realise when I made this username.

Yep, and all the solutions that treat bits independently are some combination of xor/xnor/not/identity. They can't get very long (certainly no more than 23 operations) without repeating some pair of numbers, hence being trivially reducible. The two shortest solutions are pure xor or pure xnor, so in some sense any not operations are also extraneous.

https://graphics.stanford.edu/~seander/bithacks.html

One of the Underhanded C contestants used this trick, obviously intentionally admitting &x == &y. Hitting this edge case triggered the desired "underhanded" behavior of the program.

Here: http://www.underhanded-c.org/_page_id_16.html

Why dont all languages have the inplace swap built in like python has?

In python you can just do: y, x = x, y

It only makes sense to swap elements of an arrays (lists). Swapping variable is super rare. I can't recall the same time I had to swap two integers/floats or even object references.

You're right! I was surprised. I did:

  ag '(^|[^a-zA-Z0-9=])([a-zA-Z_][a-zA-Z0-9_]*), ?([a-zA-Z_][a-zA-Z0-9_]*) ?= ?\3, ?\2'

across several Python code bases I've worked on, and indeed found very few examples.

Here's one from Python's statistics.py:

        X, Y = self, other
        if (Y._sigma, Y._mu) < (X._sigma, X._mu):   # sort to assure commutativity
            X, Y = Y, X

NumPy has only one match that isn't in test code, in numpy/core/numeric.py:convolve

    if (len(v) > len(a)):
        a, v = v, a

It's a bit more common in SciPy, like scipy/linalg/blas.py:_get_funcs which has:

    if prefer_fortran:
        module1, module2 = module2, module1

but even then, there are only 26 relevant matches across 421KLoC.

  > ag '(^|[^a-zA-Z0-9=])([a-zA-Z_][a-zA-Z0-9_]*), ?([a-zA-Z_][a-zA-Z0-9_]*) ?= ?\3, ?\2'

Why are you checking `(^|[^a-zA-Z0-9=])` before the first variable? Why are you storing it? Wouldn't `^\s*` (beginning of line, then 0 or more whitespace, not stored) be simpler? I ask to learn, not critically.

The exclusion test is to reduce false positives like:

  return open(filename, mode, encoding=encoding, errors=errors)
                           ^^^^^^^^^^^^^^^^^^^^^^^

This case matches because of the under-caret'ed

  e, encoding=encoding, e

You are right that requiring only leading whitespace would be clearer. I didn't think of it. I only wanted to eliminate those false positives I was seeing with my original test, which only had \2, \1.

In thinking more about it, your whitespace-only gives a false negative for constructs like:

  progressbar/widgets.py:306: if not self.fill_left: rpad, lpad = lpad, rpad
  matplotlib/lib/matplotlib/widgets.py:1093: if vmin>vmax: vmin, vmax = vmax, vmin

The reason I stored \1 was simply to get the grouping. I didn't recall the syntax for non-capturing groups, and it wasn't worthwhile to look up.

I see, thank you. Targeting the if statements, but not the open() methods, is an interesting corner case that I would not have though about.

I did mine because I thought some people might write it:

  (a, b) = (b, a)

so the grouping stands out better. Turns out I didn't find any examples of that.

It's a bit more common in C when swapping pointers, since it can help you ensure that there's only one pointer to a given structure at any time, and it can simplify memory management in certain cases by letting you repurpose an existing allocation.

Interestingly checking the implementation of this[0], it uses two temporary variables rather the commonly one.

[0]:https://stackoverflow.com/a/62038590/1308965

Because few languages have the ability to create a tuple with syntactic sugar on the fly that Python has. In PHP, you can similarly do the following:

> list($a, $b) = [$b, $a];

Which is a bit more verbose than what Python does, but it's the same thing under the hood - you create a list/tuple, create a new list with swapped items at specific indices and then dissolve that list back to local variables.

In the end, this is more expensive than the swap you'd do in C++^W other languages (EDIT: apparently C++ can also do this now), since it involves tuple creation. Although the compiler/JIT/interpreter will most likely recognize this pattern and optimize it to a `swap` call.

C++ can do multiple assignment now, fyi.

Since PHP 7.1 you can write

  [$a, $b] = [$b, $a];

Lots of newer languages can, like go and rust.

BTW it's not "creating a tuple with syntactic sugar on the fly", I mean, if you think that's creating a tuple, obviously in lots of languages, that tuple is created by passing x/y's value, assigning to that anonymous tuple won't affect original x/y.

The correct term should be destructuring assignment.

It's called destructuring assignment, it's not just for "in-place swap", and more over, it's about syntax, not performance.

That article is talking about performance, and as many have pointed out, it's better just use a 3rd variable(when there's no destructuring assignment) to swap and let compiler do its work.

I'm not saying syntax sugar is a bad thing.

Or, express directly what you intended and let the compiler and library do it:

e.g. https://doc.rust-lang.org/core/mem/fn.swap.html

This is old, cute, but simply slow and a really bad idea on modern hardware.

> slow and a really bad idea on modern hardware.

say more?

care to elaborate? It's just 3 instructions.

On a modern x86 cpu the ‘xchg’ instruction performs a swap and can do so entirely in the front-end via register renaming. It doesn’t even require a micro-op. This ‘trick’ actually requires executing micro-ops and creates an unnecessary data dependency (which is actually worse than the micro-ops themselves).

Better to just use more variables and let the register allocator in the compiler decide what to do. If it’s a loop then unrolling it once could remove the need for any swapping at all, for example.

I'd also hazard that throwing in an if statement in place of a temporary variable is a bad idea.

> On a modern x86 cpu the ‘xchg’ instruction performs a swap and can do so entirely in the front-end via register renaming. It doesn’t even require a micro-op.

This is only true for AMD cpus, on Intel xchg is 3 uops. Still better than the xor trick, though.

Source: https://www.uops.info/html-instr/XCHG_R64_R64.html

What if you want to swap two large memory blocks? Should be doable in a maximally cache-fridendly way with SIMD XORs I think.

> What if you want to swap two large memory blocks?

In theory, maybe.

But if that happens in your application and is performance critical, you probably should change it such that you're swapping pointers to them instead...

There are very real cases where you may want to swap around actual memory though. Gabage collectors do quite a lot of this type of large memory exhanges.

this isn't going to be any better than just loading from the two buffers into registers then storing the other way around, like:

  a = load(ap)
  b = load(bp)
  store(ap, b)
  store(bp, a)
  ap += step; bp += step;

any instructions to "do the swap" are a waste because generally load-store are separate instructions in SIMD instruction sets (and even if that wasn't the case, that's how they would get executed anyway)

if you want to avoid polluting the cache there are SSE instructions for loading without caching, which might be worthwhile

edit: this might be useful in a SIMD context where you need to swap two registers, where the cost of using another register is higher than the cost of the 3 arithmetic instructions. i could totally imagine that happening, but it's nothing to do with caches or memory

That's an old trick that, IMHO, makes no practical sense at all. Unless you are in tight long running loop that needs to swaps several pair of values, the advantage of the trick is rather tiny with the extra disadvantage of portability and readability.

Watch your steps! The swap with floats relies on sizeof( float ) == sizeof( int ) which could not always be the case. Yes, you can create a set of macros and conditional compilation stanzas to cope with that and cover also char, short, long, long long, double and long double.

Finally, the explanation on why it works would be a great supplement to the article.

And as far as I can see the assert() should have been if(x==y) return(0).

Use the temporary variable swap and let the compiler detect what you're doing and optimize it away if it can.

A similar old trick that both swaps x with y and negates y:

  x -= y   // x-y, y
  y += x   // x-y, x
  x -= y   //  -y, x

If (x, y) represents a 2d vector this operation rotates the vector counterclockwise 90°.

doesn't work with floats, due to NaN, infinity

Why treat x == y as an error instead of just returning success immediately without doing any other work?

The better way to deal with having to swap two items is to ensure they end up in the right spot in the first place. Seeing a 'swap' is usually a sign of something being wrong a bit upstream.

What about inside the implementation of a sorting routine? Or the move assign operator of a smart pointer? There are plenty of legitimate reasons to swap variables, not everyone is making a crud app.

When implementing a sorting routine the typical 'swap' operation is two loads and stores from memory, and the order of the loads and stores is what effects the swap, you don't typically do swap-in-place with memory.

99.9% of the time swaps are done for a reason, usually when sorting or manipulating linked lists pointers, but - for example - comes into play also when you want to transpose a matrix in place, or other similar algorithms.

I guess you can make an argument that the best way to get an array sorted is to have the array already sorted, but that sounds as "the best way to calculate the length of the hypotenuse is to just measure the hypotenuse, and Pythagoras never realized it was a problem upstream".

Of course swaps are done 'for a reason'. But this is an implementation detail for a swap, one where the xor trick is used to be able to swap 'in place' without using a third variable to perform the swap, and that screams 'register constraints'. To get into that situation is the mistake, not to get clever to use an xor swap to get you back out of it. In any other situation that realistically speaking would occur such constraints would not normally exist.

In a sorting algorithm, if the XOR swap (or any other trick) is faster, that seems a valid use case. The constraint being “this sort library should be correct first and as fast as possible second.”

I've implemented lots of sorting algorithms and have never found the XOR trick useful or faster. The main use was on very register constrained 8 bit machines but I haven't programmed on anything like that in assembly for years.

Still, it's a neat trick.

Reply on news.ycombinator.com