为什么边界检查无法被消除？

Question

我写了一个简单的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;

相比于“normal”代码，时间上的差异可能为15％（在我尝试的不同变体中相当一致）。我的问题：

• 除了边界检查消除之外，还有其他可能的原因吗？
• 有没有一些我看不到的复杂原因，导致不能消除j的边界检查？

答案摘要

MarkoTopolnik的答案表明，这一切都更加复杂，并且边界检查的消除并不能保证是胜利的，特别是在他的电脑上，“正常”代码比“掩码”慢。我想这是因为它允许一些额外的优化，但实际上在这种情况下是有害的（考虑到当前CPU的复杂性，编译器几乎无法确定）。

leventov的答案清楚地显示数组边界检查在“掩码”中得到执行，并且其消除使代码与“正常”速度一样快。

Donal Fellows指出，对于零长度表，掩码无效，因为x&（0-1）等于x。因此，编译器能做的最好的事情就是将边界检查替换为零长度检查。但是我认为这仍然值得，因为零长度检查可以轻松地移出循环。

优化建议

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

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

这种优化应该非常简单和便宜，因为它只查看SSA图中的父节点。与许多复杂的优化不同，它永远不会有害，因为它只用稍微简单的检查替换一个检查；所以就算无法将其移出循环，也没有问题。

我将此发布到hotspot-dev邮件列表。

新闻

John Rose提交了一个RFE，已经有一个“快速且简单”的patch。

- maaartinus

---

顺便提一下，选项-XX：CompileCommand = print，* Benchmark.time *除了过滤掉您不感兴趣的内容外，还会给出更好的输出（例如，不显示实际寄存器名称的占位符）。 - Marko Topolnik

这个链接倾向于表明，只有当“数组由索引变量的线性函数索引”时，HotSpot才会消除检查。 - ochedru

@MarkoTopolnik：这很奇怪，你能把你的代码发到某个地方吗？关于上面提到的“获取下一个值”的问题：我用x += 1替换了x += i，所以访问是顺序的，除了一个单独的环绕，但没有太多变化。我还尝试消除x并设置j = i & (table.length-1)，它等同于j = i，但似乎防止了边界检查的消除。 - maaartinus

你尝试过使用 x % (table.length-1) 而不是 x & (table.length-1) 吗？也许编译器无法在编译时智能地计算出按位与的边界。 - SnakE

@MarkoTopolnik：是的，一次快10％，一次慢10％，听起来相当无聊。我想我应该先更新我的Java。 - maaartinus

Answer 1

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

我的猜测：

边界检查更像是循环退出点，而不是引入开销的附加代码。

循环退出点阻止了我从生成的机器代码中提取的以下优化：

• 循环展开（在所有情况下都是如此）；
• 此外，从数组中获取阶段首先完成所有展开步骤，然后为所有步骤执行xor到累加器。

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

考虑一下你代码的轻微修改：

@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型号之间的不良匹配所致。

我的观点：

在如此详细的层次上进行性能建模非常不稳定，并且，正如我所见证的那样，甚至具有不确定性。

- Marko Topolnik

---

你认为这个“对于所有展开的步骤，首先完成从数组中获取数据的阶段”是罪魁祸首，对吧？有趣！ - maaartinus

理想情况下，我们应该交流一下。上述技术将BCE效果与额外分层优化效果隔离开来，所以看看它在你那边的表现会很有趣。 - Marko Topolnik

是的，我们应该这样做。这里的评论不太适合这个问题。我认为这可能是一个有趣的问题，你介意发布一下吗？否则，请给我发送电子邮件至<my_name_here>@gmail.com。 - maaartinus

我已将其发布为一个问题：https://dev59.com/Euo6XIcBkEYKwwoYKRDG - Marko Topolnik

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。

- leventov

---

很奇怪，我没有想到使用“Unsafe”来检查我的猜想！ - maaartinus

@MarkoTopolnik：没错，但是你可以使用U.getInt(table, INT_BASE + j * INT_SCALE)使其更加相似，并且这可以很容易地转换为完全相同的代码。我还没有检查它是否实际上这样做了。 - maaartinus

@maaartinus U.getInt(table, INT_BASE + j * INT_SCALE) 的速度较慢，可能是因为JIT将数组索引编译成单个计算地址和内存操作命令，其中比例应该是非常小的立即数（汇编命令代码中最多3位），但当您写* INT_SCALE时，它不知道INT_SCALE比8小，并将此结构编译为几个命令：mul，然后是偏移和内存操作。要小心。虽然我很懒，但我也没有尝试过* 4L或查看汇编。 - leventov

@leventov 你的写法最终也变成了一个mul。 - Marko Topolnik

@maaartinus Marko是正确的，我的上一条评论因不雅语言而被删除。我的假设是，在掩码之前进行乘法运算可以让CPU在算术流水线上安排指令更灵活。 - leventov

Answer 3

为了安全地消除该边界检查，必须证明：

h & (table.length - 1)

保证产生有效的索引到table。如果table.length为零，则不会产生（因为您最终会得到& -1，即实际上不执行任何操作）。如果table.length不是2的幂，则也无法有用地执行它（您将丢失信息；考虑table.length为17的情况）。

HotSpot编译器如何知道这些不良条件不成立？它必须比程序员更保守，因为程序员可以了解系统的高级约束（例如，数组永远不为空，并且始终具有2的幂次元素数）。

- Donal Fellows

---

我不理解你关于2的幂次方的评论。如果h和k是非负整数，则h＆k是一个非负整数，最多为h且最多为k。 - ruakh

@ruakh 这在技术上并不是一种安全条件，但它可能会产生可怕的分布结果。考虑有17个桶的情况；你最终会使所有东西都进入桶0或(很少)16。唯一一个h&(ary.length-1)适用的情况是当数组的大小是2的幂（>=1），且编译器无法轻松地证明这一点。 - Donal Fellows

我不明白。如果它“从技术上讲不是一个安全条件”，而编译器的目标仅仅是“安全地消除边界检查”，那么它对编译器有何意义呢？为什么编译器需要能够证明它呢？ - ruakh

@ruakh：同意，编译器不应该关心这个。它可以通过table.length > 0检查来替换边界检查，并让程序员担心分布问题。 - maaartinus