6 ms·

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

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?

mikequinlan 6mo ago
As TFA says, on x86 `sub eax, eax` encodes to the same number of bytes and executes in the same number of cycles.
- whizzter 6mo ago
  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.
  - abainbridge 6mo ago
    > 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. I think that era of CPUs used a single circuit capable of doing add, sub, xor etc. They'd have 8 of them and the signals propagate through them in a row. I think this page explains the situation on the 6502: https://c74project.com/card-b-alu-cu/ https://c74project.com/card-b-alu-cu/ And this one for the ARM 1: https://daveshacks.blogspot.com/2015/12/inside-alu-of-armv1-first-arm.html https://daveshacks.blogspot.com/2015/12/inside-alu-of-armv1-... But I'm a software engineer speculating about how hardware works. You might want to ask a hardware engineer instead.
  - adrian_b 6mo ago
    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.
    - deathanatos 6mo ago
      > In any ALU the speed is determined by the slowest operation, so XOR is never faster. On a 386, a reg/reg ADD is 2 cycles. An r32 IMUL is "9-38" cycles. If what you stated were true, you'd be locking XOR's speed to that of DIV. (Or you do not consider MUL/DIV "arithmetic", or something.) https://www2.math.uni-wuppertal.de/~fpf/Uebungen/GdR-SS02/opcode_i.html https://www2.math.uni-wuppertal.de/~fpf/Uebungen/GdR-SS02/op... > 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. (And I'm choosing 386 to avoid it being "a superpipelined CPU".)
arka2147483647 6mo ago
> 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.
- akie 6mo ago
  "The proof is left as an exercise for the reader" comes to mind
themafia 6mo ago
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 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.
- asQuirreL 6mo ago
  A carry lookahead adder makes your circuit depth logarithmic in the width of the inputs vs linear for a ripple carry adder, but that is still asymptotically worse than XORs constant depth. (But this does not discount the fact that basically all CPUs treat them both as one cycle)
- bonzini 6mo ago
  OF/CF/AF are always cleared anyway by SUB r,r. So there's absolutely no difference.
  - themafia 6mo ago
    The point is OF/CF are sometimes dependent on the inputs for SUB. They never are for XOR.
    - bonzini 6mo ago
      Ah, you mean in terms of complexity of the calculation. Thanks for clarifying. In practice AF and CF can be computed from the carry out vector which is already available, and OF is a single XOR (of the two most significant bits of the carry out vector). The same circuitry works for XOR and SUB if the carry out vector of XOR is simply all zeroes.
      - themafia 6mo ago
        It also clears any dependence on the state of those flags. Which is probably not useful in practice.
svnt 6mo ago
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.
- 3form 6mo ago
  I think an even more likely explanation would be that x86 assembly programmers often were, or learned from other-architecture assembly programmers. Maybe there's a place where it makes more sense and it can be so attributed. 6502 and 68k being first places I would look at.
  - richrichardsson 6mo ago
    For 68k depending on the size you're interested in then it mostly doesn't matter. .b and .w -> clr eor sub are all identical for .l moveq #0 is the winner
  - bonzini 6mo ago
    6502 doesn't even have register-to-register ALU operations, there's no alternative to LDA #0. 8080/Z80 is probably where XOR A got a lead over SUB A, but they are also the same number of cycles.
- zahlman 6mo ago
  GP seems to think it strange that "x86" would actually not have a performance difference here. I think this might just be due to not realizing just how far back in CPU history this goes.
  - wongarsu 6mo ago
    In a clockless cpu design you'd indeed expect xor to be faster. But in a regular CPU with a clock you either waste a bit of xor performance by making xor and sub both take the same number of ticks, or you speed up the clock enough that the speed difference between xor and sub justifies sub being at least a full tick slower The former just seems way more practical
phire 6mo ago
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.
- deleted 6mo ago
  [deleted]
- FarmerPotato 6mo ago
  I'm studying 4-bit-slice processors from the 1970s. This is all tangent to the x86 discussion. Minicomputer processors! I have two bit-slice machines from TI based on the 74S481 (4-bit slice x 4). Just like with the 74181, all ALU operations go through the same path, there are just extra gates that make the difference between logical or arithmetic. For instance, for each bit in the slice, the carry path is masked out if logical, but used if arithmetic. * The XOR operation (logical) is accomplished with A+B but no bits carry. If carry is not masked, you get arithmetic ADD. * The ZERO or CLEAR operation is (A+A without carry). With carry, A+A is a shift-left. * The ONES operation forces all the carry chain to 1 (ignoring operand) (you can do a ONES+1 to get arithmetic 0, but why?) * In the simpler 74181 (4 years earlier) there are 16 operations with 48 logical/arithmetic outcomes. Pick 12 or so for your instruction set. There are some weirdos. The crazy thing here is that in the TM990/1481 implementation, the microinstruction clock is 15 MHz, and each has a field for number of micro-wait states. This is faster than the '481s max! Theoretically, if 66ns is sufficient to settle the ALU, a logical operation doesn't need a micro-wait-state. While arithmetic needs one, only because of carry-look-ahead. If I/O buses are activated, then micro-instructions account for setup/hold times. I could be wrong about the details, but that field is there! It's the only architecture I know of with short and long microinstructions! (The others are like a fixed 4-stage cycle: input valid, ALU valid, store)
  - phire 6mo ago
    Thanks, I suspected there might be something from the minicomputer era. I've only really looked at a single AM2900 implementation (and it was far from optimal). Guess I need to dig deeper at some point. > The ONES operation forces all the carry chain to 1 (ignoring operand) (you can do a ONES+1 to get arithmetic 0, but why?) Forcing all carries to 1 inverts the output. If I'm understanding the ALU correctly, (the datasheet doesn't show that part) it only implements OR and XOR. When combined with the ability to invert both inputs, AND can be implemented as !(!A OR !B), NAND is (!A OR !B) and so on. Or maybe the ALU implements NOR and XNOR, and all the carry logic is physically inverted from what the documentation says.
feverzsj 6mo ago
It's like 0.5 cycles vs 0.9 cycles. So both are 1 cycle, considering synchronization.
- pishpash 6mo ago
  But energy consumption could be different for this hypothetical 0.5 and 0.9.
  - scheme271 6mo ago
    Energy consumption wasn't really a concern when the idiom developed. I don't think people really cared about the energy consumption of instructions until well into the x86-64 era.
    - allenrb 6mo ago
      Not sure why this is being downvoted, but it’s absolutely correct. For most of the history of computing, people were happy that it worked at all. Being concerned about energy efficiency is a recent byproduct of mobile devices and, even more recently, giant amounts of compute adding up to gigawatts.
      - pishpash 6mo ago
        This take is anachronistic. Thermal issues were evident by the late 1990's. Of course by that time not many were working in x86 assembly but embedded systems sure cared about power. People forget embedded predated mobile by a good 20 years.
        imtringued 6mo ago
        Nintendo's original Game Boy lasted 40 hours on two AA batteries in 1989. You can't reach those numbers without engineering for energy efficiency.
Tepix 6mo ago
From TFA: > It encodes to the same number of bytes, executes in the same number of cycles.
- abainbridge 6mo ago
  Those aren't the only resources. I could imagine XOR takes less energy because using it might activate less circuitry than SUB.
  - zahlman 6mo ago
    I'm not aware of any stories in the historical record of "real programmers" optimizing for power use, only for speed or code size.
    - abainbridge 6mo ago
      For a few years I worked in the team that wrote software for an embedded audio DSP. The power draw to do something was normally more important than the speed. Eg when decoding MP3 or SBC you probably had enough MIPS to keep up with the stream rate, so the main thing the customers cared about was battery life. Mostly the techniques to optimize for speed were the same as those for power. But I remember being told that add/sub used less power than multiply even though both were single cycle. And that for loops with fewer than 16 instructions used less power because there was a simple 16 instruction program memory cache that saved the energy required to fetch instructions from RAM or ROM. (The RAM and ROM access was generally single cycle too). Nowadays, I expect optimizations that minimize energy consumption are an important target for LLM hosts.
    - toast0 6mo ago
      Sibling posted a good example. But I know of (without details) things where you have to insert nops to keep peak power down, so the system doesn't brown out (in my experience, the 68hc11 won't take conditional branches if the power supply voltage dips too far; but I didn't work around that, I just made sure to use fresh batteries when my code started acting up). Especially during early boot. Apple got in a lot of trouble for reducing peak power without telling people, to avoid overloading dying batteries.
jojobas 6mo ago
The non-obvious bit is why there isn't an even faster and shorter "mov <register>,0" instructions - the processors started short-circuiting xor <register>,<register> much later.
- deleted 6mo ago
  [deleted]
- drob518 6mo ago
  Right, like a “set reg to zero” instruction. One byte. Just encodes the operation and the reg to zero. I’m surprised we didn’t have it on those old processors. Maybe the thinking was that it was already there: xor reg,reg.
  - bonzini 6mo ago
    One byte instructions, with 8 registers as in the 8086, waste 8 opcodes which is 3% of the total. There are just five: "INC reg", "DEC reg", "PUSH reg", "POP reg", "XCHG AX, reg" (which is 7 wasted opcodes instead of 8, because "XCHG AX, AX" doubles as NOP). One-byte INC/DEC was dropped with x86-64, and PUSH/POP are almost obsolete in APX due to its addition of PUSH2/POP2, leaving only the least useful of the five in the most recent incantation of the instruction set.
    - drob518 6mo ago
      I’m not sure I understand what you mean by “waste 8 opcodes.”
      - bonzini 6mo ago
        They occupy 8 of the possible 256 byte values. Together, those five cases used about 15% of the space. Though I was forgetting one important case: MOV r,imm also used one-byte opcodes with the register index embedded. And it came in byte and word variants, so it used a further 16 opcodes bytes for a total of 56 one byte opcodes with register encoding.
virexene 6mo ago
The operation is slightly more complex yes, but has there ever been an x86 CPU where SUB or XOR takes more than a single CPU cycle?
- praptak 6mo ago
  I wonder if you could measure the difference in power consumption. I mean, not for zeroing because we know from the TFA that it's special-cased anyway. But maybe if you test on different registers?
flohofwoe 6mo ago
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.
- brigade 6mo ago
  Cortex A8 vsub reads the second source register a cycle earlier than veor, so that can add one cycle latency Not scalar, but still sub vs xor. Though you’d use vmov immediate for zeroing anyway.
- GoblinSlayer 6mo ago
  Harvard Mark I? Not sure why people think programming started with Z80.
  - flohofwoe 6mo ago
    My WW2-era assembly is a bit rusty, but I don't think the Harvard Mark 1 had bitwise logical operations?
  - bonzini 6mo ago
    The article is about x86, and x86 assembly is mostly a superset of 8080 (which is why machine language numbers registers as AX/CX/DX/BX, matching roughly the function of A/BC/DE/HL on the 8080—in particular with respect to BX and HL being last).
    - GoblinSlayer 6mo ago
      So you say x86 wasn't made ex nihilo, but evolved from previous designs? When this evolution began? 8080 followed 8008, code for which was written in macro-11 https://en.wikipedia.org/wiki/PDP-11_architecture#Example_code https://en.wikipedia.org/wiki/PDP-11_architecture#Example_co...
- deleted 6mo ago
  [deleted]
- 6mo ago
billpg 6mo ago
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.
- rep_lodsb 6mo ago
  Comparing for equality can use either SUB or XOR: it sets the zero flag if (and only if) the two values are equal. That's why JE/JNE (jump if equal/not equal) is an alias for JZ/JNZ (jump if zero/not zero). There's also the TEST instruction, which does a logical AND but without storing the result (like CMP does for SUB). This can be used to test specific bits. Testing a single register for zero can be done in several ways, in addition to CMP with 0: TEST AX,AX AND AX,AX OR AX,AX INC AX followed by DEC AX (or the other way around) The 8080/Z80 didn't have TEST, but the other three were all in common use. Particularly INC/DEC, since it worked with all registers instead of just the accumulator. Also any arithmetic operation sets those flags, so you may not even need an explicit test. MOV doesn't set flags however, at least on x86 -- it does on some other architectures.
defmacr0 6mo ago
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.
- brigade 6mo ago
  Zero micro ops to be precise, that’s handled entirely at the register rename stage with no data movement.
- defrost 6mo ago
  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”.
  - rasz 6mo ago
    "rename the destination to an internal zero register" That would be quite late then, 1997 Pentium 2 for general population.
bahmboo 6mo ago
Because he is explicitly talking about x86 - maybe you missed that.
adrian_b 6mo ago
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.
- imtringued 6mo ago
bialpio 6mo ago
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.
TacticalCoder 6mo ago
> 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.
- zahlman 6mo ago
  The context was comparison to SUB EAX,EAX, not to a MOV.
drob518 6mo ago
Yea, that’s what immediately went through my head, too. XOR is ALWAYS going to be single cycle because it’s bit-parallel.
- Sharlin 6mo ago
  And SUB is also always a single cycle on any practically useful architecture since the 70s. Theoretical archs where SUB might be slower than XOR don't matter.
Someone 6mo ago
> 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 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.
- dreamcompiler 6mo ago
  Carry lookahead is definitely faster than ripple carry but it's not free. It requires high-fan-in gates that take up a fair amount of silicon. That silicon saves time though, so as you say almost nobody uses ripple carry any more.
Symmetry 6mo ago
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. [1]https://en.wikipedia.org/wiki/Carry-skip_adder https://en.wikipedia.org/wiki/Carry-skip_adder

mikequinlan 6mo ago

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

whizzter 6mo ago
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.
- abainbridge 6mo ago
  > 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. I think that era of CPUs used a single circuit capable of doing add, sub, xor etc. They'd have 8 of them and the signals propagate through them in a row. I think this page explains the situation on the 6502: https://c74project.com/card-b-alu-cu/ https://c74project.com/card-b-alu-cu/ And this one for the ARM 1: https://daveshacks.blogspot.com/2015/12/inside-alu-of-armv1-first-arm.html https://daveshacks.blogspot.com/2015/12/inside-alu-of-armv1-... But I'm a software engineer speculating about how hardware works. You might want to ask a hardware engineer instead.
- adrian_b 6mo ago
  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.
  - deathanatos 6mo ago
    > In any ALU the speed is determined by the slowest operation, so XOR is never faster. On a 386, a reg/reg ADD is 2 cycles. An r32 IMUL is "9-38" cycles. If what you stated were true, you'd be locking XOR's speed to that of DIV. (Or you do not consider MUL/DIV "arithmetic", or something.) https://www2.math.uni-wuppertal.de/~fpf/Uebungen/GdR-SS02/opcode_i.html https://www2.math.uni-wuppertal.de/~fpf/Uebungen/GdR-SS02/op... > 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. (And I'm choosing 386 to avoid it being "a superpipelined CPU".)

arka2147483647 6mo ago

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

akie 6mo ago
"The proof is left as an exercise for the reader" comes to mind

themafia 6mo ago

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

asQuirreL 6mo ago
A carry lookahead adder makes your circuit depth logarithmic in the width of the inputs vs linear for a ripple carry adder, but that is still asymptotically worse than XORs constant depth. (But this does not discount the fact that basically all CPUs treat them both as one cycle)
bonzini 6mo ago
OF/CF/AF are always cleared anyway by SUB r,r. So there's absolutely no difference.
- themafia 6mo ago
  The point is OF/CF are sometimes dependent on the inputs for SUB. They never are for XOR.
  - bonzini 6mo ago
    Ah, you mean in terms of complexity of the calculation. Thanks for clarifying. In practice AF and CF can be computed from the carry out vector which is already available, and OF is a single XOR (of the two most significant bits of the carry out vector). The same circuitry works for XOR and SUB if the carry out vector of XOR is simply all zeroes.
    - themafia 6mo ago
      It also clears any dependence on the state of those flags. Which is probably not useful in practice.

svnt 6mo ago

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.

3form 6mo ago
I think an even more likely explanation would be that x86 assembly programmers often were, or learned from other-architecture assembly programmers. Maybe there's a place where it makes more sense and it can be so attributed. 6502 and 68k being first places I would look at.
- richrichardsson 6mo ago
  For 68k depending on the size you're interested in then it mostly doesn't matter. .b and .w -> clr eor sub are all identical for .l moveq #0 is the winner
- bonzini 6mo ago
  6502 doesn't even have register-to-register ALU operations, there's no alternative to LDA #0. 8080/Z80 is probably where XOR A got a lead over SUB A, but they are also the same number of cycles.
zahlman 6mo ago
GP seems to think it strange that "x86" would actually not have a performance difference here. I think this might just be due to not realizing just how far back in CPU history this goes.
- wongarsu 6mo ago
  In a clockless cpu design you'd indeed expect xor to be faster. But in a regular CPU with a clock you either waste a bit of xor performance by making xor and sub both take the same number of ticks, or you speed up the clock enough that the speed difference between xor and sub justifies sub being at least a full tick slower The former just seems way more practical

phire 6mo ago

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.

deleted 6mo ago
[deleted]
FarmerPotato 6mo ago
I'm studying 4-bit-slice processors from the 1970s. This is all tangent to the x86 discussion. Minicomputer processors! I have two bit-slice machines from TI based on the 74S481 (4-bit slice x 4). Just like with the 74181, all ALU operations go through the same path, there are just extra gates that make the difference between logical or arithmetic. For instance, for each bit in the slice, the carry path is masked out if logical, but used if arithmetic. * The XOR operation (logical) is accomplished with A+B but no bits carry. If carry is not masked, you get arithmetic ADD. * The ZERO or CLEAR operation is (A+A without carry). With carry, A+A is a shift-left. * The ONES operation forces all the carry chain to 1 (ignoring operand) (you can do a ONES+1 to get arithmetic 0, but why?) * In the simpler 74181 (4 years earlier) there are 16 operations with 48 logical/arithmetic outcomes. Pick 12 or so for your instruction set. There are some weirdos. The crazy thing here is that in the TM990/1481 implementation, the microinstruction clock is 15 MHz, and each has a field for number of micro-wait states. This is faster than the '481s max! Theoretically, if 66ns is sufficient to settle the ALU, a logical operation doesn't need a micro-wait-state. While arithmetic needs one, only because of carry-look-ahead. If I/O buses are activated, then micro-instructions account for setup/hold times. I could be wrong about the details, but that field is there! It's the only architecture I know of with short and long microinstructions! (The others are like a fixed 4-stage cycle: input valid, ALU valid, store)
- phire 6mo ago
  Thanks, I suspected there might be something from the minicomputer era. I've only really looked at a single AM2900 implementation (and it was far from optimal). Guess I need to dig deeper at some point. > The ONES operation forces all the carry chain to 1 (ignoring operand) (you can do a ONES+1 to get arithmetic 0, but why?) Forcing all carries to 1 inverts the output. If I'm understanding the ALU correctly, (the datasheet doesn't show that part) it only implements OR and XOR. When combined with the ability to invert both inputs, AND can be implemented as !(!A OR !B), NAND is (!A OR !B) and so on. Or maybe the ALU implements NOR and XNOR, and all the carry logic is physically inverted from what the documentation says.

feverzsj 6mo ago

It's like 0.5 cycles vs 0.9 cycles. So both are 1 cycle, considering synchronization.

pishpash 6mo ago
But energy consumption could be different for this hypothetical 0.5 and 0.9.
- scheme271 6mo ago
  Energy consumption wasn't really a concern when the idiom developed. I don't think people really cared about the energy consumption of instructions until well into the x86-64 era.
  - allenrb 6mo ago
    Not sure why this is being downvoted, but it’s absolutely correct. For most of the history of computing, people were happy that it worked at all. Being concerned about energy efficiency is a recent byproduct of mobile devices and, even more recently, giant amounts of compute adding up to gigawatts.
    - pishpash 6mo ago
      This take is anachronistic. Thermal issues were evident by the late 1990's. Of course by that time not many were working in x86 assembly but embedded systems sure cared about power. People forget embedded predated mobile by a good 20 years.
      - imtringued 6mo ago
        Nintendo's original Game Boy lasted 40 hours on two AA batteries in 1989. You can't reach those numbers without engineering for energy efficiency.

Tepix 6mo ago

From TFA: > It encodes to the same number of bytes, executes in the same number of cycles.

abainbridge 6mo ago
Those aren't the only resources. I could imagine XOR takes less energy because using it might activate less circuitry than SUB.
- zahlman 6mo ago
  I'm not aware of any stories in the historical record of "real programmers" optimizing for power use, only for speed or code size.
  - abainbridge 6mo ago
    For a few years I worked in the team that wrote software for an embedded audio DSP. The power draw to do something was normally more important than the speed. Eg when decoding MP3 or SBC you probably had enough MIPS to keep up with the stream rate, so the main thing the customers cared about was battery life. Mostly the techniques to optimize for speed were the same as those for power. But I remember being told that add/sub used less power than multiply even though both were single cycle. And that for loops with fewer than 16 instructions used less power because there was a simple 16 instruction program memory cache that saved the energy required to fetch instructions from RAM or ROM. (The RAM and ROM access was generally single cycle too). Nowadays, I expect optimizations that minimize energy consumption are an important target for LLM hosts.
  - toast0 6mo ago
    Sibling posted a good example. But I know of (without details) things where you have to insert nops to keep peak power down, so the system doesn't brown out (in my experience, the 68hc11 won't take conditional branches if the power supply voltage dips too far; but I didn't work around that, I just made sure to use fresh batteries when my code started acting up). Especially during early boot. Apple got in a lot of trouble for reducing peak power without telling people, to avoid overloading dying batteries.

jojobas 6mo ago

The non-obvious bit is why there isn't an even faster and shorter "mov <register>,0" instructions - the processors started short-circuiting xor <register>,<register> much later.

deleted 6mo ago
[deleted]
drob518 6mo ago
Right, like a “set reg to zero” instruction. One byte. Just encodes the operation and the reg to zero. I’m surprised we didn’t have it on those old processors. Maybe the thinking was that it was already there: xor reg,reg.
- bonzini 6mo ago
  One byte instructions, with 8 registers as in the 8086, waste 8 opcodes which is 3% of the total. There are just five: "INC reg", "DEC reg", "PUSH reg", "POP reg", "XCHG AX, reg" (which is 7 wasted opcodes instead of 8, because "XCHG AX, AX" doubles as NOP). One-byte INC/DEC was dropped with x86-64, and PUSH/POP are almost obsolete in APX due to its addition of PUSH2/POP2, leaving only the least useful of the five in the most recent incantation of the instruction set.
  - drob518 6mo ago
    I’m not sure I understand what you mean by “waste 8 opcodes.”
    - bonzini 6mo ago
      They occupy 8 of the possible 256 byte values. Together, those five cases used about 15% of the space. Though I was forgetting one important case: MOV r,imm also used one-byte opcodes with the register index embedded. And it came in byte and word variants, so it used a further 16 opcodes bytes for a total of 56 one byte opcodes with register encoding.

virexene 6mo ago

The operation is slightly more complex yes, but has there ever been an x86 CPU where SUB or XOR takes more than a single CPU cycle?

praptak 6mo ago
I wonder if you could measure the difference in power consumption. I mean, not for zeroing because we know from the TFA that it's special-cased anyway. But maybe if you test on different registers?

flohofwoe 6mo ago

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.

brigade 6mo ago
Cortex A8 vsub reads the second source register a cycle earlier than veor, so that can add one cycle latency Not scalar, but still sub vs xor. Though you’d use vmov immediate for zeroing anyway.
GoblinSlayer 6mo ago
Harvard Mark I? Not sure why people think programming started with Z80.
- flohofwoe 6mo ago
  My WW2-era assembly is a bit rusty, but I don't think the Harvard Mark 1 had bitwise logical operations?
- bonzini 6mo ago
  The article is about x86, and x86 assembly is mostly a superset of 8080 (which is why machine language numbers registers as AX/CX/DX/BX, matching roughly the function of A/BC/DE/HL on the 8080—in particular with respect to BX and HL being last).
  - GoblinSlayer 6mo ago
    So you say x86 wasn't made ex nihilo, but evolved from previous designs? When this evolution began? 8080 followed 8008, code for which was written in macro-11 https://en.wikipedia.org/wiki/PDP-11_architecture#Example_code https://en.wikipedia.org/wiki/PDP-11_architecture#Example_co...
deleted 6mo ago
[deleted]
6mo ago

billpg 6mo ago

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.

rep_lodsb 6mo ago
Comparing for equality can use either SUB or XOR: it sets the zero flag if (and only if) the two values are equal. That's why JE/JNE (jump if equal/not equal) is an alias for JZ/JNZ (jump if zero/not zero). There's also the TEST instruction, which does a logical AND but without storing the result (like CMP does for SUB). This can be used to test specific bits. Testing a single register for zero can be done in several ways, in addition to CMP with 0: TEST AX,AX AND AX,AX OR AX,AX INC AX followed by DEC AX (or the other way around) The 8080/Z80 didn't have TEST, but the other three were all in common use. Particularly INC/DEC, since it worked with all registers instead of just the accumulator. Also any arithmetic operation sets those flags, so you may not even need an explicit test. MOV doesn't set flags however, at least on x86 -- it does on some other architectures.

defmacr0 6mo ago

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.

brigade 6mo ago
Zero micro ops to be precise, that’s handled entirely at the register rename stage with no data movement.
defrost 6mo ago
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”.
- rasz 6mo ago
  "rename the destination to an internal zero register" That would be quite late then, 1997 Pentium 2 for general population.

bahmboo 6mo ago

Because he is explicitly talking about x86 - maybe you missed that.

adrian_b 6mo ago

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.

imtringued 6mo ago

bialpio 6mo ago

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.

TacticalCoder 6mo ago

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

zahlman 6mo ago
The context was comparison to SUB EAX,EAX, not to a MOV.

drob518 6mo ago

Yea, that’s what immediately went through my head, too. XOR is ALWAYS going to be single cycle because it’s bit-parallel.

Sharlin 6mo ago
And SUB is also always a single cycle on any practically useful architecture since the 70s. Theoretical archs where SUB might be slower than XOR don't matter.

Someone 6mo ago

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

dreamcompiler 6mo ago
Carry lookahead is definitely faster than ripple carry but it's not free. It requires high-fan-in gates that take up a fair amount of silicon. That silicon saves time though, so as you say almost nobody uses ripple carry any more.

Symmetry 6mo ago

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. [1]https://en.wikipedia.org/wiki/Carry-skip_adder https://en.wikipedia.org/wiki/Carry-skip_adder