▲ 231 points
back
216 comments
XOR is a simple logic-gate operation. SUB would have to be an ALU operation.
A one-bit adder (which is subtraction in reverse) makes signals pass through two gates.
See https://en.wikipedia.org/wiki/Adder_(electronics)
You need the 2 gates for adding/subtracting because you care about carry. So if you're adding/subtracting 8 bits, 16 bits, or more, you're connecting multiples of these together, and that carry has to ripple through all the rest of the gates one-by-one. It can't be paralellized without extra circuitry, which increases your costs in other ways.
Without the AND gate needed for carry, all the XORs can fire off at the same time. If you added the extra circuitry for a parallelizable add/subtract to make it as fast as XOR, your actual parallel XOR would consume less power.
That's all true, but on any modern x86 processor both the single pair of gates for the xor and the 10 or so for a carry-bypass 64 bit wide subtraction both happen with a single clock cycle of latency so from a programmer's perspective they're the same in that sense. There's still an energy difference but its tiny compared to what even the register file and bypass network for the operation use, let along the OoO structures.
It's still the same number of clock cycles, though, isn't it? You're using some extra circuitry during the SUB, but during the XOR, that circuitry is just sitting idle anyway, so it's still six of one/half a dozen of the other.
That was what I guessed too, but according to the article Intel detected both.
Except ALUs share hardware with logic functions.
Internally the adder (which is also used as a subtractor by ones complementing one of the inputs and inverting the initial carry in) uses xor, and you can implement the XOR logic op with the same gates.
Also, modern ALUs don't use ripple carries really any more, but instead stuff like a Kogge-Stone adder (or really, typically a hierarchical set of different techniques). https://en.wikipedia.org/wiki/Kogge%E2%80%93Stone_adder
On some of IBM's smaller processors, such as channel controllers and the CSP used in the midrange line prior to the System/38, the xor instruction had a special feature when used with identical source and destination - It would inhibit parity and/or ECC error checking on the read cycle, which meant that xor could be used to clear a register or memory location that had been stored with bad parity without taking a machine check or processor check.
Interesting, since the general culture at IBM seems to have preferred SUB over XOR -- their earlier business-oriented machines didn't even have a XOR instruction, and even on later ones the use of SUB has persisted, including in the IBM PC and AT BIOS.
(There was another, now deleted, comment somewhere in this thread that mentioned IBM's preference for SUB. Source of that statement was Claude, but it seems very likely to be correct. The BIOS code I've checked myself, lots of 'SUB AX,AX', no XOR)
"Bonus bonus chatter: The xor trick doesn’t work for Itanium because mathematical operations don’t reset the NaT bit. Fortunately, Itanium also has a dedicated zero register, so you don’t need this trick. You can just move zero into your desired destination."
Will remember for the next time I write asm for Itanium!
Quite a few architectures have a dedicated 0 register.
It would probably run really fast, considering that Itanium's downfall was the difficulty in compiling. (Including translating x86 instructions into Itanium instructions)
The obvious answer is that XOR is faster. To do a subtract, you have to propagate the carry bit from the least-significant bit to the most-significant bit. In XOR you don't have to do that because the output of every bit is independent of the other adjacent bits.
Probably, there are ALU pipeline designs where you don't pay an explicit penalty. But not all, and so XOR is faster.
Surely, someone as awesome as Raymond Chen knows that. The answer is so obvious and basic I must be missing something myself?
> To do a subtract, you have to propagate the carry bit from the least-significant bit to the most-significant bit.
Yes, but that need not scale linearly with the number of bits. https://en.wikipedia.org/wiki/Carry-lookahead_adder:
“A carry-lookahead adder (CLA) or fast adder is a type of electronics adder used in digital logic. A carry-lookahead adder […] can be contrasted with the simpler, but usually slower, ripple-carry adder (RCA), for which the carry bit is calculated alongside the sum bit, and each stage must wait until the previous carry bit has been calculated to begin calculating its own sum bit and carry bit. The carry-lookahead adder calculates one or more carry bits before the sum, which reduces the wait time to calculate the result of the larger-value bits of the adder.
[…]
Already in the mid-1800s, Charles Babbage recognized the performance penalty imposed by the ripple-carry used in his difference engine, and subsequently designed mechanisms for anticipating carriage for his never-built analytical engine.[1][2] Konrad Zuse is thought to have implemented the first carry-lookahead adder in his 1930s binary mechanical computer, the Zuse Z1.”
I think most, if not all, current ALUs implement such adders.
His point is that in x86 there is no performance difference but everyone except his colleague/friend uses xor, while sub actually leaves cleaner flags behind. So he suspects its some kind of social convention selected at random and then propagated via spurious arguments in support (or that it “looks cooler” as a bit of a term of art).
It could also be as a result of most people working in assembly being aware of the properties of logic gates, so they carry the understanding that under the hood it might somehow be better.
That comment is not very useful without pointing to realworld CPUs where SUB is more expensive than XOR ;)
E.g. on Z80 and 6502 both have the same cycle count.
> The answer is so obvious
A tangent, but what is Obvious depends on what you know.
Often experts don't explain the things they think are Obvious, but those things are only Obvious to them, because they are the expert.
We should all kind, and explain also the Obvious things those who do not know.
As TFA says, on x86 `sub eax, eax` encodes to the same number of bytes and executes in the same number of cycles.
XOR is faster when you do that alone in an FPGA or in an ASIC.
When you do XOR together with many other operations in an ALU (arithmetic-logical unit), the speed is determined by the slowest operation, so the speed of any faster operation does not matter.
This means that in almost all CPUs XOR and addition and subtraction have the same speed, despite the fact that XOR could be done faster.
In a modern pipelined CPU, the clock frequency is normally chosen so that a 64-bit addition can be done in 1 clock cycle, when including all the overheads caused by registers, multiplexers and other circuitry outside the ALU stages.
Operations more complex than 64-bit addition/subtraction have a latency greater than 1 clock cycle, even if one such operation can be initiated every clock cycle in one of the execution pipelines.
The operations less complex than 64-bit addition/subtraction, like XOR, are still executed in 1 clock cycle, so they do not have any speed advantage.
There have existed so-called superpipelined CPUs, where the clock frequency is increased, so that even addition/subtraction has a latency of 2 or more clock cycles.
Only in superpipelined CPUs it would be possible to have a XOR instruction that is faster than subtraction, but I do not know if this has ever been implemented in a real superpipelined CPU, because it could complicate the execution pipeline for negligible performance improvements.
Initially superpipelining was promoted by DEC as a supposedly better alternative to the superscalar processors promoted by IBM. However, later superpipelining was abandoned, because the superscalar approach provides better energy efficiency for the same performance. (I.e. even if for a few years it was thought that a Speed Demon beats a Brainiac, eventually it was proven that a Brainiac beats a Speed Demon, like shown in the Apple CPUs)
While mainstream CPUs do not use superpipelining, there have been some relatively recent IBM POWER CPUs that were superpipelined, but for a different reason than originally proposed. Those POWER CPUs were intended for having good performance only in multi-threaded workloads when using SMT, and not in single-thread applications. So by running simultaneous threads on the same ALU the multi-cycle latency of addition/subtraction was masked. This technique allowed IBM a simpler implementation of a CPU intended to run at 5 GHz or more, by degrading only the single-thread performance, without affecting the SMT performance. Because this would not have provided any advantage when using SMT, I assume that in those POWER CPUs XOR was not made faster than subtraction, even if this would have theoretically been possible.
From TFA:
The predominance of these idioms as a way to zero out a register led Intel to add special xor r, r-detection and sub r, r-detection in the instruction decoding front-end and rename the destination to an internal zero register, bypassing the execution of the instruction entirely.
I'm not actually aware of any CPUs that preform a XOR faster than a SUB. And more importantly, they have identical timings on the 8086, which is where this pattern comes from.
There's a structure called a carry-bypass adder[1] that lets you add two numbers in O(√n) time for only O(n) gates. That or a similar structure is what modern CPUs use and they allow you two add two numbers in a single clock cycle which is all you care about from a software perspective.
There are also tree adders which add in O(log(n)) time but use O(n^2) gates if you really need the speed, but AFAIK nobody actually does need to.
XOR and SUB have had identical cycle counts and latencies since the 8088. That's because you can "look ahead" when doing carries in binary. It's just a matter of how much floorspace on the chip you want to use.
https://en.wikipedia.org/wiki/Carry-lookahead_adder
The only minor difference between the two on x86, really, is SUB sets OF and CF according to the result while XOR always clears them.
I had a similar reaction when learning 8086 assembly and finding the correct way to do `if x==y` was a CMP instruction which performed a subtraction and set only the flags. (The book had a section with all the branch instructions to use for a variety of comparison operators.) I think I spent a few minutes experimenting with XOR to see if I could fashion a compare-two-values-and-branch macro that avoided any subtraction.
Relatedly, there's a steganographic opportunity to hide info in machine code by using "XOR rax,rax" for a "zero" and "SUB rax,rax" for a "one" in your executable. Shouldn't be too hard to add a compiler feature to allow you to specify the string you want encoded into its output.
Back when I was in university, one of the units touching Assembly[0] required students to use subtraction to zero out the register instead of using the move instruction (which also worked), as it used fewer cycles.
I looked it up afterwards and xor was also a valid instruction in that architecture to zero out a register, and used even fewer cycles than the subtraction method; but it was not listed in the subset of the assembly language instructions we were allowed to use for that unit. I suspect that it was deemed a bit off-topic, since you would need to explain what the mathematical XOR operation was (if you didn't already learn about it in other units), when the unit was about something else entirely- but everyone knows what subtraction is, and that subtracting a number by itself leads to zero.
[0] Not x86, I do not recall the exact architecture.
It amazes me how entertaining Raymond's writing on most mundane aspects of computing often is.
It might be because XOR is rarely (in terms of static count, dynamically it surely appears a lot in some hot loops) used for anything else, so it is easier to spot and identify as "special" if you are writing manual assembly.
Looking at some random 1989 Zenith 386SX bios written in assembly so purely programmer preferences:
8 'sub al, al', 14 'sub ah, ah', 3 'sub ax, ax'
26 'xor al, al', 43 'xor ah, ah', 3 'xor ax, ax'
edit: checked a 2010 bios and not a single 'sub x, x'
> but xor took a slightly lead due to some fluke, perhaps because it felt more “clever”.
Absolutely. But I can also imagine that it feels more like something that should be more efficient, because it's "a bit hack" rather than arithmetic. After all, it avoids all the "data dependencies" (carries, never mind the ALU is clocked to allow time for that regardless)!
I imagine that a similar feeling is behind XOR swap.
> Once an instruction has an edge, even if only extremely slight, that’s enough to tip the scales and rally everyone to that side.
Network effects are much older than social media, then....
I ran into this rabbithole while writing an x86-64 asm rewriter.
xor was the default zeroing idiom.I onkly did sub reg,reg when I actually want its flags result. Otherwise the main rule is: do not touch either form unless flags liveness makes the rewrite obviously safe. Had about 40 such idioms for the passes.
Once an instruction has an edge, even if only extremely slight, that’s enough to tip the scales and rally everyone to that side.
I vaguely remember we used the XOR trick on processors other than Intel, so it may not be Intel-specific.
In principle, sub requires 4 steps:
1. Move both operands to the ALU
2. Invert second operand (twos complement convert)
3. Add (which internally is just XOR plus carry propagate)
4. Move result to proper result register.
This is absolutely not how modern processors do it in practice; there are many shortcuts, but at least with pure XOR you don't need twos complement conversion or carry propagation.
Source: Wrote microcode at work a million years ago when designing a GPU.
Back in the early 1980s I leveled up my self taught Z80 assembly skills by reading a book that attempted to disassemble and explain the Sinclair Spectrum ROM.
I remember the very first ROM instruction was XOR A and this was already a revelation to me as I'd never considered doing anything other than LD A,0 to clear the accumulator.
It should be noted that XOR is just (bitwise) subtraction modulo 2.
There are many kinds of SUB instructions in the x86-64 ISA, which do subtraction modulo 2^64, modulo 2^32, modulo 2^16 or modulo 2^8.
To produce a null result, any kind of subtraction can be used, and XOR is just a particular case of subtraction, it is not a different kind of operation.
Unlike for bigger moduli, when operations are done modulo 2 addition and subtraction are the same, so XOR can be used for either addition modulo 2 or subtraction modulo 2.
SUB has higher latency than XOR on some Intel CPUs:
latency (L) and throughput (T) measurements from the InstLatx64 project (https://github.com/InstLatx64/InstLatx64) :
| GenuineIntel | ArrowLake_08_LC | SUB r64, r64 | L: 0.26ns= 1.00c | T: 0.03ns= 0.135c |
| GenuineIntel | ArrowLake_08_LC | XOR r64, r64 | L: 0.03ns= 0.13c | T: 0.03ns= 0.133c |
| GenuineIntel | GoldmontPlus | SUB r64, r64 | L: 0.67ns= 1.0 c | T: 0.22ns= 0.33 c |
| GenuineIntel | GoldmontPlus | XOR r64, r64 | L: 0.22ns= 0.3 c | T: 0.22ns= 0.33 c |
| GenuineIntel | Denverton | SUB r64, r64 | L: 0.50ns= 1.0 c | T: 0.17ns= 0.33 c |
| GenuineIntel | Denverton | XOR r64, r64 | L: 0.17ns= 0.3 c | T: 0.17ns= 0.33 c |
I use the carry flag in a lot of z80 assembly for communicating a status of an operation. XOR doesn’t mess with the carry flag, I think it’s another point in favor of xor. (Though I don’t remember even considering using sub)
The hw implementation of xor is simpler than sub, so it should consume slightly less energy. Wondering how much energy was saved in the whole world by using xor instead of sub.
> I don’t know why xor won the battle, but I suspect it was just a case of swarming.
> In my hypothetical history, xor and sub started out with roughly similar popularity, but xor took a slightly lead due to some fluke, perhaps because it felt more “clever”.
SO MUCH ink and "odd" code has been spilled over these 2 sentences over the past few decades...
I recall thinking about these things quite a bit when reading Michael Abrash back in the 90s.
How much of that advice applies to anything these days is questionable. Back then we used to squeeze as much as possible from every clock cycle.
And cache misses weren’t great but the “front side bus” vs CPU clock difference wasn’t so insane either. RAM is “far away” now.
So the stuff you optimize for has changed a bit.
Always measure!
My favorite (admittedly not super useful) trick in this domain is that sbb eax, eax breaks the dependency on the previous value of eax (just like xor and sub) and only depends on the carry flag. arm64 is less obtuse and just gives you csetm (special case of csinv) for this purpose.
Afaik xor reg,reg is optimized by the cpu as zero-out reg; sub reg, reg is quite more difficult to optimize this way; this seems to be quite important in modern cpus, where cisc is translated to micro-ops; in superscalar archs, this is probably optimized away instead of causing a stall.
XOR is faster than SUB on bit slice processors. I'd posit that that created established idioms as micros came on the scene.
XORing just feels more like xxxxing out the register. SUB feels like a calculation or mistaken use of a register.
SUB may have side effects of setting flags that XOR may not depending on the CPU.
Back in the stone ages XOR ing was just 1 byte of opcode. Habbits stick. In effect XORing is no longer faster since a long time.