5 ms·

Behold!, as it all becomes the same thing in C++ with optimizations on: https://godbolt.org/z/joh1jhdhq https://godbolt.org/z/joh1jhdhq Good production compil

by a_e_k 5y ago

Behold!, as it all becomes the same thing in C++ with optimizations on: https://godbolt.org/z/joh1jhdhq https://godbolt.org/z/joh1jhdhq 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.

layer8 5y ago
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.
- a_e_k 5y ago
  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/9fdac7e16c940fb6264e6ddaf99c761f1a64a054/gcc/match.pd#L1492 https://github.com/gcc-mirror/gcc/blob/9fdac7e16c940fb6264e6...
- civilized 5y ago
  This is fascinating.
- tialaramex 5y ago
  Idiom recognition has been a thing in compilers for decades, so certainly don't rule it out.
sgeisenh 5y ago
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.

by a_e_k 5y ago

layer8 5y ago

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.

a_e_k 5y ago
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/9fdac7e16c940fb6264e6ddaf99c761f1a64a054/gcc/match.pd#L1492 https://github.com/gcc-mirror/gcc/blob/9fdac7e16c940fb6264e6...
civilized 5y ago
This is fascinating.
tialaramex 5y ago
Idiom recognition has been a thing in compilers for decades, so certainly don't rule it out.

sgeisenh 5y ago

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.