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

Question

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

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，编译器可以执行以下操作：

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

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

我会把它发布到热点开发邮件列表中。

新闻

约翰·罗斯(John Rose)提交了RFE，并且已经有一个"快速而肮脏"的补丁。

Answer 1

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

我的猜想：

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

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

• 循环展开(在所有情况下都是如此);
• 此外，首先对所有展开的步骤从阵列级获取，然后对所有步骤进行xoring 进入累加器。

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

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

@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 所见证的那样，甚至不稳定。

Answer 2

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<table.length; ++i) table[i] = random.nextInt();
}
@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);
result ^= table[i] + j;
}
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);
result ^= i + table[j];
}
return result;
}
@GenerateMicroBenchmark public int maskedIndexUnsafe() {
int result = 0;
final int[] table = this.table;
long x = 0;
for (int i=0; i<=table.length-1; ++i) {
x += i * INT_SCALE;
final long j = x & ((table.length-1) * INT_SCALE);
result ^= i + U.getInt(table, INT_BASE + j);
}
return result;
}
}

结果：

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. 第二个问题是针对热点开发邮件列表，而不是 StackOverflow，恕我直言。

Answer 3

为了安全地消除边界检查，有必要证明

h & (table.length - 1)

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

HotSpot 编译器如何知道这些不良条件是不真实的？它必须比程序员更保守，因为程序员可以更多地了解系统上的高级约束(例如，数组永远不会为空，并且总是作为 2 次幂的元素数量)。