What the heck is OSR? It’s HotSpot jargon for On-Stack-Replacement – and it’s used to convert a running function’s interpreter frame into a JIT’d frame – in the middle of that method. It crops up in micro-benchmarks all the friggin’ time, but only rarely in other apps (or at least only rarely in a performance critical way). What happens is this:
- The JVM starts executing some method for the first time ever, in the interpreter, e.g. main().
- That method has a long running loop, that is now being executed in the interpreter
- The interpreter figures out that the method is hot and triggers a normal compilation
- That compilation will be used the NEXT time this method is called, but e.g. it’s main() and there is no next time
- Eventually the interpreter triggers an OSR compilation. The OSR is specialized by some bytecode it will be called at, which is typically the loop back-edge branch.
- Eventually the OSR compilation completes.
- At this point the interpreter jumps to the OSR code when it crosses the specialized entry bytecode – in the middle of the method.
Martin Thompson is asking me questions about writing micro-benchmarks. I’m replaying some of that conversation here (with permission!).
On Fri, Nov 18, 2011 at 11:20 AM, Cliff Click wrote:
Do more & shorter warmup runs. 100K iterations is fine, but loop around the ‘runTest’ 10 times during warmup. Otherwise you risk ending up testing an ‘OSR’ compile instead of a normal one.
On Mon, Nov 21, 2011 at 12:29 PM, Martin Thompson wrote:
Standard Jit’ing and On Stack Replacement are not equal. I have been operating under the assumption that they were. Just to ensure my understanding is correct. The JVM implements a counter for each method that gets incremented when the method returns and also on branch back within a loop. If this counter exceeds 10K on the server VM then it will trigger a compilation of the method. If the method is called again the compiled code is used. If the method was continuing to loop more than the 10K increments then at approximately 14K increments the method will be swapped via OSR. I do not understand why OSR can be a less efficient result but will take your word for it. So I should re-organise the code to avoid OSR and do a number of shorter warm up runs. This is very interesting feedback for main loop design. Can you point me about more detail on how the main loops should be best structured?
OK, Martin, here goes…
A number of shorter warm-up loops will do better, or calling the warm-up loop itself in a loop. Do not nest the warm-up loops in the same function, that defeats the purpose. It probably helps to understand what’s going on in an OSR compile.
In an OSR the code has entered some Java method IN THE INTERPRETER. It’s now spinning in some hot loop IN THE INTERPRETER. The interpreter is busy gathering backedge counts (which will soon hit 14000) and function-entry counts (will only ever be 1).
When the OSR compilation starts, we start parsing bytecodes IN THE MIDDLE OF THE HOT LOOP. For singly-nested loops the effect is to partially peel one loop iteration, then enter the loop proper. To make it clear what the problem(s) are, my examples are written closer to the bytecodes actually experienced by the JVM, as opposed to clean Java. Single-nested-loop example:
<span style="color: blue;">public</span> <span style="color: blue;">static</span> <span style="color: blue;">void</span> main(String args[]) {
S1; i=<span style="color: maroon;">0</span>;
loop:
<span style="color: blue;">if</span>(P) <span style="color: blue;">goto</span> done
S3; A[i++];
<span style="color: blue;">goto</span> loop; <span style="color: green;">// <<--- OSR HERE</span>
done:
S2;
}
Suppose the interpreter has already triggered a normal compile (after 10,000 back-edge branches) and decides that since this loop as run 14,000 back-edges already and we might never exit this function (and thus re-enter it via the normal compilation), and now we need an OSR compilation. This OSR compilation will only be validly entered at the backwards goto bytecode (and also it needs to do some horrible stack-mangling to remove the interpreter’s frame and insert it’s own before entering the main function proper). What program semantics does the OSR compilation have to deal with? The OSR compile “sees” a function that looks like we started executing bytecodes at that backwards goto; this function might look something like this:
<span style="color: blue;">void</span> OSR_main() {
A=value on entry from interpreter;
i=value on entry from interpreter;
<span style="color: blue;">goto</span> loop;
loop:
<span style="color: blue;">if</span>(P) <span style="color: blue;">goto</span> done
S3; A[i++];
<span style="color: blue;">goto</span> loop;
done:
...never reached...
}
This typical optimizes fairly well. Variably ‘i’ is a well-formed array loop index (whose starting value is unknown, but it is a stride-1 increasing value capped at the smaller of ‘A.length’ and ‘!P’). However for a doubly nested loop things get ugly.
<span style="color: blue;">p</span><span style="color: blue;">ublic</span> <span style="color: blue;">static</span> <span style="color: blue;">voi</span><span style="color: blue;">d</span> main(String args[]) {
S0;
loop1:
<span style="color: blue;">if</span>(P1) <span style="color: blue;">goto</span> done1
S1; i=<span style="color: maroon;">0</span>;
loop2:
<span style="color: blue;">if</span>(P2) <span style="color: blue;">goto</span> done2
S3; A[i++];
<span style="color: blue;">goto</span> loop2; <span style="color: green;">// <<--- OSR HERE</span>
done2:
S2;
<span style="color: blue;">goto</span> loop1;
done1:
S4;
}
Here we (again) decide to OSR at the backedge – although there are two backedges to choose from. In practice, the inner one is typically much more frequent than the outer one, so that’s the typical OSR choice. Not that the interpreter can tell; it only tracks backward branches and has no clue about any possible looping structure. In any case, our example OSR compilation starts parsing bytecodes at the ‘goto loop2‘ … leading to this structure:
<span style="color: blue;">void</span> OSR_main() {
A=...value on entry from interpreter...
i=...value on entry from interpreter...
<span style="color: blue;">goto</span> loop2;
loop2:
<span style="color: blue;">if</span>(P2) <span style="color: blue;">goto</span> done2
S3; A[i++];
<span style="color: blue;">goto</span> loop2
done2:
S2;
<span style="color: blue;">goto</span> loop1;
loop1:
<span style="color: blue;">if</span>(P1) <span style="color: blue;">goto</span> done1
S1; i=<span style="color: maroon;">0</span>;
<span style="color: blue;">goto</span> loop2
done1:
...never reached...
}
Blah! What happened? We lost the nested-loop structure! After the optimizer cleans up the control-flow a little we end up with something that looks kinda like this:
<span style="color: blue;">void</span> OSR_main() {
A=...value on entry from interpreter...
i=...value on entry from interpreter...
loop2:
<span style="color: blue;">if</span>(P2) {
S2;
<span style="color: blue;">if</span>(P1) <span style="color: blue;">goto</span> done1
S1; i=<span style="color: maroon;">0</span>;
} <span style="color: blue;">else</span> {
S3; A[i++];
}
<span style="color: blue;">goto</span> loop2
done1:
...never reached...
}
Predicate ‘P2’ probably reports a very low but non-zero frequency (since it’s really the original inner-loop exit test). Since P2 is non-zero, variable i gets reset during the loop. Now variable i is no longer a proper array loop index. There’s no simple affine function describing i, and we no longer can range-check-eliminate A[i++] from the original inner loop. Performance of the OSR version can be as bad as 1/2 that of a normal compilation (although it’s not usually that bad… and 1/2 normal-speed is still 5x interpreted speed!).
Recovering nicely nested loops from here is tough. And what happens above is the GOOD case. There’s another bytecode parsing pattern/technique HS used to use here, and that one leads to having IRREDUCIBLE loops… which pretty much blows all chance of any loop optimizations in any case.
I hope this little chat has given you some idea of what goes on in an OSR compile… and when OSR’s kick in. If you want to test some little function or other in a tight loop… then the Right Thing To Do is to wrap it in a loop in a function in a loop in a function. The outermost loop might OSR, but the inner-most loop(s) will be normal function entries so the inner-loop code-gen will Do The Right Thing.
Cliff