5 ms·

"Code that runs OK-ish on that CPU averages around 1 instruction per cycle, well-optimized code around 3 instructions per cycle." Is unoptimized code really th

by ant6n 10y ago

"Code that runs OK-ish on that CPU averages around 1 instruction per cycle, well-optimized code around 3 instructions per cycle." Is unoptimized code really that bad? I thought between modern compilers and supporting 4 op/cycle with out-of-order execution, a new Kaby Lake cpu would get more than 1 cycle overall. Or are the branch delays just killing the performance? (Code is small relative to data, most of it should be in cache most of the time)

deleted 10y ago
[deleted]
inetknght 10y ago
Yes, unoptimized code is really that bad. Moreover, optimized code is able to do more with less (by not repeating itself). Unoptimized code sits and does the same thing over and over. Then there's parallelism (threads and, in particular, SIMD); use right, it works great. Use wrong and it only expands your memory bandwidth requirements (and kills your effective instructions per cycle).
- ant6n 10y ago
  The author wrote "OK-ish" code. I think code that is OK is one that was compiled with -o3, like basically all code in release mode. 'optimized' in this context should mean somebody spent time to make it faster. In this discussion, doing something 'over and over', or doing less with more is a consideration at a higher level, and shouldn't play into this. This is about instructions per cycle, so being able to only do one instruction per cycle on average should only be due to continuous streams of dependent instructions, waiting on branches and waiting on memory.
  - panic 10y ago
    Intel CPUs run one micro-op per execution port per cycle (see section 2.3.4 of http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf http://www.intel.com/content/dam/www/public/us/en/documents/... for details, though the manual is a bit out of date -- more recent CPUs have more ports: http://www.anandtech.com/show/6355/intels-haswell-architecture/8 http://www.anandtech.com/show/6355/intels-haswell-architectu...). Optimized code has to be written with execution port utilization in mind.
    - ant6n 10y ago
      I'm not disputing that ... I just thought that out-of-order execution was supposed to deal with that to an extend, with tens to even hundreds instruction in flight at a time.
    - gpderetta 10y ago
      There are so many execution ports compared to the throughput of decoding, renaming and retiring, that they are rarely the bottleneck. As ant6n correctly pointed, memory latency, branch prediction, dependency chain length, decoding and renaming are, in that order, normally the bottleneck even for hand optimized assembler code.
  - vardump 10y ago
    -o3? I'm assuming you mean gcc -O3. Not enough by itself. The code will likely be pretty bad, unless you'll also add -march=native.
Jweb_Guru 10y ago
> Is unoptimized code really that bad? Absolutely. Compilers can't do much about poor locality and most code is not written with locality in mind. And in many cases locality isn't really much of an option anyway; for instance, think about a key-value dictionary much larger than cache, responding to random requests. People have contrived ways of trying to make these cache-friendly but they generally end up slower than a really well-optimized hash lookup. You can improve it further in some cases by using prefetching extensively and trading memory bandwidth for latency, but as the article points out that can actually be a really terrible idea. So without further knowledge of the workload there just isn't a lot you can do.
- fulafel 10y ago
  To refine: popular compilers don't do much about poor locality. It's very possible do this but you need the language to permit it and the compiler engineering done. Data optimizations have for some reason received too litlte attention for a long time. For example, most key-value dictionaries could shave off 50-90% of their memory use if the value ranges and key counts were optimized for, along with unboxing.
  - deleted 10y ago
    [deleted]
dom0 10y ago
> Is unoptimized code really that bad? Most application code is far worse and stalls (sadly - almost literally) every few instructions for L2 / memory. > (Code is small relative to data, most of it should be in cache most of the time) Not if your application is dragging two and a half invasive runtimes around.
- socmag 10y ago
  > Not if your application is dragging two and a half invasive runtimes around. Cheers to that :/
jandrewrogers 10y ago
Saturating the execution ports in a modern CPU is something compilers demonstrably have a difficult time doing automatically because the the code involved in this optimization has poor locality by definition. Compilers tend to have a bit of tunnel vision to a very local context so that operation relationships are easily analyzed. Optimizing this requires detecting patterns in scattered parts of the code and reorganizing the code in a functionally neutral way. Not difficult to do but the human programmer has to do the work because it requires a higher level view of code sequencing relationships. It doesn't produce code that is any less obvious or readable in my experience. Even on older Sandybridge CPUs, I often saw upwards of 2x throughput by mildly reorganizing perfectly correct C++ for better operation concurrency. Writing code that is well-optimized in this regard becomes natural with awareness and experience. Optimizing cache line hit rates has an even higher throughput improvement than execution port saturation but is a similar optimization.
- dom0 10y ago
  I don't think it's even possible any more. Haswell and later are 8-wide designs, but can only fetch+decode and retire 4 instructions per cycle (peak). So one would need ops that decode to 2+ execution-unit independent µops. Linear data-dependent algorithms are also such a huge pain: "Why does that only shovel 500 MB/s?" Well... five instructions long dependency chain, that's why! (Yes, the last bit may be a bit unrelated to the discussion at hand)
  - kbwt 10y ago
    > 8-wide designs, but can only fetch+decode and retire 4 instructions per cycle That's where the Trace Cache helps in tight loops.
    - dom0 10y ago
      The µop cache (trace cache went out the window) doesn't help with fetching instructions AIUI, but accelerates decoding them. So the 4 insns/cycle fetch bandwidth is not changed by that.
  - 10y ago
fulafel 10y ago
Put another way, he's saying if the dataset doesn't fit in cache, it's bottlenecked on memory rather than the CPU's computational resources. It might still be good code. Transforming an arbitrary computational task to a perfectly balanced "n operations of computation per n bytes of data accessed" suited to hardware du jour is a not a generally solved problem, as much as programmers like to talk about memory/speed tradeoffs.
- ant6n 10y ago
  I understand the overall point of the article is about memory blocking cpu; but the author uses the idea of instruction through-put instruction-memory/cycle a way to show that the throughput isn't enough just to execute code. So in order to make that argument, you'd have to look at the instruction through-put without the assumption of memory accesses slowing you down. Otherwise the point comparing cpu speed vs memory speed is moot, if you start with the assumption that cpu speed is bound by memory speed to begin with.
- jfoutz 10y ago
  > Transforming an arbitrary computational task to a perfectly balanced ... I think that's halting problem level difficulty there. We can probably do neat things for special cases, but i seriously doubt it's generally solvable.
gvb 10y ago
I thought between modern compilers and supporting 4 op/cycle with out-of-order execution, a new Kaby Lake cpu would get more than 1 cycle overall. Or are the branch delays just killing the performance? The problem at the level of how many operations per cycle is data dependencies. A lot of code is assignments to variables and subsequent use of those variables in calculations, etc. Simplistic example: a = 1; b = 2; c = a + b; The assignment to variable "c" stalls until "a" and "b" assignments are completed. Obviously, in real life the assignments of "a" and "b" would generally be other complicated assignments that are dependent on other variables, functions, calculations, etc. The x86 is additionally hampered by its relative lack of registers. This is hidden to some extent by using register renaming so that the CPU actually has multiple instances of register e.g. AX and tracks the dependencies. Ref: https://en.wikipedia.org/wiki/Register_allocation https://en.wikipedia.org/wiki/Register_allocation https://en.wikipedia.org/wiki/Register_renaming https://en.wikipedia.org/wiki/Register_renaming
- ant6n 10y ago
  Skylake has up to 224 instructions in flight [1], apparently on multiple branches. This compares to your 3 instruction example. I think it's a valid question whether this doesn't imply we get more than 1 instruction/cycle, even for code that isn't hand-optimized (i.e. just usual code optimized by the compiler), assuming that the work load isn't data-memory bound. [1] http://www.anandtech.com/show/9582/intel-skylake-mobile-desktop-launch-architecture-analysis/5 http://www.anandtech.com/show/9582/intel-skylake-mobile-desk...
  - gvb 10y ago
    You will get the number of instructions in parallel that is the minimum of (a) the number of instructions that can be handled by the hardware simultaneously and (b) the number of instructions that don't have inter-dependencies. My example was not a 3 instruction example. It was a minimum example of data dependencies. In the example, until the CPU can resolve what the value of the variable (register) "a" is, it cannot do the calculation for the variable "c". Most programs have a high level of data inter-dependencies. Conditional branches are major class of data inter-dependency - the CPU cannot execute code beyond the branch[1] until it knows which branch it will take. There is a class of programs that are "embarrassingly parallel" that having more execution units will speed them up, ideally linearly (graphics GPUs are a classic example). "Garden variety" programs end up under utilizing execution units because the execution unit assigned to calculate "c" (from my example) will be stalled waiting for execution units assigned to calculate "a" and "b" to complete their calculations. This is related to the long unrealized, and still unrealized, promise of VLIW architectures. https://en.wikipedia.org/wiki/Very_long_instruction_word https://en.wikipedia.org/wiki/Very_long_instruction_word [1] A small-ish lie: many processors nowadays do "speculative execution" where they guess which branch will be taken and execute ahead. If they guess right, they win. If they guess wrong, they throw away the work they did and restart the execution on the other branch.

by ant6n 10y ago

deleted 10y ago

[deleted]

inetknght 10y ago

Yes, unoptimized code is really that bad. Moreover, optimized code is able to do more with less (by not repeating itself). Unoptimized code sits and does the same thing over and over. Then there's parallelism (threads and, in particular, SIMD); use right, it works great. Use wrong and it only expands your memory bandwidth requirements (and kills your effective instructions per cycle).

ant6n 10y ago
The author wrote "OK-ish" code. I think code that is OK is one that was compiled with -o3, like basically all code in release mode. 'optimized' in this context should mean somebody spent time to make it faster. In this discussion, doing something 'over and over', or doing less with more is a consideration at a higher level, and shouldn't play into this. This is about instructions per cycle, so being able to only do one instruction per cycle on average should only be due to continuous streams of dependent instructions, waiting on branches and waiting on memory.
- panic 10y ago
  Intel CPUs run one micro-op per execution port per cycle (see section 2.3.4 of http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf http://www.intel.com/content/dam/www/public/us/en/documents/... for details, though the manual is a bit out of date -- more recent CPUs have more ports: http://www.anandtech.com/show/6355/intels-haswell-architecture/8 http://www.anandtech.com/show/6355/intels-haswell-architectu...). Optimized code has to be written with execution port utilization in mind.
  - ant6n 10y ago
    I'm not disputing that ... I just thought that out-of-order execution was supposed to deal with that to an extend, with tens to even hundreds instruction in flight at a time.
  - gpderetta 10y ago
    There are so many execution ports compared to the throughput of decoding, renaming and retiring, that they are rarely the bottleneck. As ant6n correctly pointed, memory latency, branch prediction, dependency chain length, decoding and renaming are, in that order, normally the bottleneck even for hand optimized assembler code.
- vardump 10y ago
  -o3? I'm assuming you mean gcc -O3. Not enough by itself. The code will likely be pretty bad, unless you'll also add -march=native.

Jweb_Guru 10y ago

> Is unoptimized code really that bad? Absolutely. Compilers can't do much about poor locality and most code is not written with locality in mind. And in many cases locality isn't really much of an option anyway; for instance, think about a key-value dictionary much larger than cache, responding to random requests. People have contrived ways of trying to make these cache-friendly but they generally end up slower than a really well-optimized hash lookup. You can improve it further in some cases by using prefetching extensively and trading memory bandwidth for latency, but as the article points out that can actually be a really terrible idea. So without further knowledge of the workload there just isn't a lot you can do.

fulafel 10y ago
To refine: popular compilers don't do much about poor locality. It's very possible do this but you need the language to permit it and the compiler engineering done. Data optimizations have for some reason received too litlte attention for a long time. For example, most key-value dictionaries could shave off 50-90% of their memory use if the value ranges and key counts were optimized for, along with unboxing.
- deleted 10y ago
  [deleted]

dom0 10y ago

> Is unoptimized code really that bad? Most application code is far worse and stalls (sadly - almost literally) every few instructions for L2 / memory. > (Code is small relative to data, most of it should be in cache most of the time) Not if your application is dragging two and a half invasive runtimes around.

socmag 10y ago
> Not if your application is dragging two and a half invasive runtimes around. Cheers to that :/

jandrewrogers 10y ago

Saturating the execution ports in a modern CPU is something compilers demonstrably have a difficult time doing automatically because the the code involved in this optimization has poor locality by definition. Compilers tend to have a bit of tunnel vision to a very local context so that operation relationships are easily analyzed. Optimizing this requires detecting patterns in scattered parts of the code and reorganizing the code in a functionally neutral way. Not difficult to do but the human programmer has to do the work because it requires a higher level view of code sequencing relationships. It doesn't produce code that is any less obvious or readable in my experience. Even on older Sandybridge CPUs, I often saw upwards of 2x throughput by mildly reorganizing perfectly correct C++ for better operation concurrency. Writing code that is well-optimized in this regard becomes natural with awareness and experience. Optimizing cache line hit rates has an even higher throughput improvement than execution port saturation but is a similar optimization.

dom0 10y ago
I don't think it's even possible any more. Haswell and later are 8-wide designs, but can only fetch+decode and retire 4 instructions per cycle (peak). So one would need ops that decode to 2+ execution-unit independent µops. Linear data-dependent algorithms are also such a huge pain: "Why does that only shovel 500 MB/s?" Well... five instructions long dependency chain, that's why! (Yes, the last bit may be a bit unrelated to the discussion at hand)
- kbwt 10y ago
  > 8-wide designs, but can only fetch+decode and retire 4 instructions per cycle That's where the Trace Cache helps in tight loops.
  - dom0 10y ago
    The µop cache (trace cache went out the window) doesn't help with fetching instructions AIUI, but accelerates decoding them. So the 4 insns/cycle fetch bandwidth is not changed by that.
- 10y ago

fulafel 10y ago

Put another way, he's saying if the dataset doesn't fit in cache, it's bottlenecked on memory rather than the CPU's computational resources. It might still be good code. Transforming an arbitrary computational task to a perfectly balanced "n operations of computation per n bytes of data accessed" suited to hardware du jour is a not a generally solved problem, as much as programmers like to talk about memory/speed tradeoffs.

ant6n 10y ago
I understand the overall point of the article is about memory blocking cpu; but the author uses the idea of instruction through-put instruction-memory/cycle a way to show that the throughput isn't enough just to execute code. So in order to make that argument, you'd have to look at the instruction through-put without the assumption of memory accesses slowing you down. Otherwise the point comparing cpu speed vs memory speed is moot, if you start with the assumption that cpu speed is bound by memory speed to begin with.
jfoutz 10y ago
> Transforming an arbitrary computational task to a perfectly balanced ... I think that's halting problem level difficulty there. We can probably do neat things for special cases, but i seriously doubt it's generally solvable.

gvb 10y ago

I thought between modern compilers and supporting 4 op/cycle with out-of-order execution, a new Kaby Lake cpu would get more than 1 cycle overall. Or are the branch delays just killing the performance? The problem at the level of how many operations per cycle is data dependencies. A lot of code is assignments to variables and subsequent use of those variables in calculations, etc. Simplistic example: a = 1; b = 2; c = a + b; The assignment to variable "c" stalls until "a" and "b" assignments are completed. Obviously, in real life the assignments of "a" and "b" would generally be other complicated assignments that are dependent on other variables, functions, calculations, etc. The x86 is additionally hampered by its relative lack of registers. This is hidden to some extent by using register renaming so that the CPU actually has multiple instances of register e.g. AX and tracks the dependencies. Ref: https://en.wikipedia.org/wiki/Register_allocation https://en.wikipedia.org/wiki/Register_allocation https://en.wikipedia.org/wiki/Register_renaming https://en.wikipedia.org/wiki/Register_renaming

ant6n 10y ago
Skylake has up to 224 instructions in flight [1], apparently on multiple branches. This compares to your 3 instruction example. I think it's a valid question whether this doesn't imply we get more than 1 instruction/cycle, even for code that isn't hand-optimized (i.e. just usual code optimized by the compiler), assuming that the work load isn't data-memory bound. [1] http://www.anandtech.com/show/9582/intel-skylake-mobile-desktop-launch-architecture-analysis/5 http://www.anandtech.com/show/9582/intel-skylake-mobile-desk...
- gvb 10y ago
  You will get the number of instructions in parallel that is the minimum of (a) the number of instructions that can be handled by the hardware simultaneously and (b) the number of instructions that don't have inter-dependencies. My example was not a 3 instruction example. It was a minimum example of data dependencies. In the example, until the CPU can resolve what the value of the variable (register) "a" is, it cannot do the calculation for the variable "c". Most programs have a high level of data inter-dependencies. Conditional branches are major class of data inter-dependency - the CPU cannot execute code beyond the branch[1] until it knows which branch it will take. There is a class of programs that are "embarrassingly parallel" that having more execution units will speed them up, ideally linearly (graphics GPUs are a classic example). "Garden variety" programs end up under utilizing execution units because the execution unit assigned to calculate "c" (from my example) will be stalled waiting for execution units assigned to calculate "a" and "b" to complete their calculations. This is related to the long unrealized, and still unrealized, promise of VLIW architectures. https://en.wikipedia.org/wiki/Very_long_instruction_word https://en.wikipedia.org/wiki/Very_long_instruction_word [1] A small-ish lie: many processors nowadays do "speculative execution" where they guess which branch will be taken and execute ahead. If they guess right, they win. If they guess wrong, they throw away the work they did and restart the execution on the other branch.