How do the .NET JITs optimise generated code layout?

Question

Back in 2009 I posted this answer to a question about optimisations for nested try/catch/finally blocks.

Thinking about this again some years later, it seems the question could be extended to that other control flow, not only try/catch/finally, but also if/else.

At each of these junctions, execution will follow one path. Code must be generated for both, obviously, but the order in which they're placed in memory, and the number of jumps required to navigate through them will differ.

The order generated code is laid out in memory has implications for the miss rate on the CPU's instruction cache. Having the instruction pipeline stalled, waiting for memory reads, can really kill loop performance.

I don't think loops (for/foreach/while) are a such a good fit unless you expect the loop have zero iterations more often than it has some, as the natural generation order seems pretty optimal.

Some questions:

• In what ways do the available .NET JITs optimise for generated instruction order?
• How much difference can this make in practice to common code? What about perfectly suited cases?
• Is there anything the developer can do to influence this layout? What about mangling with the forbidden goto?
• Does the specific JIT being used make much difference to layout?
• Does the method inlining heuristic come into play here too?
• Basically anything interesting related to this aspect of the JIT!

---

Some initial thoughts:

Moving catch blocks out of line is an easy job, as they're supposed to be the exceptional case by definition. Not sure this happens.

For some loops I suspect you can increase performance non-trivially. However in general I don't think it'll make that much difference.

I don't know how the JIT decides the order of generated code. In C on Linux you have likely(cond) and unlikely(cond) which you can use to tell to the compiler which branch is the common path to optimise for. I'm not sure that all compilers respect these macros.

Instruction ordering is distinct from the problem of branch prediction, in which the CPU guesses (on its own, afaik) which branch will be taken in order to start the pipeline (oversimplied steps: decode, fetch operands, execute, write back) on instructions, before the execute step has determined the value of the condition variable.

I can't think of any way to influence this order in the C# language. Perhaps you can manipulate it a bit by gotoing to labels explicitly, but is this portable, and are there any other problems with it?

Perhaps this is what profile guided optimisation is for. Do we have that in the .NET ecosystem, now or in plan? Maybe I'll go and have a read about LLILC.

Answer 1

The optimization you are referring to is called the code layout optimization which is defined as follows:

• Those pieces of code that are executed close in time in the same thread should be be close in the virtual address space so that they fit in a single or few consecutive cache lines. This reduces cache misses.
• Those pieces of code that are executed close in time in different threads should be be close in the virtual address space so that they fit in a single or few consecutive cache lines as long as there is no self-modifying code. This gets lower priority than the previous one. This reduces cache misses.
• Those pieces of code that are executed frequently (hot code) should be close in the virtual address space so that they fit in as few virtual pages as possible. This reduces page faults and working set size.
• Those pieces of code that are rarely executed (cold code) should be close in the virtual address space so that they fit in as few virtual pages as possible. This reduces page faults and working set size.

Now to your questions.

In what ways do the available .NET JITs optimise for generated instruction order?

"Instruction order" is really a very general term. Many optimizations affect instruction order. I'll assume that you're referring to code layout.

JITters by design should take the minimum amount of time to compile code while at the same time produce high-quality code. To achieve this, they only perform the most important optimizations so that it's really worth spending time doing them. Code layout optimization is not one of them because without profiling, it may not be beneficial. While a JITter can certainly perform profiling and dynamic optimization, there is a generally preferred way.

How much difference can this make in practice to common code? What about perfectly suited cases?

Code layout optimization by itself can improve overall performance typically by -1% (negative one) to 4%, which is enough to make compiler writers happy. I would like to add that it reduces energy consumption indirectly by reducing cache misses. The reduction in miss ratio of the instruction cache can be typically up to 35%.

Is there anything the developer can do to influence this layout? What about mangling with the forbidden goto?

Yes, there are numerous ways. I would like to mention the generally recommended one which is mpgo.exe. Please do not use goto for this purpose. It's forbidden.

Does the specific JIT being used make much difference to layout?

No.

Does the method inlining heuristic come into play here too?

Inlining can indeed improve code layout with respect to function calls. It's one of the most important optimizations and all .NET JITs perform it.

Moving catch blocks out of line is an easy job, as they're supposed to be the exceptional case by definition. Not sure this happens.

Yes it might be "easy", but what is the potential gained benefit? catch blocks are typically small in size (containing a call to a function that handles the exception). Handling this particular case of code layout does not seem promising. If you really care, use mpgo.exe.

I don't know how the JIT decides the order of generated code. In C on Linux you have likely(cond) and unlikely(cond) which you can use to tell to the compiler which branch is the common path to optimise for.

Using PGO is much more preferable over using likely(cond) and unlikely(cond) for two reasons:

1. The programmer might inadvertently make mistakes while placing likely(cond) and unlikely(cond) in the code. It actually happens a lot. Making big mistakes while trying to manually optimize the code is very typical.
2. Adding likely(cond) and unlikely(cond) all over the code makes it less maintainable in the future. You'll have to make sure that these hints hold every time you change the source code. In large code bases, this could be ( or rather is) a nightmare.

Instruction ordering is distinct from the problem of branch prediction...

Assuming you are talking about code layout, yes they are distinct. But code layout optimization is usually guided by a profile which really includes branch statistics. Hardware branch prediction is of course totally different.

Maybe I'll go and have a read about LLILC.

While using mpgo.exe is the mainstream way of performing this optimization, you can use LLILC also since LLVM support profile-guided optimization as well. But I don't think you need to go this far.