<div dir="ltr">Hi Vladimir,<br><div><br></div><div>below I&#39;m mostly talking to myself... you know learning by writing. It&#39;d be nice if you could find something useful therein.</div><div><br></div><div class="gmail_extra">


On Thu, Feb 13, 2014 at 1:18 AM, Vladimir Kozlov <span dir="ltr">&lt;<a href="mailto:vladimir.kozlov@oracle.com" target="_blank">vladimir.kozlov@oracle.com</a>&gt;</span> wrote:<br>

<div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">Hi Martin,<br>
<br>
The issue is more complicated than I thought. The code I pointed before was added by me about 3 years ago for:<br>
<br>
7097546: Optimize use of CMOVE instructions<br>
<a href="https://bugs.openjdk.java.net/browse/JDK-7097546" target="_blank">https://bugs.openjdk.java.net/<u></u>browse/JDK-7097546</a><br>
<br>
Changes were done to avoid 2x performance hit with cmov for code like next:<br>
<br>
    public static int test(int result, int limit, int mask) { // mask = 15<br>
        for (int i = 0; i &lt; limit; i++) {<br>
          if ((i&amp;mask) == 0) result++; // Non frequent<br>
        }<br>
        return result;<br>
    }<br>
<br>
Cmov instruction has big flow - it requires an additional register.</blockquote><div><br></div><div>I think you could save one register and two instructions. The generated code for the conditional increment seems to use <span style="font-size:13.333333015441895px;line-height:11.333333015441895px;font-family:Arial,FreeSans,Helvetica,sans-serif">BlockLayoutByFrequency and </span>looks like <br>
</div>



<div><br></div><div><div><font face="courier new, monospace">mov    %ebp,%r8d</font></div><div><font face="courier new, monospace">and    %ebx,%r8d</font></div><div><font face="courier new, monospace">test   %r8d,%r8d # not used anymore</font></div>




<div><font face="courier new, monospace">je     0x00007fafdf77d907</font></div><div><br></div></div><div>while simply</div><div><br></div><div><div><font face="courier new, monospace">test   %ebp,%ebx<br>
</font></div><div><font face="courier new, monospace">je     0x00007fafdf77d907</font></div></div><div><br></div><div>should do. I can imagine this doesn&#39;t fit into the intermediate representation used, but maybe it could be handled when mapping into instructions gets done? As this works for AND only, it may be too restrictive for real world examples.</div>




<div><br></div><div>After switching <span style="font-size:13.142857551574707px;font-family:Arial,FreeSans,Helvetica,sans-serif;line-height:11.330357551574707px">BlockLayoutByFrequency off,  t</span>he loop body is essentially this chunk of code repeated 16 times (with <font face="courier new, monospace">old_result</font> and <font face="courier new, monospace">new_result</font> switching between iterations):</div>


<div><br></div><div><div><font face="courier new, monospace">mov    %i, %tmp</font></div><div><font face="courier new, monospace">add    $increment, %tmp</font></div><div><font face="courier new, monospace">and    %mask, %tmp</font></div>


<div><font face="courier new, monospace">mov    %old_result, %new_result</font></div><div><font face="courier new, monospace">inc    %new_result</font></div><div><font face="courier new, monospace">test   %tmp,%tmp</font></div>


<div><font face="courier new, monospace">cmovne %old_result,%new_result</font></div></div><div><br></div><div>Even when looking at the xxx_result only, each chunk seems to need two cycles, because of data dependencies (assuming mov+inc get fused into a single 3-operand microinstruction).</div>
<div><br></div><div style>This dependency could be eliminated, but there are still 7 instructions which is a lot. Now I can see how branching out helps.</div><div style><br></div><div style>By using <font face="courier new, monospace">LEA</font> the instruction count can be reduced to 5, but without any visible speedup in my test.</div>
<div style><br></div><div style>Can <font face="courier new, monospace">add with carry</font> be used? <br></div><div style><br></div><div style><div><font face="courier new, monospace">mov    %i, %tmp</font></div><div><font face="courier new, monospace">add    $increment, %tmp</font></div>
<div><font face="courier new, monospace">and    %mask, %tmp</font></div><div><span style="font-family:&#39;courier new&#39;,monospace">add    $-1, %tmp</span><br></div><div><font face="courier new, monospace">adc    $0,%result</font></div>
</div>

<div><br></div><div style>This works only for counting non-zeros (or zeros after a simple transform or with <font face="courier new, monospace">SBB</font>), but counting is pretty common. In my stupid hand-made assembly there&#39;s a nice speedup (from 0.7 ns/iteration to 0.4).</div>
<div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
If loop&#39;s body is complex, using cmov will result in a register spilling - additional instructions. The performance hit could be high than branch misprediction.<br></blockquote><div><br></div><div style>I guess there&#39;s no way to find it out early enough?</div>
<div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
I am not sure how to proceed from here. I may do some benchmark testing to see affects if cmov is used in more cases.<div></div></blockquote></div><br></div><div class="gmail_extra" style>I can see that <font face="courier new, monospace">CMOV</font> is more expensive than I thought. Maybe after some benchmarking the threshold can be shifted a bit. For my benchmark, it should ideally be no maybe 5%, 10% would be acceptable and 18% are very bad.</div>
<div class="gmail_extra" style><br></div><div class="gmail_extra" style>I guess I know what&#39;s the biggest difference between my and your benchmarks: predictability. In the snippet above, you can happily jump around as it&#39;s nearly free. In mine, you can&#39;t. I updated my benchmark with</div>
<div class="gmail_extra" style><br></div><div class="gmail_extra" style><div class="gmail_extra"><font face="courier new, monospace">double nextDouble = predictable </font></div><div class="gmail_extra"><font face="courier new, monospace">  ? (0.5 + sb.length() % 20) / 20</font></div>
<div class="gmail_extra"><font face="courier new, monospace">  : random.nextDouble();</font></div><div class="gmail_extra"><font face="courier new, monospace">boolean shouldMatch =</font></div><div class="gmail_extra"><font face="courier new, monospace">  nextDouble &lt; fractionMatching;</font></div>
<div><br></div></div><div class="gmail_extra" style>and got these results:</div><div class="gmail_extra" style><a href="https://microbenchmarks.appspot.com/runs/d003427e-5a94-45b9-8a06-fb17d344ec17#r:scenario.benchmarkSpec.parameters.fractionMatching&amp;c:scenario.benchmarkSpec.parameters.predictable">https://microbenchmarks.appspot.com/runs/d003427e-5a94-45b9-8a06-fb17d344ec17#r:scenario.benchmarkSpec.parameters.fractionMatching&amp;c:scenario.benchmarkSpec.parameters.predictable</a><br>
</div><div class="gmail_extra" style><br></div><div class="gmail_extra" style>Does the JVM collect any stats about branch predictability?</div><div class="gmail_extra" style><br></div><div class="gmail_extra" style>Regards,</div>
<div class="gmail_extra" style>Martin.</div><div class="gmail_extra" style><br></div></div>