Live data from Hacker News

XOR'ing a register with itself is the idiom for zeroing it out. Why not sub?

devblogs.microsoft.com

71–80 of 231 posts

Re: XOR'ing a register with itself is the idiom for zeroing it out. Why not sub?

#71
post #4

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 C…

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.

Re: XOR'ing a register with itself is the idiom for zeroing it out. Why not sub?

#72
post #4

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 C…

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.

Re: XOR'ing a register with itself is the idiom for zeroing it out. Why not sub?

#73

Earlier quoted context omitted.

As TFA says, on x86 `sub eax, eax` encodes to the same number of bytes and executes in the same number of cycles.

On modern ones, x86 has quite a history and the idiom might carry on from an even older machine. Edit: Looked at comments, seems like x86 and the major 8bit cpu's had the same speed, pondering in this might be a remnant from the 4-bit ALU times.

Nope.

In any ALU the speed is determined by the slowest operation, so XOR is never faster. It does not matter which is the width of the ALU, all that matters is that an ALU does many kinds of operations, including XOR and subtraction, where the operation done by an ALU is selected by some control bits.

I have explained in another comment that the only CPUs where XOR can be faster than subtraction are the so-called superpipelined CPUs. Superpipelined CPUs have been made only after 1990 and there were very few such CPUs. Even if in superpipelined CPUs it is possible for XOR to be faster than subtraction, it is very unlikely that this feature has been implemented in anyone of the few superpipelined CPU models that have ever been made, because it would not have been worthwhile.

For general-purpose computers, there have never been "4-bit ALU times".

The first monolithic general-purpose processor was Intel 8008 (i.e. the monolithic version of Datapoint 2200), with an 8-bit ISA.

Intel claims that Intel 4004 was the first "microprocessor" (in order to move its priority earlier by one year), but that was not a processor for a general-purpose computer, but a calculator IC. Its only historical relevance for the history of personal computers is that the Intel team which designed 4004 gained a lot of experience with it and they established a logic design methodology with PMOS transistors, which they used for designing the Intel 8008 processor.

Intel 4004, its successors and similar 4-bit processors introduced later by Rockwell, TI and others, were suitable only for calculators or for industrial controllers, never for general-purpose computers.

The first computers with monolithic processors, a.k.a. microcomputers, used 8-bit processors, and then 16-bit processors, and so on.

For cost reduction, it is possible for an 8-bit ISA to use a 4-bit ALU or even just a serial 1-bit ALU, but this is transparent for the programmer and for general-purpose computers there never were 4-bit instruction sets.

Re: XOR'ing a register with itself is the idiom for zeroing it out. Why not sub?

#74
post #4

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 C…

> The obvious answer is that XOR is faster.

It used to be not only faster but also smaller. And back then this mattered.

Say you had a computer running at 33 Mhz, you had 33 million cycles per second to do your stuff. A 60 Hz game? 33 million / 60 and suddenly you only have about 500 000 cycles per frame. 200 scanlines? Suddenly you're left with only 2500 cycles per scanline to do your stuff. And 2500 cycles really isn't that much.

So every cycle counted back then. We'd use the official doc and see how many cycles each instruction would take. And we'd then verify by code that this was correct too. And memory mattered too.

XOR was both faster and smaller (less bytes) then a MOV ..., 0.

Full stop.

And when those CPU first began having cache, the cache were really tiny at first: literally caching ridiculously low number of CPU instructions. We could actually count the size of the cache manually (for example by filling with a few NOP instructions then modifying them to, say, add one, and checking which result we got at the end).

XOR, due to being smaller, allowed to put more instructions in the cache too.

Now people may lament that it persisted way long after our x86 CPUs weren't even real x86 CPUs anymore and that is another topic.

But there's a reason XOR was used and people should deal with it.

We zero with XOR EAX,EAX and that's it.

Re: XOR'ing a register with itself is the idiom for zeroing it out. Why not sub?

#75
post #57

Earlier quoted context omitted.

I would be surprised if modern CPUs didn't decode "xor eax, eax" into a set of micro-ops that simply moves from an externally invisible dedicated 0 register. These days the x86 ISA is more of an API contract than an actual representation of what the hardware internals do.

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. You can imagine that the instruction, in some sense, “takes zero cycles to execute”.

"rename the destination to an internal zero register"

That would be quite late then, 1997 Pentium 2 for general population.

Re: XOR'ing a register with itself is the idiom for zeroing it out. Why not sub?

#76
post #4

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 C…

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.

[deleted]

Re: XOR'ing a register with itself is the idiom for zeroing it out. Why not sub?

#77
post #4

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 C…

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 6502 doesn't support XOR A or SUB A, and in fact doesn't have a SUB opcode at all, only SBC (subtract with carry, requiring an extra opcode to set the carry flag beforehand).

Re: XOR'ing a register with itself is the idiom for zeroing it out. Why not sub?

#78
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.

Re: XOR'ing a register with itself is the idiom for zeroing it out. Why not sub?

#79
post #47

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.

This sounds like a Paged Out article ;)

Re: XOR'ing a register with itself is the idiom for zeroing it out. Why not sub?

#80
> 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....

Post reply on HN