为什么边界检查不会被消除？

我写了一个简单的基准测试 ，以便找出当通过按位和数组计算数组时是否可以消除边界检查。 这基本上就是几乎所有哈希表的作用：它们计算 

h & (table.length - 1)

作为table的索引，其中h是hashCode或派生值。 结果表明边界检查不会被消除。

我的基准测试的想法很简单：计算两个值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％（在我尝试的不同变体中非常一致）。 我的问题：

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

答案摘要

MarkoTopolnik的回答表明它更复杂，并且边界检查的消除并不能保证是一场胜利，尤其是在他的计算机上，“普通”代码比“蒙面”慢。 我想这是因为它允许一些额外的优化，在这种情况下显示实际上是有害的（鉴于当前CPU的复杂性，编译器甚至几乎不知道）。

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

Donal Fellows指出这样一个事实，即掩码不适用于零长度表，因为x & (0-1)等于x 。 因此，编译器可以做的最好的事情是用零长度检查替换绑定的检查。 但这是恕我直言仍然值得，因为零长度检查可以很容易地移出循环。

建议优化

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

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

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

我将把它发布到hotspot-dev邮件列表中。

新闻

John Rose提交了一份RFE，并且已经有了“快速而肮脏”的补丁 。

  1. 不，这显然是没有足够的智能边界检查消除的效果。

我已经扩展了Marko Topolnik的基准： 

 @OutputTimeUnit(TimeUnit.NANOSECONDS) @BenchmarkMode(Mode.AverageTime) @OperationsPerInvocation(BCElimination.N) @Warmup(iterations = 5, time = 1) @Measurement(iterations = 10, time = 1) @State(Scope.Thread) @Threads(1) @Fork(2) public class BCElimination { public static final int N = 1024; private static final Unsafe U; private static final long INT_BASE; private static final long INT_SCALE; static { try { Field f = Unsafe.class.getDeclaredField("theUnsafe"); f.setAccessible(true); U = (Unsafe) f.get(null); } catch (Exception e) { throw new IllegalStateException(e); } INT_BASE = U.arrayBaseOffset(int[].class); INT_SCALE = U.arrayIndexScale(int[].class); } private final int[] table = new int[BCElimination.N]; @Setup public void setUp() { final Random random = new Random(); for (int i=0; i

结果： 

 Benchmark Mean Mean error Units BCElimination.maskedIndex 1,235 0,004 ns/op BCElimination.maskedIndexUnsafe 1,092 0,007 ns/op BCElimination.normalIndex 1,071 0,008 ns/op

2.第二个问题是针对hotspot-dev邮件列表而不是StackOverflow，恕我直言。

首先，两个测试之间的主要区别在于边界检查消除; 然而，它影响机器代码的方式远不是天真的期望所暗示的。

我的猜想：

边界检查更强烈地表示为循环退出点，而不是引入开销的附加代码 。

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

  • 循环展开（在所有情况下都是如此）;
  • 另外，对于所有展开的步骤，首先从arrays阶段获取 ，然后对所有步骤进行xoring into accumulator 。

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

考虑对代码的这种轻微修改： 

 @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 osMeasure.maskedIndex avgt 5 1.378 0.229 ns/op osMeasure.normalIndex avgt 5 0.924 0.092 ns/op

如通常预期的那样，“正常指数”变体显着更快。

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

 // if (entry == 0) break;

现在我的结果如下： 

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

“蒙面指数”可预测地响应（降低了开销），但“正常指数”突然变得更糟 。 这显然是由于额外的优化步骤与我的特定CPU模型之间的不合适。

我的观点：

如此详细的性能模型是非常不稳定的，正如我的CPU所见，甚至不稳定。

为了安全地消除该边界检查，有必要certificate这一点 

 h & (table.length - 1)

保证在table生成有效的索引。 如果table.length为零，则不会（因为你最终会得到& -1 ，一个有效的noop）。 如果table.length不是2的幂，那么它也不会有用（你会丢失信息;考虑table.length为17的情况）。

HotSpot编译器如何知道这些不良条件不正确？ 它必须比程序员更保守，因为程序员可以更多地了解系统的高级约束（例如，数组永远不会是空的，并且总是作为一些元素，这是一个强大的function – 二）。

Interesting Posts