Hacker News Reader

Comment by a_e_k | Hacker News Reader

Behold!, as it all becomes the same thing in C++ with optimizations on:

Good production compilers recognize all these swap idioms and will compile them down (i.e., canonicalize them) to the same thing. In the case of things like swapping by adding and xoring, they'll often undo the cleverness and just use temporary registers anyway. These are the kinds of micro-optimizations that compilers excel at, so write the code clearly, leave that job to them, and worry about the high-level stuff that the compiler can't do for you.

View on HN

I don’t think the compilers recognize the specific idiom here, but instead (what you also say) perform normalizations (e.g. into static single assignment form), expression analysis and elimination, yielding the same result. For the present case, I’d imagine a sequence of transformations like this:

Convert into SSA:

    c = a + b;
    d = c - b;
    e = c - d;
    b’ = d;
    a’ = e;

Eliminate c:

    d = a + b - b;
    e = a + b - d;
    b’ = d;
    a’ = e;

Simplify d:

    d = a;
    e = a + b - d;
    b’ = d;
    a’ = e;

Eliminate dependency of e on d:

    d = a;
    e = a + b - a;
    b’ = d;
    a’ = e;

Simplify e:

    d = a;
    e = b;
    b’ = d;
    a’ = e;

Eliminate d:

    e = b;
    b’ = a;
    a’ = e;

…resulting in the normal swap.

True; I probably overstated it in terms of idiom recognition (compiler enthusiast, but by no means expert). I suspect that a similar SSA or data flow analysis combined with some judicious rewrite rules like (X ^ Y) ^ Y -> X [0] are enough for the xor swap trick as well.

[0] https://github.com/gcc-mirror/gcc/blob/9fdac7e16c940fb6264e6...

This is fascinating.

Idiom recognition has been a thing in compilers for decades, so certainly don't rule it out.

This example is kind of funny in a compiled language because a lot of modern compilers use a static single assignment (SSA) form as an intermediate representation. SSA effectively creates temporaries for each subsequent assignment operation. This helps with data-flow analysis but also makes it so that code like in the post can actually be less space efficient without optimizations in compiled languages.

Reply on news.ycombinator.com