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

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

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

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

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

新闻

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