Intrinsics for Math.min and max

[Vitaly Davidovich]

I don't think it's reasonably possible to model hardware branch prediction
in software.  As you say, details are murky, the hardware changes and
advances, etc.

So clearly there will be cases where cmov will yield a speedup over
branches.  The question is whether compiler can ascertain that with very
good precision; otherwise code is penalized and doesn't take advantage of
any advances in branch prediction in hardware.

By removing branches in java I meant rewriting the code/algorithm to not
branch (or branch more predictably); this is akin to what people do in
other languages/domains (e.g. c or c++ on hardware with weak predictors).
Granted level of control in java is limited to some degree, but certainly
avoiding branches or making them more predictable is feasible?

Sent from my phone
On Apr 2, 2014 10:11 AM, "Martin Grajcar" <maaartinus at gmail.com> wrote:

> On Wed, Apr 2, 2014 at 2:55 PM, Vitaly Davidovich <vitalyd at gmail.com>wrote:
>
>> I think hotspot profiling records cumulative probability of a branch
>> taken vs not taken - it doesn't record the pattern, right? This basically
>> means that the best hotspot can do is determine if a jump is very likely
>> taken or not, rather than being able to answer whether something is highly
>> unpredictable.  You can have a branch with 50/50 chance of being taken or
>> not, but the pattern is just as important for hardware branch prediction.
>> For example, a loop runs for 100 iterations with first 50 taking the jump
>> and last 50 not; branch predictor should do fine here even though frequency
>> as recorded by hotspot will simply say 50/50 (correct me if I'm wrong
>> though).
>>
> I'm afraid you're right.
>
>> So it really seems that hotspot can only use profiling to determine very
>> high probability of branches taken, but not able to say much else for other
>> cases because it doesn't model prediction the same way as cpu does (nor
>> should it).
>>
> Maybe  it should, but I'm afraid it's just too complicated and possibly
> not publicly known. I guess hotspot could recognize some simple patterns,
> which are sure to be recognized by the CPU as well.
>
> Maybe considering the condition's origin might be a good
> heuristic: Conditions dependent on array content are probably less
> predictable than those depending let's say on the counter only.
>
>> Given that, seems like code gen should prefer to emit jumps almost all
>> the time.
>>
> I must disagree here. Even a 50% branch can be perfectly predictable, but
> in case it isn't you lose too much. Just extrapolate the slowdown from the
> first image on
> http://stackoverflow.com/questions/19689214/strange-branching-performance to
> 50%. Not using cmov would lead to a slowdown factor 8.
>
>> There's the other aspect to this which is that if hotspot emits jumps and
>> profiling shows high branch misprediction, developer can possibly change
>> their code to either remove branches or make them more predictable.  If
>> cmov is emitted though, then there's nothing dev can do (unless you guys
>> modify intrinsic for math/min to use profile info).
>>
>> Am I missing something in my reasoning?
>>
> I'm afraid there's no good way to remove branches in Java. In general
> you'll get something notably slower than cmov.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/attachments/20140402/e9dd2cc7/attachment-0001.html>