为什么没有取消边界检查？

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)等于0的长度为零的表，屏蔽不起作用x。因此，编译器可以做的最好的事情是用零长度检查替换边界检查。但这仍然值得恕我直言，因为零长度检查可以轻松地移出循环。

拟议的优化

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

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

这种优化应该非常简单且便宜，因为它仅查看SSA图中的父节点。与许多复杂的优化不同，它永远不会有害，因为它只能用稍微简单一些的支票代替它。因此没有问题，即使无法将其移出循环也没有问题。

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

新闻

约翰·罗斯（John
Rose）提出了RFE，并且已经有一个“快速而肮脏的”
补丁。

Answer 1

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。