Conditional moves vs. branching in unrolled loops

[John Rose]

On Jan 6, 2016, at 6:45 AM, Vitaly Davidovich <vitalyd at gmail.com> wrote:
> 
> Basically, if the cost of branch misprediction is higher than waiting for both inputs to cmov to be available, then cmov is better.  For very predictable branches, cmov is a loss (as we've already established in this thread) and I think always will be (i.e. cpu vendors seem to be putting more and more smarts into branch prediction instead).
> 
> Yes, that was me not understanding the underlying branch profiling mechanisms.
> 
> Actually, that question of mine was more aimed at John who said we should do something special for loops with max/min accumulators :). 

Buried in the bug comments is the following insight:  Branch profiling by the JVM is different from branch profiling by the CPU, and the difference is significant for the specific use case of an accumulated max (or min).

The CPU's profiling has a much shorter time scale:  It collects information (many times) over the course of a single loop.  The JVM's profiling has a long time scale, usually the whole application execution.  If a loop has bursty behavior (high short-span correlation) the CPU can predict branches very well, even though the JVM sees just noise.

(Fun fact:  The JVM could also profile auto-correlation and other statistics, but we have avoided doing this so far.)

So, usually, the branch profiling done in software by the JVM (interpreter or profiled tier) gives enough information to predict what the CPU will experience.  In this very special case (a = max(a, x) for loop-varying x), almost all inputs "settle down" to an almost 100% branch profile, in favor of 'a'.  For random data, you expect to find your max half way through the loop.  That means that the second half of the loop can be speculated as "a = a" instead of "a = max(a, x)".

This, in turn, can be detected in the JIT by pattern-matching locally on the max node, to see if it is of the form phi = max(phi, x).

Fair enough?

— John
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/attachments/20160106/c0272896/attachment.html>