6 ms·

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

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 7y ago
There is a small typo under the "Pipeline Width" Heading. Superscalar link is "Supercalar"
- BeeOnRope 7y ago
  Thanks, fixed and credited.
  - hyperpape 7y ago
    Really nice article. Near the end of the Carried Dependency Chains section, you have another typo: "transforamtion".
    - BeeOnRope 7y ago
      Thanks, fixed and credited. I'm glad I'm not paying by the typo, I'd be broke by now (one person alone identified ~15 typos).
      - caf 7y ago
        Under "Out of Order Limits", ...which all effect the... should be ...which all affect the... Under "Calls in Flight", Only 14-15 to calls... should be Only 14-15 calls... In footnote 17, ...compilers will often cannot.. should probably be just ...compilers often cannot.... In footnote 19, Node that LSD... should be Note that LSD...
        BeeOnRope 7y ago
        Thanks! Fixed and credited.
nkurz 7y 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/ https://darekkay.com/blog/static-site-comments/.
- BeeOnRope 7y 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 7y ago
This is very practical guide, thanks for sharing.
vardump 7y ago
Very good, you clearly got a very accurate grasp of the low level details. Thanks for writing such an informative guide!
vnorilo 7y 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!
- BeeOnRope 7y 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 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 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 7y ago
Nice work - thank you!
agumonkey 7y ago
Do you have books or lectures on the topic or do you go from scratch and pure brain juice ?
- BeeOnRope 7y 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 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.
  - agumonkey 7y ago
    Thanks a ton, both article and answer :)
mr_luc 7y 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_threaded_code 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)
- caf 7y 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).
RivieraKid 7y 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.
- BeeOnRope 7y 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 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).
  - RivieraKid 7y ago
    It makes complete sense now, appreciate the explanation.
  - 7y ago
caf 7y ago
Do 'ret' instructions count against the branch order buffer, since they're essentially indirect branches?
- BeeOnRope 7y 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.
haberman 7y 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?
- nkurz 7y 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.
  - BeeOnRope 7y ago
    Because that's not how the ROB or any of the other "in order" structures like the load buffers, etc, work. Fundamentally, retirement happens in order. uops only leave the ROB when they retire, and they retire in the same order as they appear in the dynamic instruction steam. The ROB is needed to preserve the ability to roll back if any instruction faults, to handle interrupts, to generate precise exceptions, etc: think about what would happen if you had retired a bunch of random instructions on either side of an un-retired instruction that ended up faulting? Everything is speculative. The CPU always operates as if any unretired instruction is speculative. In reality it almost is: probably at least a quarter of all instructions can fault in some way, and as soon as there is any such instruction in the unretired stream all younger instructions are "speculative". I'm putting it in quotes because "speculative" as we're discussing it just something we are making up: CPUs don't have a "I'm speculating" flag: everything is treated as speculative all the time (and if you consider interrupts, maybe even the cases where you have a stream of cannot-fault instructions would also be "speculative"). There is a structure that works as you describe: the scheduler/reservation station. That's the place where everything happens out of order and slow instructions can stall and be passed by younger ones who leave the scheduler and make room for others - but this sits within the in-order allocate + retire machinery.

maztheman 7y ago

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

BeeOnRope 7y ago
Thanks, fixed and credited.
- hyperpape 7y ago
  Really nice article. Near the end of the Carried Dependency Chains section, you have another typo: "transforamtion".
  - BeeOnRope 7y ago
    Thanks, fixed and credited. I'm glad I'm not paying by the typo, I'd be broke by now (one person alone identified ~15 typos).
    - caf 7y ago
      Under "Out of Order Limits", ...which all effect the... should be ...which all affect the... Under "Calls in Flight", Only 14-15 to calls... should be Only 14-15 calls... In footnote 17, ...compilers will often cannot.. should probably be just ...compilers often cannot.... In footnote 19, Node that LSD... should be Note that LSD...
      - BeeOnRope 7y ago
        Thanks! Fixed and credited.

nkurz 7y 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/ https://darekkay.com/blog/static-site-comments/.

BeeOnRope 7y 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 7y ago

This is very practical guide, thanks for sharing.

vardump 7y ago

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

vnorilo 7y 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!

BeeOnRope 7y 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 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 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 7y ago

Nice work - thank you!

agumonkey 7y ago

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

BeeOnRope 7y 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 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.
- agumonkey 7y ago
  Thanks a ton, both article and answer :)

mr_luc 7y 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_threaded_code 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)

caf 7y 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).

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

BeeOnRope 7y 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 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).
- RivieraKid 7y ago
  It makes complete sense now, appreciate the explanation.
- 7y ago

caf 7y ago

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

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

haberman 7y 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?

nkurz 7y 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.
- BeeOnRope 7y ago
  Because that's not how the ROB or any of the other "in order" structures like the load buffers, etc, work. Fundamentally, retirement happens in order. uops only leave the ROB when they retire, and they retire in the same order as they appear in the dynamic instruction steam. The ROB is needed to preserve the ability to roll back if any instruction faults, to handle interrupts, to generate precise exceptions, etc: think about what would happen if you had retired a bunch of random instructions on either side of an un-retired instruction that ended up faulting? Everything is speculative. The CPU always operates as if any unretired instruction is speculative. In reality it almost is: probably at least a quarter of all instructions can fault in some way, and as soon as there is any such instruction in the unretired stream all younger instructions are "speculative". I'm putting it in quotes because "speculative" as we're discussing it just something we are making up: CPUs don't have a "I'm speculating" flag: everything is treated as speculative all the time (and if you consider interrupts, maybe even the cases where you have a stream of cannot-fault instructions would also be "speculative"). There is a structure that works as you describe: the scheduler/reservation station. That's the place where everything happens out of order and slow instructions can stall and be passed by younger ones who leave the scheduler and make room for others - but this sits within the in-order allocate + retire machinery.