Performance Speed Limits

https://travisdowns.github.io/blog/2019/06/11/speed-limits.html

by pimterry • 7 years ago

256 48 7 years ago

travisdowns.github.io

BeeOnRope20• 7 years ago

Author here, happy for any feedback and to answer any questions!

Some things are definitely missing - I realize I don't cover load or store buffers in the OoO part, for example. I am working on fixing that.

maztheman• 7 years ago

There is a small typo under the "Pipeline Width" Heading. Superscalar link is "Supercalar"

BeeOnRope20• 7 years ago

Thanks, fixed and credited.

nkurz4• 7 years ago

Great article, thanks!

My main suggestion for improvement would be to flesh out the details of determining which limit you are hitting. For example, how do you (semi-automatically) determine that changing to a simpler addressing mode might let you fit in another load per cycle? How do you determine that you are being limited by the size of the ROB? Knowing that these bottleneck exists helps, but knowing which remedy to try helps even more.

As for errors, there are a bunch of small typos. Making a pass with a spell-checker would catch most of these, or I could send my usual email. In the early passage about vectorization, I think you mean "you could get [an additional] 3x, down to roughly 0.125". Factually, I wasn't sure that "One operation per port, per cycle" was quite true, especially since you later talk about address calculations.

As far as static site commenting options, I came across this nice summary of approaches when we were trying to fix up Daniel's blog: https://darekkay.com/blog/static-site-comments/.

BeeOnRope20• 7 years ago

Thanks nkurz!

I will look at installing a spell checker in the IDE where I wrote this. I recently removed it because it was too frustrating for code and technical documentation due to the large number of false positives, but I'll take another shot.

My main suggestion for improvement would be to flesh out the details of determining which limit you are hitting.

Yeah. For the few limits I wrote about (which isn't in the order of the document) I included perf counters you can use to check if you are hitting the limit.

The basic idea though is that you go though the limits one by one, calculate the limit as it applies to your code, then compare that against the observed performance. Ideally, one limit will match the performance you are getting and then that's the limit (it could be tied of course, but it's still the limit in the sense that you can't go faster w/o solving that).

Of course, this is often difficult to do: not everyone wants to read assembly and go through the list of limits. That's where say llvm-mca comes into play, although I could write more about that.

I can also write more about peformance counters which can detect the problems, but then it starts to overlap a lot with Intel's top-down methodology, on which a lot has already been written (BTW, topdown is good, I recommend it).

Factually, I wasn't sure that "One operation per port, per cycle" was quite true, especially since you later talk about address calculations.

I didn't catch the issue, can you elaborate?

shereadsthenews• 7 years ago

This is very practical guide, thanks for sharing.

vardump• 7 years ago

Very good, you clearly got a very accurate grasp of the low level details. Thanks for writing such an informative guide!

vnorilo2• 7 years ago

Thank you for this - bookmarked for the future.

My uarch knowledge is a bit out of date; would you happen to know if the following can still cause performance problems in modern Intel/AMD?

- call/return address mismatch

- mixing int/float vector instructions with same register

- false dependencies between partial registers (ie. AH and AL)

Thanks again!

BeeOnRope20• 7 years ago

- call/return address mismatch

Definitely, it's as important as ever.

If you have matched call/ret pairs but cause an address mismatch by say modifying the return value on the stack, the subsequent `ret` will mispredict.

OTOH, if you cause a mismatch by having unbalanced call ret pairs, e.g., a `call` to a location that does a `jmp` back instead of a ret, the situation is much worse: the ret prediction stack is mismatched so you'll can mispredict on the next N return calls where N is 16 or 32 or whatever the size of the stack is (it doesn't mean that will happen: if the following code does many more calls before the correspond rets the bad predictions may fall of the stack and never be used).

The good news is that this one is really easy to avoid. Why would you end up with mismatched call/ret in the first place? It doesn't happen in normal code and even in hand-rolled assembly I can't see many reasons you'd end up like that.

There is one pattern that is used sometimes with mismatched calls: `call; pop eax` to get the current IP in rax (for example) - useful in 32-bit position independent code (in 64-bit code you can just use rip-relative addressing). This one is special cased though so it does not cause a misprediction.

Way more details avaialble here (this page is also linked in my post):

http://blog.stuffedcow.net/2018/04/ras-microbenchmarks

- mixing int/float vector instructions with same register

These are the so-called domain bypass penalties. They are much reduced and I haven't seen them in practice on modern chips, but lets check Agner...

Yeah, it's best just to read Agner. See 10.9 Data Bypass Delays, for example. Here's an excerpt:

However, there are fewer such delays on Haswell and Broadwell than on previous processors. I found no such delays in the following cases:
- when a floating point Boolean instruction, such as ORPS is used with integer data
- when a wrong type of move instruction is used, e.g. MOVPS or MOVDQA
- when a wrong type of shuffle instruction is used, e.g. SHUFPS or PFHUFD

The situation is similar for Skylake. Recommend checking out microarchitecture.pdf for the full scoop.

- false dependencies between partial registers (ie. AH and AL)

This one has the best answer of all, very complete:

https://stackoverflow.com/q/45660139/149138

I refer to it whenever I forget the details. The part I always remember: anything involving al always extracts/merges from/into the existing physical register: there are no uop or latency penalties, but there is always a dependency on the full register (rax in this case). So a write to al can't proceed until the rest of rax is available, and same for a read.

ah is very different: it renames to separate register, so it acts decoupled from rax. The penalties are reversed from above: there is no false dependency, but there may be merging uops and other costs.

The details on old chips are different.

IMO this one has little impact, but there are some cases where it matters, like really trying to optimize scalar byte extraction.

an_d_rew• 7 years ago

Nice work - thank you!

agumonkey2• 7 years ago

Do you have books or lectures on the topic or do you go from scratch and pure brain juice ?

BeeOnRope20• 7 years ago

I learned from Agner's guides, the Intel and AMD optimization manuals and experimentation.

It didn't exist in its current form whenn I started, but the x86 tag wiki is a great source for x86 specific stuff:

https://stackoverflow.com/tags/x86/info

I focus on x86 but I would say 75% of the knowledge is transferable to other architectures. 25% is weird x86 stuff that you aren't likely to find anywhere else.

mr_luc• 7 years ago

Huh -- when I read this:

This pattern is hard to achieve in practice in a high level language, although you might have luck emulating it with gcc’s labels as values functionality.

it sounded familiar, and immediately made me wonder if it's the same as the 'direct threading' technique used in the BEAM VM under the hood that uses that gcc extension -- it sounds like it is, if I'm reading this right:

https://blog.stenmans.org/theBeamBook/#_dispatch_directly_th...

(A language based more or less on embracing context switches is of course funny company for an article about performance speed limits)

caf3• 7 years ago

This is using the same GCC functionality, but for a different purpose.

The emulator is using it to replace a loop which selects one of several bodies on each iteration, with a direct jump from the body of the previous iteration to the correct body for the next iteration.

This article is suggesting using it to replace a call/return pair to a leaf function with what essentially amounts to a single-entry call stack (or a manually implemented link register).

RivieraKid2• 7 years ago

This is one of the best technical articles I've ever read, thanks.

It wasn't clear to me what "organize the likely path instead as untaken" means.

BeeOnRope20• 7 years ago

Yes, it is confusing: it should probably say "organize the code so that the likely branch outcome is the fall-through one".

Does that make sense?

Basically the "jump" should be the unusual case. You can always organize the code like that, but sometimes the compiler needs a little help.

Consider the following function, which just sets negative values to zero.

    void zero_threshold(int *data, size_t len) {
        for (size_t i = 0; i < len; i++) {
            int x = data[i];
            if (x < 0) data[i] = 0;
        }
    }

On gcc this compiles to something like:

    .L4:
        mov     edx, DWORD PTR [rdi]
        test    edx, edx
        jns     .L3
        mov     DWORD PTR [rdi], 0
    .L3:
        add     rdi, 4
        cmp     rdi, rax
        jne     .L4

The `jns` is the jump that reflects the if (x < 0) statement and it jumps in the case the number is >= 0 (i.e., non-negative). gcc organizes it like this because it involves a only a single jump. However if you expect the non-negative case to be the common one, this is will limit the throughput of the code. It would be better to compile it like this:

  .L4:
        mov     edx, DWORD PTR [rdi]
        test    edx, edx
        js      .L10
  .L3:
        add     rdi, 4
        cmp     rdi, rax
        jne     .L4
  .L1:
        ret
  .L10:
        mov     DWORD PTR [rdi], 0
        jmp     .L3

This now involves two jumps when the number is negative: it has to jump out to the extra bit of code outside the main body of the function at .L10, and then jump back, but the common case is now "fall through" so this could execute at close to 1 per cycle, twice as fast as the other version.

You can get gcc to produce the second code by changing the condition to __builtin_expect(x < 0, 0):

https://godbolt.org/z/2Qgk7p

Of course, this code would be much off vectorized, but it's just an example (and the same principle applies to jumps in vectorized code).

caf3• 7 years ago

Do 'ret' instructions count against the branch order buffer, since they're essentially indirect branches?

BeeOnRope20• 7 years ago

Good question, I am not sure. Henry mentions they do not count against the 14-15 "call limit", but they may be handled the same as a branch in the BOB as you suggest.

haberman2• 7 years ago

As an example, a load instruction takes a cache miss which means it cannot retire until the miss is complete. On an Haswell machine with a ROB size of 192, at most 191 additional instructions can execute while waiting for the load: at that point the ROB window is exhausted and the core stalls. This puts an upper bound on the maximum IPC of the region of 192 / 300 = 0.64.

Where does 300 come from? Is this the number of cycles for the cache miss?

nkurz4• 7 years ago

Yes, I think 300 is an estimate of the number of cycles for a load from RAM: 192 ops / 300 cycles == .64 ops / cycle.

I'm not sure whether the calculation is true, though. Why can't the post-load µops be executed and retired, and the ROB refilled, and then more µops executed? I'd think the calculation would only apply if everything was somehow speculative and thus nothing could be retired, but I don't see this being a common occurrence.

BeeOnRope20• 7 years ago

Thanks, good catch - it is indeed the number of cycles. I had reorganized that sentence planning to move the number of cycles and instead it just got dropped.

Fixed and credited. Now it says:

Let's say the load takes 300 cycles to finish, which is a typical latency. Then, on an Haswell machine with a ROB size of 192...

https://github.com/travisdowns/travisdowns.github.io/commit/...

rkunde• 7 years ago

You mention there’s always only one scalar multiplication unit. Can you elaborate why that is the case? What’s keeping AMD and Intel from adding more?

BeeOnRope20• 7 years ago

Multipliers that can do a 64x64->128 bit multiplication every cycle at 5 GHz are large in area and power hungry. They are most expensive traditional hardcoded integer unit (divide is even more expensive, but it is usually implemented as many operations that repeatedly use a divider unit and other units to do a few digits at a time: on essentially all current x86 chips large divides take 40-80 cycles!).

The limitation isn't that bad in practice: it's hard to get more than 1 multiplication per cycle in non-trivial code since you have only 3 more ops to do all the other work - where are the multiplication inputs coming from, for example?

So more than one multiplier probably has a small payoff. Apple chips, for example, are wider, and IIRC they have two multipliers as they can take more advantage.

It's worth noting that 64-bit multipliers are expensive enough that even in AVX-512 Intel still offers zero 64-bit input multiplies in their SIMD unit (they offer a 53 bit one that reuses the FMA hardware though).

haberman2• 7 years ago

I generally dislike the "bottleneck" metaphor when applied to performance, because the metaphor only makes sense when the individual "parts" run in parallel. In most scenarios, each bit of code adds its own latency that is independent of the latency of other components. So every component is a "bottleneck", so-to-speak, it's just that some are bigger bottlenecks than others.

However this case is an unusual exception, because all of these hardware components described in this article do run in parallel. So the slowest element does truly gate the throughput of all stages of the pipeline. You could add more load to the non-bottlenecked resources and the overall latency of the pipeline wouldn't change at all, roughly speaking.

BeeOnRope20• 7 years ago

Yes, exactly. I didn't describe this but it's something I was thinking about: if you don't hit the bottleneck, you don't pay any price: if the limit of uops allocated is 4 but you are only doing 3.5, you don't pay any price: the limit might as well be infinite.

It's for this reason I struggled to include, for example, branch prediction failures. Let's say they take a 15 cycle bubble in the front-end. You can create a "speed limit" there and say "you can't do more than 1/15 mispredicts per cycle", which is indeed true. However, it then doesn't work like the other limits: if you measure 1 mispredict every 30 cycles, you aren't at the limit, but it still has a huge impact on performance, because the bubbles are likely slowing down everything else you do in those 30 cycles too. Perhaps 15 cycles of the 30 are solely dedicated to handling the mispredicts.

Therefore to include mispredicts here, it won't be a simple "speed limit" thing: you will need to understand the exact effect of the mispredict on the front end, and how it interacts with the other speed limits. Sometimes a mispredict costs 15 cycles (the figure you hear), but sometimes they don't slow down your code at all, and you can certainly design tests where they cost 1000s of cycles each.

Asm2D3• 7 years ago

Thanks for the article!

I started AsmGrid project that provides X86 architecture overview and instruction timings for people like me that often work with assembly. It's basically a simple web application that displays data provided by AsmDB and timings obtained through cult tool (https://github.com/asmjit/cult).

AsmGrid is available here, click on X86 Perf tab to see instruction timings:

  - https://asmjit.com/asmgrid

A bit older version that has more microarchitectures (but less instructions) is here:

  - https://kobalicek.com/asmgrid

I'm also looking for some help with instruction timings. I would be thankful to anyone who has X86 CPU having a different microarchitecture than those available at https://asmjit.com/asmgrid/ and is willing to compile & run cult tool, and provide me its output.

Instructions for cloning and compiling cult are here:

  - https://github.com/asmjit/cult

BeeOnRope20• 7 years ago

Thanks for the link, I didn't know about CULT (but I use asmjit, it's a great project).

I do feel like there is a lot of redundancy in this area. You are probably aware of Agner's instruction tables, and he makes the source available for his latency testing tools. You are probably aware of uops.info which has latency/throughput numbers for instructions online and in XML format. Now there is CULT (or actually CULT came before uops.info but I wasn't aware of it), and ASMDB.

There is the AIDA64 instruction latency thing giving the tables at:

http://instlatx64.atw.hu/

There is also uarch-bench which I wrote, which has slightly different goals than just getting the latency/throughput of instructions, but still does a lot of that and has a lot of overlap in other areas.

I have seen more as well, but I can't remember all of them.

Unless you love is really writing these kind of tools (mine is not), it would be nice if there was one winner here: one canonical source for instruction timings, available in whatever format, one test application for new platforms, etc. Then efforts like "please run this on your new hardware" won't be split among various people: right now sometimes Agner gets new hardware first, sometimes the uops.info guys, sometimes the Instlat guy, etc.

Let a thousand flowers bloom and all that, but personally I think this space is due for some collaboration...

Asm2D3• 7 years ago

Yeah there is definitely some redundancy here, but there were reasons I wrote these tools. There are multiple sources that provide instruction timings. Agner's instruction tables are amazing, but they cover only a single microarchitecture at a time, so it's really difficult to compare multiple microarchitectures. Intel's online intrinsics guide only shows instruction latencies of few latest microarchitectures, etc... Basically before AsmGrid it was time consuming for me to verify whether the instructions I have selected would perform well on a majority of machines that I target.

I wrote AsmGrid initially for myself to explore AsmDB data and to spot possible errors. Then I wrote CULT just for fun as I wanted to see whether it's possible to write such tool based on AsmJit. CULT basically iterates over AsmJit instruction database, checks whether instructions (with various signatures) can be executed, and then creates JIT code for executing them either in parallel or sequencially. It works really well and the testing can be easily done in user space.

In other words, I wanted a table of instructions and their timings where I can compare several microarchitectures at the same time during development and AsmGrid provides that. The only downside is that I cannot test all microarchitectures myself and when I make changes to support more instructions a re-run is necessary.

Performance Speed Limits

Related Stories