title: Why the bounds check doesn't get eliminated?
body: <p>I wrote a simple <a href="https://dl.dropboxusercontent.com/u/4971686/published/maaartin/so/BoundsCheckBenchmark.java" rel="noreferrer">benchmark</a> in order to find out if bounds check can be eliminated when the array gets computed via bitwise and. This is basically what nearly all hash tables do: They compute</p>
  <pre><code>h &amp; (table.length - 1)
  </code></pre>
  <p>as an index into the <code>table</code>, where <code>h</code> is the <code>hashCode</code> or a derived value. The <a href="https://microbenchmarks.appspot.com/runs/ad9f2e21-e457-4516-a2c5-769413eee4ef" rel="noreferrer">results</a> shows that the bounds check don't get eliminated.</p>
  <p>The idea of my benchmark is pretty simple: Compute two values <code>i</code> and <code>j</code>, where both are guaranteed to be valid array indexes.</p>
  <ul>
  <li><code>i</code> is the loop counter. When it gets used as array index, the bounds check gets eliminated.</li>
  <li><code>j</code> gets computed as <code>x &amp; (table.length - 1)</code>, where <code>x</code> is some value changing on each iteration. When it gets used as array index, the bounds check does not get eliminated.</li>
  </ul>
  <p>The relevant part is as follows:</p>
  <pre><code>for (int i=0; i&lt;=table.length-1; ++i) {
      x += result;
      final int j = x &amp; (table.length-1);
      result ^= i + table[j];
  }
  </code></pre>
  <p>The other experiment uses</p>
  <pre><code>    result ^= table[i] + j;
  </code></pre>
  <p>instead. The difference in timing is maybe 15% (pretty consistently across different variants I've tried). My questions:</p>
  <ul>
  <li>Are there other possible reasons for this besides bound check elimination?</li>
  <li>Is there some complicated reason I can't see why there's no bound check elimination for <code>j</code>?</li>
  </ul>
  <h1>A summary of the answers</h1>
  <p>MarkoTopolnik's answer shows that it's all more complicated and the elimination of the bounds checks is not guaranteed to be a win, especially on his computer the &quot;normal&quot; code is slower than &quot;masked&quot;. I guess this is because of it allowing some additional optimization which shows to be actually detrimental in this case (given the complexity of the current CPUs, the compiler hardly even knows for sure).</p>
  <p>leventov's answer shows clearly that the array bounds check gets done in &quot;masked&quot; and that it's elimination makes the code as fast as &quot;normal&quot;.</p>
  <p>Donal Fellows points to the fact, that the masking doesn't work for a zero-length table, as <code>x &amp; (0-1)</code> equals to <code>x</code>. So the best thing the compiler can do is to replace the bound check by a zero-length check. But this is IMHO still worth it, as the zero-length check can be moved out of the loop easily.</p>
  <h2>Proposed optimization</h2>
  <p>Because of the the equivalence <code>a[x &amp; (a.length - 1)]</code> throws if and only if <code>a.length == 0</code>, the compiler can do the following:</p>
  <ul>
  <li>For each array access, check if the index has been computed via a bitwise and.</li>
  <li>If so, check if either of the operands was computed as length minus one.</li>
  <li>If so, replace the bounds check by a zero-length check.</li>
  <li>Let the existing optimizations take care of it.</li>
  </ul>
  <p>Such an optimization should be pretty simple and cheap as it only looks at the parent nodes in the <a href="http://en.wikipedia.org/wiki/Static_single_assignment_form" rel="noreferrer">SSA</a> graph. Unlike many complex optimizations, it can never be detrimental, as it only replaces one check by a slightly simpler one; so there's no problem, not even if it can't be moved out of the loop.</p>
  <p>I'll post this to the hotspot-dev mailing lists.</p>
  <h1>News</h1>
  <p>John Rose filed an <a href="https://bugs.openjdk.java.net/browse/JDK-8003585" rel="noreferrer">RFE</a> and there's already a &quot;quick-and-dirty&quot; <a href="https://gist.github.com/rednaxelafx/8964030" rel="noreferrer">patch</a>.</p>