Those who have dabbled with x86 assembly will know that this is pretty much the standard to set a register to zero. Code is peppered with the likes of 'xor eax, eax'.
It begs a question though: How many instructions in <insert ISA here> are equivalent? I assume that a compiler writer has a list of equivalents and will typically choose the shorter one?
There are a number of considerations there. Size is only one of them. Speed and internal processor state effects are two others. For instance, a larger, slower instruction might prevent a pipeline stall in a particular function or might enable loop unrolling or might allow a shorter loop unrolling, while in a similar function that doesn’t pipeline the same way, the compiler will choose a faster instruction.
The only issue is that for RISC, all these instructions are of equal length, so flipping them around would gain you very little, or more likely zero effect unless you are chasing some corner case thing like "XOR instruction value compresses slightly better than ADD because.."
Well that 0 that you are loading comes from the instruction, so it is already "there". It boils down to the fact that the instruction is sorter.
In fact in theory the load is slower, because XOR has data dependencies on the arguments. So an out-of-order processor could be delayed. However x86 has special logic that XOR with itself doesn't carry any dependencies on the arguments.
In addition to other concerns, processors usually treat xor specially since it was the best way to zero things for so long that it became ubiquitous. Often its performance impacts are equivalent to a noop.
The “missing integer” example is awkward, because what’s interesting here is not whether you can solve the problem with xor or plus, but whether you need two loops or just one. Edit: I guess overflow is one consideration, as mentioned in the article.
Warning: if x == y, then instead of swapping, the two values are set to zero.
So this swapping trick works only for x!=y.
---------
The other tricks are interesting, and likely hold the key to some kind of parallel programming trick, as a sequence of XORs is trivially parallelizable through the prefix-sum pattern.
All of the other tricks are O(n) number of XOR operations, while parallel prefix-sum is O(log(n)) depth and O(n) total work.
My favorite application is comparing vectors. Example in C++:
// Compare 32 bytes for equality, with 2 AVX2 instructions
inline bool equals( __m256i a, __m256i b )
{
// When the vectors are equal, their XOR is completely zero..
__m256i xx = _mm256_xor_si256( a, b );
// ..and there's a special instruction to test the complete vector for zero
return (bool)_mm256_testz_si256( xx, xx );
}
It took me a minute to figure out the last step of the final example since the author doesn’t quite spell it out. So for anyone else who’s feeling a little slow:
Once you’ve partitioned the search space into “values where the ith bit is 0” and “values where the ith bit is 1” (for example, even and odd values if it happens to be the least significant bit), then you can simply iterate through all the input values and xor together all the values where the ith bit is 0, then xor those with all possible values where the ith bit is 0, and you’ve found one of the missing values. Repeat the process with 1 instead of 0 to find the other.
Nitpick: I think the trick(s) also depend on XOR being associative.
Are there any more complex applications of this, especially if you generalize it to any operator that obeys the necessary properties? I'm curious if there's any sort of interesting data structures you can build, probably building on commutative monoids where x `mappend` x == mempty for all x (the generalization of x^x == 0).
20 comments
[ 1.9 ms ] story [ 58.1 ms ] threadThose who have dabbled with x86 assembly will know that this is pretty much the standard to set a register to zero. Code is peppered with the likes of 'xor eax, eax'.
That 0 has to come from somewhere, while in the other case XORing a register with itself does not involve loading any data. It's also shorter.
ADD Reg0 to Reg0 and store result in Rx
OR Reg0 with reg0 and store result in Rx
XOR Reg0 with reg0 and ..
The only issue is that for RISC, all these instructions are of equal length, so flipping them around would gain you very little, or more likely zero effect unless you are chasing some corner case thing like "XOR instruction value compresses slightly better than ADD because.."
In fact in theory the load is slower, because XOR has data dependencies on the arguments. So an out-of-order processor could be delayed. However x86 has special logic that XOR with itself doesn't carry any dependencies on the arguments.
Warning: if x == y, then instead of swapping, the two values are set to zero.
So this swapping trick works only for x!=y.
---------
The other tricks are interesting, and likely hold the key to some kind of parallel programming trick, as a sequence of XORs is trivially parallelizable through the prefix-sum pattern.
All of the other tricks are O(n) number of XOR operations, while parallel prefix-sum is O(log(n)) depth and O(n) total work.
Huh, what?
The issue is:
The issue is *aliasing*. If the pointer &x == &y, then everything goes to crap. When the pointers alias to themselves, the function degenerates into: Which sets x (and the y value) to zero.In contrast:
This always works, even with aliasing.Once you’ve partitioned the search space into “values where the ith bit is 0” and “values where the ith bit is 1” (for example, even and odd values if it happens to be the least significant bit), then you can simply iterate through all the input values and xor together all the values where the ith bit is 0, then xor those with all possible values where the ith bit is 0, and you’ve found one of the missing values. Repeat the process with 1 instead of 0 to find the other.
Are there any more complex applications of this, especially if you generalize it to any operator that obeys the necessary properties? I'm curious if there's any sort of interesting data structures you can build, probably building on commutative monoids where x `mappend` x == mempty for all x (the generalization of x^x == 0).