我写了一个简单的benchmark为了找出当通过按位与计算数组时是否可以消除边界检查。这基本上是几乎所有哈希表所做的:它们计算

h & (table.length - 1)

作为 table 的索引，其中 h 是 hashCode 或派生值。 results表明边界检查没有被消除。

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

• i 是循环计数器。当它被用作数组索引时，边界检查就被消除了。
• 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%(在我尝试过的不同变体中非常一致)。我的问题:

• 除了绑定(bind)检查消除之外，还有其他可能的原因吗？
• 是否有一些复杂的原因我无法理解为什么 j 没有绑定(bind)检查消除？

答案总结

MarkoTopolnik 的回答表明这一切都更加复杂，并且不能保证消除边界检查一定会成功，尤其是在他的计算机上，“正常”代码比“屏蔽”代码要慢。我猜这是因为它允许进行一些额外的优化，这在这种情况下实际上是有害的(鉴于当前 CPU 的复杂性，编译器甚至几乎无法确定)。

leventov 的回答清楚地表明，数组边界检查是在“屏蔽”中完成的，并且它的消除使代码与“正常”一样快。

Donal Fellows 指出，掩码不适用于零长度表，因为 x & (0-1) 等于 x。所以编译器能做的最好的事情就是用零长度检查代替边界检查。但恕我直言，这仍然值得，因为零长度检查可以轻松移出循环。

建议优化

由于等价的 a[x & (a.length - 1)] 当且仅当 a.length == 0 时抛出，编译器可以这样做以下:

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

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

我会将其发布到热点开发邮件列表。

新闻

John Rose 提交了 RFE并且已经有一个“又快又脏”的 patch .

最佳答案

首先，您的两个测试之间的主要区别肯定是边界检查消除；然而，这对机器代码的影响远非天真的期望所暗示的那样。

我的猜想:

边界检查作为循环退出点比作为引入开销的附加代码更强烈。

循环退出点阻止了我从发出的机器代码中剔除的以下优化:

• 循环展开(在所有情况下都是如此)；
• 此外，从数组中提取阶段首先对所有展开的步骤进行，然后异或到累加器对所有步骤进行。

如果循环可以在任何步骤中断，则此暂存将导致执行的工作循环步骤从未实际执行过。

考虑一下您的代码的这种轻微修改:

@OutputTimeUnit(TimeUnit.NANOSECONDS)
@BenchmarkMode(Mode.AverageTime)
@OperationsPerInvocation(Measure.N)
@Warmup(iterations = 3, time = 1)
@Measurement(iterations = 5, time = 1)
@State(Scope.Thread)
@Threads(1)
@Fork(1)
 public class Measure {
  public static final int N = 1024;

  private final int[] table = new int[N];
  @Setup public void setUp() {
    final Random random = new Random();
    for (int i = 0; i < table.length; ++i) {
      final int x = random.nextInt();
      table[i] = x == 0? 1 : x;
    }
  }
  @GenerateMicroBenchmark public int normalIndex() {
    int result = 0;
    final int[] table = this.table;
    int x = 0;
    for (int i = 0; i <= table.length - 1; ++i) {
      x += i;
      final int j = x & (table.length - 1);
      final int entry = table[i];
      result ^= entry + j;
      if (entry == 0) break;
    }
    return result;
  }
  @GenerateMicroBenchmark public int maskedIndex() {
    int result = 0;
    final int[] table = this.table;
    int x = 0;
    for (int i = 0; i <= table.length - 1; ++i) {
      x += i;
      final int j = x & (table.length - 1);
      final int entry = table[j];
      result ^= i + entry;
      if (entry == 0) break;
    }
    return result;
  }
}

只有一个区别:我添加了支票

if (entry == 0) break;

为循环提供一种在任何步骤中提前退出的方法。 (我还引入了一个守卫来确保没有数组条目实际上是 0。)

在我的机器上，结果如下:

Benchmark                   Mode   Samples         Mean   Mean error    Units
o.s.Measure.maskedIndex     avgt         5        1.378        0.229    ns/op
o.s.Measure.normalIndex     avgt         5        0.924        0.092    ns/op

“正常索引”变体比通常预期的要快得多。

但是，让我们删除额外的检查:

// if (entry == 0) break;

现在我的结果是:

Benchmark                   Mode   Samples         Mean   Mean error    Units
o.s.Measure.maskedIndex     avgt         5        1.130        0.065    ns/op
o.s.Measure.normalIndex     avgt         5        1.229        0.053    ns/op

“屏蔽索引”的响应可预测(减少开销)，但“正常索引”突然更糟。这显然是由于额外的优化步骤与我的特定 CPU 模型之间的不匹配造成的。

我的观点:

如此详细的性能模型非常不稳定，正如我在 CPU 上看到的那样，甚至不稳定。

关于java - 为什么边界检查没有被消除？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21702939/