问为什么边界检查没有被消除？

EN

我写了一个简单的benchmark，以便了解在通过按位and计算数组时是否可以消除边界检查。这基本上就是几乎所有哈希表所做的事情:它们计算

h & (table.length - 1)

作为table的索引，其中h是hashCode或派生值。results显示边界检查不会被消除。

我的基准测试的想法非常简单:计算两个值i和j，这两个值都保证是有效的数组索引。

• i是循环计数器。当它被用作数组索引时，边界检查将eliminated.
• j计算为x & (table.length - 1)，其中x是在每次迭代中更改的某个值。当它用作数组索引时，不会消除边界检查。

相关部分如下：

for (int i=0; i<=table.length-1; ++i) {
    x += result;
    final int j = x & (table.length-1);
    result ^= i + table[j];
}

另一个实验使用

    result ^= table[i] + j;

而不是。时间上的差异可能是15% (在我尝试过的不同变种中都是如此)。我的问题：

除了绑定检查elimination?

• Is，还有其他可能的原因吗?我看不出为什么j

没有绑定检查消除的复杂原因

答案摘要

MarkoTopolnik的回答表明，这一切都要复杂得多，消除边界检查并不能保证成功，特别是在他的计算机上，“正常”代码比“屏蔽”代码慢。我猜这是因为它允许一些额外的优化，这在这种情况下实际上是有害的(考虑到当前CPU的复杂性，编译器甚至很难确定)。

列文托夫的回答清楚地表明，数组边界检查是在“掩蔽”中完成的，它的消除使代码的速度与“正常”一样快。

Donal for指出，掩码不适用于长度为零的表，因为x & (0-1)等于x。因此，编译器能做的最好的事情就是用零长度的检查来代替边界检查。但这仍然是值得的，因为零长度检查可以很容易地移出循环。

建议的优化

由于当且仅当a.length == 0时a[x & (a.length - 1)]抛出的等价性，编译器可以执行以下操作：

• 对于每个数组访问，请检查索引是否已通过位and。
• 计算。如果是，请检查其中一个操作数是否计算为长度减一。
• 如果是，请将边界检查替换为零长度检查。
• 让现有优化来处理它。

这样的优化应该是非常简单和廉价的，因为它只查看SSA图中的父节点。与许多复杂的优化不同，它永远不会是有害的，因为它只用稍微简单的检查替换了一次检查；所以没有问题，即使它不能移出循环。

我会把这个贴到hotspot-dev邮件列表上。

新闻

John Rose提交了一份RFE，而且已经有了一个“快速和肮脏”的patch。