我写了一个简单的基准测试,以找出在通过按位和计算数组时是否可以消除边界检查。基本上,这就是几乎所有哈希表的作用:它们计算
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的答案清楚地表明,数组边界检查是在“ masked”中完成的,并且消除它使代码与“ normal”一样快。
Donal Fellows指出以下事实:对于x & (0-1)
等于0的长度为零的表,屏蔽不起作用x
。因此,编译器可以做的最好的事情就是用零长度检查替换边界检查。但这仍然值得恕我直言,因为零长度检查可以轻松地移出循环。
由于a[x & (a.length - 1)]
当且仅当时等价抛出a.length == 0
,编译器可以执行以下操作:
这种优化应该非常简单且便宜,因为它仅查看SSA图中的父节点。与许多复杂的优化不同,它永远不会有害,因为它只会用稍微简单一些的支票代替它。因此没有问题,即使无法将其移出循环也没有问题。
我将其发布到hotspot-dev邮件列表。
我已经扩展了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.第二个问题是热点开发邮件列表,而不是IMHO的StackOverflow。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句