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)
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.
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)
That's where the Trace Cache helps in tight loops.
Skylake apparently has up to 224 instructions in flight. So during those dependent 5 instructions, theoretically it could be doing some of the next hundred. Or the previous hundred.
I simply find it hard to believe that Intel would design monsters with so many out-of-order instructions, but still every random bit of software will constantly get completely stalled by dependent instructions.
Not if the next iteration of the loop not only branches on the previous result (okay, that one's easy on the predictors), but also depends on the previous iteration :)
--
The basic idea behind these designs is that
a) most software is a fat, ugly blob of shit which sometimes calls into
b) specific functions implementing high-performance algorithms (be it compression, encryption, hashing, ..., image manipulation, ...)
So for b) you want a capable design to have high throughput, and that also plays well with a) because it means that the core can spend most of it's time blocking on memory or executing an instruction or two every couple cycles. It also means that SMT works very, very well, since now you got two fat blobs smearing their shit around, but the core has more than enough resources to deal with that. That's why SMT gives 50++ % speed-ups for many applications. Because they're fat blobs.
If the intention was just to speed up hand-tuned library functions, it would be much easier to ask the library-hand-tuners to figure out instruction dependencies ahead of time (instead of doing re-ordering) and to provide a lot of registers (instead of doing renaming).
That's not a scaleable approach, i.e. only works for some set of parameters that are then set in stone after that. Changing the parameters means changing the ISA.
An ISA that did something similar was Itanium and it failed spectacularly. On the other hand, the idea to offload these optimizations to the CPU is quite old. E.g. "SPARC" is for "scaleable processor architecture" -- the scaleable part mostly refers to the number of register windows the CPUs have.
On the other hand, other processors do this with great success. Examples here are the extremely primitive cores used in HPC accelerators for the TOP500, or those used in GPUs. There this works since code can be hand-tailored to a specific computer, or because the problem itself and algorithmic approaches ensure that a compiler can generate good SIMT code (in the case of GPUs).
> are like just-in-time trace optimizers that can use run-time values to improve the optimization.
Practically no optimizations found in CPUs do that (looking at "run-time values"). Or I'm misreading you here.
That's not true. One just needs to _add_ to the ISA. That's exactly what SSE and AVX do: oodles of registers, oodles of compute power. Apparently those are to be used by those specialized libraries you mention.
OOO, register-renaming, and having the ability of hundreds of instruction in flight (!) seem more about improving general computing performance.
> Practically no optimizations found in CPUs do that (looking at "run-time values"). Or I'm misreading you here.
Modern CPUs are like essentially like trace optimizers that do depend on run-time values. For one, there's the branch predictor. Secondly, instructions may execute as soon as the dependent data becomes available. So it's possible that some memory load happens quickly because data is in L1, compared to another independent instruction doing a memory load from main memory. Since the data from one instruction arrived earlier, it can get scheduled ahead of the other -- in real time.
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.
Cheers to that :/
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.
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.
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 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:
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-desk...
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
[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.
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).
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.
Not enough by itself. The code will likely be pretty bad, unless you'll also add -march=native.
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.
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.
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.