6 ms·

The call shifts the loop from being limited at the backend level (mostly uops not being retired by having to wait for memory) to being limited at the frontend l

by pbsd 9y ago

The call shifts the loop from being limited at the backend level (mostly uops not being retired by having to wait for memory) to being limited at the frontend level. The core event to look for here is `IDQ_UOPS_NOT_DELIVERED.CORE`, which tells us whether the frontend is delivering the full 4 uops per cycle it is able to. In the tight loop this is almost always the case, whereas in the call loop this is rarely the case. CALL, RET, and JNE all share the same execution port (6 in Skylake), so it seems plausible that the added pressure in this port prevents speculative execution from continuing with the loop at the same rate as the tight loop. If you look at the execution port breakdowns of each loop, port 6 dominates in the call loop, whereas the tight loop is bottlenecked at port 4 (the port where stores go). By delivering fewer uops per cycle, the pressure on the backend is eased. But this is a delicate balance. If you add another call, the loop becomes much slower than the tight loop. You can get a similar effect by replacing `__asm__("call foo")` with __asm__("jmp 1f\n1:\n"); __asm__("jmp 1f\n1:\n"); which consumes the same amount of port 6.

exikyut 9y ago
1. Where did you learn all of this? 2. I'm... guessing that gcc/clang are too dumb to be able to be taught this and get the balance right.
- ahartmetz 9y ago
  Well, it's a highly specific situation, and what most people use - for widely deployed software - is blended code which is approximately optimal for current-ish CPUs. So probably most work goes into generating blended code. Maybe the Intel compiler can get the code exactly right for i7?
- rayiner 9y ago
  > https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf https://www.intel.com/content/dam/www/public/us/en/documents... More than you could ever want to know (but see specifically B.4.7.1).
- DannyBee 9y ago
  >2. I'm... guessing that gcc/clang are too dumb to be able to >be taught this and get the balance right. No, actually, you could model this and other things exactly. It's just not worth the cost ;)
  - nkurz 9y ago
    I think you're bluffing. I think this particular case is one that is so deep into the processor that no compiler stands a chance of modeling this exactly. :) But one optimization I'd like to see is convincing the compilers to do better on "macro-op fusion", which let "INC/JCC" type operations be treated as a single µop if they are one after the other. GCC/Clang don't seem to be aware of the benefit of this, and often gratuitously break it by splitting them up. It's a reasonably rare case where it makes a big difference, but it almost never hurts, and frequently is a small positive. Who would I need to convince to change this? What sort of benchmark would they need as motivation? Would pointing to Intel documentation possibly be sufficient?
    - exikyut 9y ago
      > It's a reasonably rare case where it makes a big difference, but it almost never hurts, and frequently is a small positive. Who would I need to convince to change this? What sort of benchmark would they need as motivation? Would pointing to Intel documentation possibly be sufficient? From someone completely naive on the compiler scene, I think I can safely say that - A benchmark with better results than it should have (ie, savings on the order of whole seconds) would obviously grab and keep attention - For finding out who to pester and/or what everyone thinks of the subject, #gcc is big-ish, #llvm is a bit smaller, and #clang is smaller still, all on freenode - presumably low activity (as seems the norm nowadays) and type-and-wait, but a lighter-weight (for want of a better term) alternative than the mailinglists. Ultimately I expect you'll end up posting to a list somewhere, but IRC sounds like a good way to get oriented first - My strong guess is that LLVM and GCC already have fairly heavily ingrained internal architecture/structure, and yeah, some convincing would be needed. - I have no idea how to get in touch with people associated with LKML off-LKML, but they seem to have opinions about generated code quality too: https://lkml.org/lkml/2017/11/10/310 https://lkml.org/lkml/2017/11/10/310 (focusing on reply at bottom, not quote; linked in https://news.ycombinator.com/item?id=15849305 https://news.ycombinator.com/item?id=15849305, from https://news.ycombinator.com/item?id=15845118 https://news.ycombinator.com/item?id=15845118)
nkurz 9y ago
I think you are on to something, but I don't think it's the final answer. Your explanation sounds true, but it doesn't really explain how greater pressure on P6 speeds things up. I'm working with a slightly modified loop that counts down rather than up, so that the loop has slightly fewer instructions. I've switched to using an "add to memory" to reduce the instruction count further. None of these seem to directly affect the speed of the loop, but here's the fastest loop I have: .p2align 3 1: addq %rax, counter(%rip) dec %rax jmp 2f 2: jne 1b rep ret On Skylake, it executes in 0.497 s. If I remove the "jump to the next instruction", it slows to 0.646 s. This agrees with your explanation. But here's the part I don't understand, and that may undercut your theory: if I change the first line to be ".p2align 4" (that is, if I increase the minimum alignment from 8 to 16) the speed is the same whether or not I have the extra jump. Even more confusingly, it's always the slower speed! Here's what port usage looks like for the two different cases (both with the same instructions, just different alignments): Fast Slow INSTR_RETIRED_ANY | 1600095750 | 1600095846 CPU_CLK_UNHALTED_CORE | 1643927320 | 2192886305 UOPS_DISPATCHED_PORT_PORT_0 | 645482071 | 774370373 UOPS_DISPATCHED_PORT_PORT_1 | 653347597 | 782702101 UOPS_DISPATCHED_PORT_PORT_2 | 299084760 | 298170998 UOPS_DISPATCHED_PORT_PORT_3 | 300474456 | 292800108 UOPS_DISPATCHED_PORT_PORT_4 | 1410210909 | 1994332142 UOPS_DISPATCHED_PORT_PORT_5 | 406138100 | 791887776 UOPS_DISPATCHED_PORT_PORT_6 | 989257513 | 1338919000 UOPS_DISPATCHED_PORT_PORT_7 | 200496146 | 209093087 From the first line we see that both Fast and Slow have the same number of instructions executed (which makes sense, since both are executing the same instructions), but down below we see very different numbers of µops dispatched! I'm not sure what to make of this, but I think this shows that it is not (solely?) a front end issue.
- nkurz 9y ago
  I still don't have an answer, but here are some more readings that might give someone a hint. Fast is with .p2align 3, Slow is with .p2align4 as above. Measurements are on Skylake with Likwid (https://github.com/RRZE-HPC/likwid/wiki/likwid-perfctr https://github.com/RRZE-HPC/likwid/wiki/likwid-perfctr). Fast Slow Runtime (RDTSC) [s] | 4.912542e-01 | 6.476124e-01 RESOURCE_STALLS_ANY | 135,743,115 |1,298,835,857 IDQ_DSB_UOPS |1,441,709,567 | 97,635 LSD_UOPS | 197,902,567 |1,999,996,841 IDQ_MITE_UOPS | 360,547,507 | 82,354 INSTR_RETIRED_ANY | 1600095725 | 1600095769 CPU_CLK_UNHALTED_CORE | 1662620966 | 2192914751 Again, these are the same instructions just with different alignment. I assume that Fast vs Slow is essentially arbitrary, although there may be cache line effects such that only the smaller alignment has the chance of being fast. First, RESOURCE_STALLS_ANY is picking up some important difference. Slow has lots, Fast has fewer. Breaking these down to see what subtype it is might give an exact answer: https://download.01.org/perfmon/index/skylake.html https://download.01.org/perfmon/index/skylake.html. It's not RESOURCE_STALLS_SB that changes, but the others don't seem to be predefined. LSD_UOPS is the number of µops delivered by the "Loop Stream Detector", which is the smallest and fastest cache for instructions. It's very small, and only works for tiny loops. Usually this is where you want the µops to stream from, but in this case using it results in a slower final result. IDQ_DSB_UOPS is the number of µops delivered from the "Decode Stream Buffer". This is usually slightly slower than the "Loop Stream Buffer", but in this case using it produces a faster result. This is large enough to hold a reasonably sized function. IDQ_MITE_UOPS is the "legacy" instruction decoder. This is the normal path by which instructions are decoded into µops. It's always used the first time instructions are encountered, but for hot loops and hot functions the results can be cached. Usually you'd like to see less of this, but here using the legacy decoding path gives a faster result. What does this mean? It probably means that something about the alignment combined with the jump defeats what would normally be the fastest µop cache. This isn't that strange in itself, but the oddity is that for some reason, this causes an overall faster result. Why? I'd thought it was something to do with "store forwarding", and it still might be, but I haven't found any counters that directly point to that as being the problem. Instead, I think it might have to do with the processor getting too far ahead on the reads and stores, and then having to redo them once it realizes that the data is out of date. Somehow having fewer instructions available in the reorder buffer (because they are coming in from a slightly slower decoder) improves overall performance. But I don't yet understand the specifics. I'm going to stop for the night, but I'd love to wake up to someone revealing the "true" answer!

by pbsd 9y ago

exikyut 9y ago

1. Where did you learn all of this? 2. I'm... guessing that gcc/clang are too dumb to be able to be taught this and get the balance right.

ahartmetz 9y ago
Well, it's a highly specific situation, and what most people use - for widely deployed software - is blended code which is approximately optimal for current-ish CPUs. So probably most work goes into generating blended code. Maybe the Intel compiler can get the code exactly right for i7?
rayiner 9y ago
> https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf https://www.intel.com/content/dam/www/public/us/en/documents... More than you could ever want to know (but see specifically B.4.7.1).
DannyBee 9y ago
>2. I'm... guessing that gcc/clang are too dumb to be able to >be taught this and get the balance right. No, actually, you could model this and other things exactly. It's just not worth the cost ;)
- nkurz 9y ago
  I think you're bluffing. I think this particular case is one that is so deep into the processor that no compiler stands a chance of modeling this exactly. :) But one optimization I'd like to see is convincing the compilers to do better on "macro-op fusion", which let "INC/JCC" type operations be treated as a single µop if they are one after the other. GCC/Clang don't seem to be aware of the benefit of this, and often gratuitously break it by splitting them up. It's a reasonably rare case where it makes a big difference, but it almost never hurts, and frequently is a small positive. Who would I need to convince to change this? What sort of benchmark would they need as motivation? Would pointing to Intel documentation possibly be sufficient?
  - exikyut 9y ago
    > It's a reasonably rare case where it makes a big difference, but it almost never hurts, and frequently is a small positive. Who would I need to convince to change this? What sort of benchmark would they need as motivation? Would pointing to Intel documentation possibly be sufficient? From someone completely naive on the compiler scene, I think I can safely say that - A benchmark with better results than it should have (ie, savings on the order of whole seconds) would obviously grab and keep attention - For finding out who to pester and/or what everyone thinks of the subject, #gcc is big-ish, #llvm is a bit smaller, and #clang is smaller still, all on freenode - presumably low activity (as seems the norm nowadays) and type-and-wait, but a lighter-weight (for want of a better term) alternative than the mailinglists. Ultimately I expect you'll end up posting to a list somewhere, but IRC sounds like a good way to get oriented first - My strong guess is that LLVM and GCC already have fairly heavily ingrained internal architecture/structure, and yeah, some convincing would be needed. - I have no idea how to get in touch with people associated with LKML off-LKML, but they seem to have opinions about generated code quality too: https://lkml.org/lkml/2017/11/10/310 https://lkml.org/lkml/2017/11/10/310 (focusing on reply at bottom, not quote; linked in https://news.ycombinator.com/item?id=15849305 https://news.ycombinator.com/item?id=15849305, from https://news.ycombinator.com/item?id=15845118 https://news.ycombinator.com/item?id=15845118)

nkurz 9y ago

I think you are on to something, but I don't think it's the final answer. Your explanation sounds true, but it doesn't really explain how greater pressure on P6 speeds things up. I'm working with a slightly modified loop that counts down rather than up, so that the loop has slightly fewer instructions. I've switched to using an "add to memory" to reduce the instruction count further. None of these seem to directly affect the speed of the loop, but here's the fastest loop I have: .p2align 3 1: addq %rax, counter(%rip) dec %rax jmp 2f 2: jne 1b rep ret On Skylake, it executes in 0.497 s. If I remove the "jump to the next instruction", it slows to 0.646 s. This agrees with your explanation. But here's the part I don't understand, and that may undercut your theory: if I change the first line to be ".p2align 4" (that is, if I increase the minimum alignment from 8 to 16) the speed is the same whether or not I have the extra jump. Even more confusingly, it's always the slower speed! Here's what port usage looks like for the two different cases (both with the same instructions, just different alignments): Fast Slow INSTR_RETIRED_ANY | 1600095750 | 1600095846 CPU_CLK_UNHALTED_CORE | 1643927320 | 2192886305 UOPS_DISPATCHED_PORT_PORT_0 | 645482071 | 774370373 UOPS_DISPATCHED_PORT_PORT_1 | 653347597 | 782702101 UOPS_DISPATCHED_PORT_PORT_2 | 299084760 | 298170998 UOPS_DISPATCHED_PORT_PORT_3 | 300474456 | 292800108 UOPS_DISPATCHED_PORT_PORT_4 | 1410210909 | 1994332142 UOPS_DISPATCHED_PORT_PORT_5 | 406138100 | 791887776 UOPS_DISPATCHED_PORT_PORT_6 | 989257513 | 1338919000 UOPS_DISPATCHED_PORT_PORT_7 | 200496146 | 209093087 From the first line we see that both Fast and Slow have the same number of instructions executed (which makes sense, since both are executing the same instructions), but down below we see very different numbers of µops dispatched! I'm not sure what to make of this, but I think this shows that it is not (solely?) a front end issue.

nkurz 9y ago
I still don't have an answer, but here are some more readings that might give someone a hint. Fast is with .p2align 3, Slow is with .p2align4 as above. Measurements are on Skylake with Likwid (https://github.com/RRZE-HPC/likwid/wiki/likwid-perfctr https://github.com/RRZE-HPC/likwid/wiki/likwid-perfctr). Fast Slow Runtime (RDTSC) [s] | 4.912542e-01 | 6.476124e-01 RESOURCE_STALLS_ANY | 135,743,115 |1,298,835,857 IDQ_DSB_UOPS |1,441,709,567 | 97,635 LSD_UOPS | 197,902,567 |1,999,996,841 IDQ_MITE_UOPS | 360,547,507 | 82,354 INSTR_RETIRED_ANY | 1600095725 | 1600095769 CPU_CLK_UNHALTED_CORE | 1662620966 | 2192914751 Again, these are the same instructions just with different alignment. I assume that Fast vs Slow is essentially arbitrary, although there may be cache line effects such that only the smaller alignment has the chance of being fast. First, RESOURCE_STALLS_ANY is picking up some important difference. Slow has lots, Fast has fewer. Breaking these down to see what subtype it is might give an exact answer: https://download.01.org/perfmon/index/skylake.html https://download.01.org/perfmon/index/skylake.html. It's not RESOURCE_STALLS_SB that changes, but the others don't seem to be predefined. LSD_UOPS is the number of µops delivered by the "Loop Stream Detector", which is the smallest and fastest cache for instructions. It's very small, and only works for tiny loops. Usually this is where you want the µops to stream from, but in this case using it results in a slower final result. IDQ_DSB_UOPS is the number of µops delivered from the "Decode Stream Buffer". This is usually slightly slower than the "Loop Stream Buffer", but in this case using it produces a faster result. This is large enough to hold a reasonably sized function. IDQ_MITE_UOPS is the "legacy" instruction decoder. This is the normal path by which instructions are decoded into µops. It's always used the first time instructions are encountered, but for hot loops and hot functions the results can be cached. Usually you'd like to see less of this, but here using the legacy decoding path gives a faster result. What does this mean? It probably means that something about the alignment combined with the jump defeats what would normally be the fastest µop cache. This isn't that strange in itself, but the oddity is that for some reason, this causes an overall faster result. Why? I'd thought it was something to do with "store forwarding", and it still might be, but I haven't found any counters that directly point to that as being the problem. Instead, I think it might have to do with the processor getting too far ahead on the reads and stores, and then having to redo them once it realizes that the data is out of date. Somehow having fewer instructions available in the reorder buffer (because they are coming in from a slightly slower decoder) improves overall performance. But I don't yet understand the specifics. I'm going to stop for the night, but I'd love to wake up to someone revealing the "true" answer!