Hacker News Reader

I remember an AMD chief architect telling me that the hardest part of building a performant x86 core is getting the memory subsystem right.

Definitely; Linus also makes this point in his well-known post on x86 (http://yarchive.net/comp/linux/x86.html ):

The low register count isn't an issue when you code in any high-level language, and it has actually forced x86 implementors to do a hell of a lot better job than the competition when it comes to memory loads and stores - which helps in general. While the RISC people were off trying to optimize their compilers to generate loops that used all 32 registers efficiently, the x86 implementors instead made the chip run fast on varied loads and used tons of register renaming hardware (and looking at _memory_ renaming too).

More recently, I've heard that the effectiveness of caching, out-of-order execution, and speculation mean that on modern x86 the most frequently accessed memory, which would be the local variables near the stack pointer, is almost as fast as the registers - comparisons have been made between the x86's 8 (or 16 for x86-64) registers and the 256 bytes around the stack pointer to the 6502's "one really fast register, and 256 others that are nearly as fast."

The uops/instruction number looks bogus. I remember those numbers being very close 1.

It depends greatly on the exact instruction mix being executed; same for the cycles/uop.

> 6502's "one really fast register, and 256 others that are nearly as fast."

Thanks. That brought back some sweet memories. The 6502's simplicity has been a source of inspiration for me throughout my career. Sometimes I wish I had designed more hardware.

  Definitely; Linux also makes this point in his well-known post on x86

Linus, perhaps?

Yes I do mean him. Fixed.

Your link is fabulous ! Thanks for sharing it, that was not-so-well known.

This is definitely not the case, x86 chips can do a load+arith_op or a store+arith_op in the same uop.

I don't think so? While these operations can be written with a single x86 assembly instruction, internally they are split into different µops which execute on different ports. Here's Agner's chart[1] for ADD and SUB on Haswell (with some typographic editing for clarity):

    inst   operands  fused unfused     ports   latency throughput
  ADD SUB  r <- r/i    1    1      p0156             1 0.25
  ADD SUB  r <- m      1    2      p0156 p23           0.5
  ADD SUB  m <- r/i    2    4      2p0156 2p237 p4   6 1

This is saying that adding register (r) to a register or an immediate (i) takes one µop which executes on any one of Ports 0, 1, 5, or 6, has a latency of 1 cycle, and that 4 of these can be executed per cycle.

For an add that comes from memory with the result put in the register, the instruction is decoded as a single µop (fused), but this is executed as two separate µops: one on Port 0, 1, 5, or 6; and one on Port 2 or 3. Latency is unspecified (depends on the source of the load), and you can execute a maximum of 2 per cycle.

For an adding a register with a memory location and storing the result to memory, the single x86 assembly instruction decodes to 2 fused µops, which then execute as 4 unfused µops: two on any combination of Ports 0, 1, 5, or 6; one on Port 2, 3, or 7; and one on Port 4. The latency is at least 6 cycles, and at best you can sustain one of these per cycle.

The uops/instruction number looks bogus. I remember those numbers being very close 1. The cycles per uop of 0.37 seems wildly optimistic. I remember numbers closer to 1.

It's easier now than then, but depending on workload, executing 3 µops per cycle (.33) is easily achievable for optimized code. The current limit is essentially 4 (.25), but even this is within reach. I recently had a pathological case where I sustained almost 5 µops executed per cycle (.21), which at first glance is impossible since only 4 µops can be issued or retired per cycle. I think what was happening was that due to failed memory disambiguation, some of the stores and loads were being executed twice before being retired.

[1] http://www.agner.org/optimize/microarchitecture.pdf

The paper is concerned with the front end, so the fused uops are what matter there even if they get split up for the actual execution. Similarly for structures like ROB, you'll artificially inflate occupancy, and possibly create fake bottlenecks, if you split up uops too much.

But yes, if you're pointing out a add reg, men instruction actually gets executed in two places, you're right.

Also for the uops per cycle, I don't doubt you can get really nice numbers for tight highly optimized. But if you're running entire applications like Winzip, which do a whole lot of things including lots of I/O and system calls, I doubt that you'll still get those numbers.

uop fusion was added in Pentium-M, the Pentium III modeled in the paper didn't have it.

The decoders have a throughput of 4 fused uops or instructions per cycle, but are limited to 16 bytes per cycle (which tends to become the limit if you attempt to push >4 unfused uop perc cycle). But in Haswell, the uop cache has double that size limit, plus it counts late-fused uops as one, so it's not that impossible to sustain >4 unfused uop per cycle in certain loops... Agner puts the limit at 6 instructions, so at least 6 unfused uop per cycle (maybe 8)

Renaming or retirement could bottleneck, but Agner hasn't found them to bottleneck in Haswell so that's more theoretical.

The bright part is that tight loops are almost always going to be coming out of the ~1500 µop decoded instruction cache or the 28 µop Loop Stream detector. These have the same issue limit of 4 µops per cycle, but count both macro- and micro-fused µops as 1. I'm not certain how they are treated at retirement. Is it the same?

A big surprise to me recently was learning that having the number of µops in a tight loop be a multiple of 4 can make a big difference. I put up what I think is a mind-bending example last week: https://gist.github.com/nkurz/1ecb46486746c4e078b3 Perversely, in this example making the loop slower actually has the effect of making the run time faster.

I don't think the number of uops in the loop being a multiple of 4 is the factor there. To see this, replace `ADD RAX, 1` with `INC RAX`, which does the exact same thing but does not alter the carry flag. The number of uops remains the same, but the runtime difference vanishes.

I can't verify this at the moment, but my guess is that the true effect of SBB is to partially serialize the loop, therefore avoiding numerous store-forwarding and other pesky memory subsystem stalls down the line.

I'd love for you to dive into this one and see where you get. I think this example has a number of confusing layers. My conclusion after staring at it a long time was that the difference between SBB and SUB is that SUB/JNE allows macro fusion and leaves the loop with 4 µops, whereas SBB JNE does not fuse, leaving the loop with 5 µops. Having 5 µops slows the loop down by a cycle, which as you guessed, saves us from a problem caused by issuing the load too soon after the store, although from measuring events, I'm pretty sure this isn't related to store-forwarding. The relevant sections in the Intel Optimization manual are 3.4.2.5 for the µop multiples of 4, and 3.6.5.2 for the load too quickly after store. I'd love to understand better what's actually happening during that delay. Measurements seem to say that it causes the load to be re-executed multiple times.

I've tried your switch, and yes, switching to a non-flag-setting 'INC RAX' causes both the SUB and SBB versions to run slowly. Since this is not explained by my theory, my explanation must be at least partly wrong. I suspect you are on the correct path, and the dependence on the carry flag is significant

But I keep finding all sorts of other timing differences that I can't explain. For example, using the 'INC RAX' version but adding a stray 'XOR RDX, RAX' into the loop makes both SUB and SBB run fast rather than slow. Does this fit with your explanation?

Both fast examples create a dependence between loop iterations. The ADD+SBB case creates a dependence between the carry flag and the value loaded from memory; the INC + XOR creates a dependence on the value of RDX and the value loaded from memory. I don't know what exactly is the mechanism here, but the data dependencies seem to prevent memory loads to be speculated like crazy, presumably the source of the slowdown.

Another data point: replace SUB RCX, 1 / JNZ by LOOP. LOOP is much slower, something like 7 uops, but it still results in a speedup. Here I cannot blame data dependencies. LOOP is microcoded, so perhaps its internal implementation has the same effect.

> For instance they claim an ADD mem, reg instruction would be translated into three 3 uops. This is definitely not the case, x86 chips can do a load+arith_op or a store+arith_op in the same uop.

Sort of. An `add mem, reg` operation will result in 3 uops, but 2 of them will be fused (treated as a single one) throughout the pipeline until they're dispatched to execution units. This was introduced in the Pentium M, and perfected in Core 2---both of which released much later than the linked paper.

What's the source for this? I've definitely worked on an AMD processor which executed add reg, mem as a single uop. I can't comment on Intel's uop fusion and uop cracking shenanigans because I don't understand them very well.

Since K7/K8 at least. See Agner Fog's microarchitecture manuals, or Anandtech's core/K8 comparison.

You're probably thinking in terms of AMD's "macro-ops" which is basically the same thing as Intel's fused uops.

uop fusion is described in Agner's microarchitecture [1] and also on Intel's optimization manual [2, §2.3.2.6]. I don't know of any breakdown of uops for AMD's chips, but it's reasonable to assume that `add reg, mem` does that; it's the `add mem, reg` case which forces at least 2 fused uops to be issued.

EDIT: OK, apparently an AMD "macro-op" can actually be a 3-uop read-modify-write operation [3]. This is news to me.

[1] http://agner.org/optimize/microarchitecture.pdf

[2] http://www.intel.com/content/www/us/en/architecture-and-tech...

[3] http://www.realworldtech.com/bulldozer/5/

18 cycle latency for memory access is way too low as well.

Some of the figures seem hard to believe, but on the other hand this was 2001. The first 1GHz chip hit shelves in 2000 (?). So 18 cycles then was (very roughly) 100 cycles now. That puts us more in the ballpark. (At 3.3GHz, it's around 200 cycles)

Then add in, if my memory serves DDR was lower latency than DDR3.

It's in the right order of magnitude, considering that at the time the most popular type of PC memory would be PC100/133 SDRAM with a latency of 2-3 cycles at 100/133MHz FSB, and a typical CPU being a Pentium II/III at 400-500MHz - 4-5x FSB frequency meaning 8-15 cycles at the core.

Yeah, I mean it's way too low for 2014.