Hacker News Reader

Comment by johnbender | Hacker News Reader

To add just a bit more:

When assignments to variables happen in the context of a procedure call it's preferable to use registers for performance reasons since memory access (even cache) is much slower by comparison. Unfortunately registers are a limited resource, so we would like to reuse them when a variable, though in scope, isn't "live" or in use.

This whole area of optimization is called register allocation and the optimal solution reduces to the graph coloring problem which is NP-complete. As a result there are a myriad of approximation algorithms with knobs to turn to spend a bit more complexity for a bit more accuracy. This patch appears to be the turning of one such knob.

View on HN

Graph coloring is a small part of register allocation, and not the hard part. It's also not NP complete on interference graphs built from SSA form, which most modern compilers (though not GCC) use in the backend. In fact, it's linear time optimally solvable if you build ssi form, which can be done in linear time.

The optimal spilling and rematerialization problems have not yet shown to be solvable in polynomial time on these forms, but folks are working on it.

The bit about SSI form is news to me. I have more research to do.

See http://web.cs.ucla.edu/~palsberg/paper/PereiraPalsberg08.pdf Look at page 10.

(Fernando was once my intern, back in the day ;P)

Also, something being NP complete does not say much about whether it is hard to do in the real world. Exponential is fine, as long as the constant, the value of n, or the exponent aren't too large.

Here, real world cases likely will have only a fairly limited number of registers and only a limited (but potentially very long) length of code to optimize across.

It would be interesting (and quite an accomplishment, even if doesn't give significant performance gains) to combine this with whole-program optimization (imagine optimizing the calling conventions on a per-function basis, and considering generating code for a function twice, with different calling conventions) and/or with the code that decides what functions to inline, but AFAIK, nobody does that.

"Here, real world cases likely will have only a fairly limited number of registers and only a limited (but potentially very long) length of code to optimize across. "

You can do a good job with polynomial time heuristics (chaitin's heuristic) for coloring, however, you are wrong about the code. It is often very weird. At the same time, most of the performance issue is not coloring, or trying not to spill at all. The problem is deciding where to split live ranges (which introduces copies), where to merge existing live ranges (which removes copies at a cost of more interferences), where to spill, where to remat, are quite hard.

I thought L1 cache access cost the same as register access on Intel machines. Is this not true?

Just something I had heard somewhere; I don't have data to back it up.

I think register access is technically faster than a L1 hit, but due to store forwarding from the write back cache, this extra latency is usually not visible, so in practice they're the same.

You need two additional (micro)instructions, a store and a load. Store forwarding will save you from going to the cache and back, but it won't be as fast a register forwarding.

Yes. In particular store forwarding is slightly slower [1] than (or, in Skylake, as fast as) a plain L1 load. This still beats waiting for the dependent store to complete, but it is nowhere as fast as using a direct register reference.

[1] i.e. higher latency.

No, it's not true. Even if L1 accesses were only 1 cycle, they would be slower. The CPU will try to execute instructions out-of-order and needs to detect dependencies and possible conflicts between instructions. This is easy with registers, if the registers are the same (have the same name), there may be conflicts or dependencies. This can be tested right after decoding the instruction. With memory it's much more complex, because the memory addresses have to be calculated before any comparisons can be made. Therefore it's much harder to reorder memory instructions. There are some exceptions, like push/pop pairs, but in general memory accesses will be significantly slower.

Makes sense, thanks!

Reply on news.ycombinator.com