5 ms·
The code from the Wikipedia article for XOR swapping [1] checks if the values are equal. void XorSwap(int *x, int *y) { if (x != y) { *x ^= *y;
by azhenley 6y ago
The code from the Wikipedia article for XOR swapping [1] checks if the values are equal.
void XorSwap(int *x, int *y) {
if (x != y) {
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
}
[1] https://en.wikipedia.org/wiki/XOR_swap_algorithm https://en.wikipedia.org/wiki/XOR_swap_algorithm
- wongarsu 6y agoAt that point it's probably almost always better to just use some temporary space, rather than dealing with all the overhead of a branch (what if it's mispredicted, what about the resources in the branch predictor tied up by this that might cause something else to be mispredicted). On the other hand there are many situations where you can guarantee that x and y are not the same space in memory (for example because they are local variables). There this trick might still be interesting (for the compiler or assembly programmer)
- Someone 6y agoIf they’re local variables, the compiler may not need to generate any code for a swap. It could do the equivalent of register renaming (https://en.wikipedia.org/wiki/Register_renaming https://en.wikipedia.org/wiki/Register_renaming)
- saagarjha 6y agoAnd if your compiler can't do it, your hardware might.
- Snild 6y agoThe xor swap truck is rarely better. It causes pipeline stalls, and so is likely to be significantly slower than the trivial swap. The temporary storage will be in a register, so it's (usually) not causing memory accesses.
- Taniwha 6y agoYeah exactly this, it only really makes sense in some very limited situations in embedded software, for example when you might be in an interior handler and have no free registers
- mhh__ 6y agoOn top of that, the CPU can literally elide movs at runtime so the whole swap could end up being zero latency depending on the code motion
- FabHK 6y ago> checks if the values are equal Not the values (the values being equal doesn't break the trick), but the pointers. That is, if you use the XOR trick to swap a value with itself, then it will be set to zero, instead. As if you had written: x ^= x x ^= x x ^= x Yeah, now x would be zero, not itself.
- deleted 6y ago[deleted]
- voldacar 6y agoWouldnt the extra branch kill any performance improvement you were getting from the xor trick?
- ChrisRR 6y agoAs with every performance optimisation, it's better to test and profile rather than to assume