问题描述
对于Othello（Reversi）的实现，我预先计算了要在数组中查找的2的幂。 如今，在尝试优化速度时，这让我感到为时过早，因为我以前认为查找速度更快，但从未真正成为基准。
这是我如何预先计算两个的幂：
private static final long[] POWERS_OF_TWO = LongStream.range(0L, NUM_SQUARES)
.map(l -> 1L << l)
.toArray();
这就是呼叫站点的外观
final long newSelf = self | cur | POWERS_OF_TWO[i];
现在，替代方法是直接在呼叫站点上计算2的幂：
final long newSelf = self | cur | (1L << i);
哪种方法更快？
1楼
我决定编写一个JMH基准测试我的问题。
基准测试
import org.openjdk.jmh.Main;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Warmup;
import org.openjdk.jmh.runner.RunnerException;
import java.io.IOException;
import java.util.stream.LongStream;
@Warmup(iterations = 3)
@Measurement(iterations = 3)
@Fork(value = 1)
public class LookupVsShift {
private static final int NUM_SQUARES = 64;
private static final long[] POWERS_OF_TWO = LongStream.range(0L, NUM_SQUARES)
.map(l -> 1L << l)
.toArray();
private static final int N = 1_000_000;
@Benchmark
public long testLookupUnroll() {
long sum = 0;
for (int i = 0; i < N; i++) {
sum += (i + POWERS_OF_TWO[58]) & 0x3f;
sum += (i + POWERS_OF_TWO[23]) & 0x3f;
sum += (i + POWERS_OF_TWO[55]) & 0x3f;
sum += (i + POWERS_OF_TWO[56]) & 0x3f;
sum += (i + POWERS_OF_TWO[52]) & 0x3f;
sum += (i + POWERS_OF_TWO[38]) & 0x3f;
sum += (i + POWERS_OF_TWO[49]) & 0x3f;
sum += (i + POWERS_OF_TWO[36]) & 0x3f;
sum += (i + POWERS_OF_TWO[9]) & 0x3f;
sum += (i + POWERS_OF_TWO[7]) & 0x3f;
sum += (i + POWERS_OF_TWO[19]) & 0x3f;
sum += (i + POWERS_OF_TWO[54]) & 0x3f;
sum += (i + POWERS_OF_TWO[37]) & 0x3f;
sum += (i + POWERS_OF_TWO[4]) & 0x3f;
sum += (i + POWERS_OF_TWO[35]) & 0x3f;
sum += (i + POWERS_OF_TWO[8]) & 0x3f;
sum += (i + POWERS_OF_TWO[40]) & 0x3f;
sum += (i + POWERS_OF_TWO[33]) & 0x3f;
sum += (i + POWERS_OF_TWO[43]) & 0x3f;
sum += (i + POWERS_OF_TWO[13]) & 0x3f;
sum += (i + POWERS_OF_TWO[14]) & 0x3f;
sum += (i + POWERS_OF_TWO[3]) & 0x3f;
sum += (i + POWERS_OF_TWO[20]) & 0x3f;
sum += (i + POWERS_OF_TWO[63]) & 0x3f;
sum += (i + POWERS_OF_TWO[29]) & 0x3f;
sum += (i + POWERS_OF_TWO[18]) & 0x3f;
sum += (i + POWERS_OF_TWO[45]) & 0x3f;
sum += (i + POWERS_OF_TWO[22]) & 0x3f;
sum += (i + POWERS_OF_TWO[57]) & 0x3f;
sum += (i + POWERS_OF_TWO[26]) & 0x3f;
sum += (i + POWERS_OF_TWO[24]) & 0x3f;
sum += (i + POWERS_OF_TWO[10]) & 0x3f;
sum += (i + POWERS_OF_TWO[16]) & 0x3f;
sum += (i + POWERS_OF_TWO[15]) & 0x3f;
sum += (i + POWERS_OF_TWO[46]) & 0x3f;
sum += (i + POWERS_OF_TWO[32]) & 0x3f;
sum += (i + POWERS_OF_TWO[17]) & 0x3f;
sum += (i + POWERS_OF_TWO[48]) & 0x3f;
sum += (i + POWERS_OF_TWO[41]) & 0x3f;
sum += (i + POWERS_OF_TWO[39]) & 0x3f;
sum += (i + POWERS_OF_TWO[12]) & 0x3f;
sum += (i + POWERS_OF_TWO[51]) & 0x3f;
sum += (i + POWERS_OF_TWO[21]) & 0x3f;
sum += (i + POWERS_OF_TWO[0]) & 0x3f;
sum += (i + POWERS_OF_TWO[50]) & 0x3f;
sum += (i + POWERS_OF_TWO[44]) & 0x3f;
sum += (i + POWERS_OF_TWO[2]) & 0x3f;
sum += (i + POWERS_OF_TWO[60]) & 0x3f;
sum += (i + POWERS_OF_TWO[34]) & 0x3f;
sum += (i + POWERS_OF_TWO[31]) & 0x3f;
sum += (i + POWERS_OF_TWO[30]) & 0x3f;
sum += (i + POWERS_OF_TWO[53]) & 0x3f;
sum += (i + POWERS_OF_TWO[61]) & 0x3f;
sum += (i + POWERS_OF_TWO[1]) & 0x3f;
sum += (i + POWERS_OF_TWO[27]) & 0x3f;
sum += (i + POWERS_OF_TWO[62]) & 0x3f;
sum += (i + POWERS_OF_TWO[25]) & 0x3f;
sum += (i + POWERS_OF_TWO[28]) & 0x3f;
sum += (i + POWERS_OF_TWO[11]) & 0x3f;
sum += (i + POWERS_OF_TWO[5]) & 0x3f;
sum += (i + POWERS_OF_TWO[6]) & 0x3f;
sum += (i + POWERS_OF_TWO[42]) & 0x3f;
sum += (i + POWERS_OF_TWO[59]) & 0x3f;
sum += (i + POWERS_OF_TWO[47]) & 0x3f;
}
return sum;
}
@Benchmark
public long testShiftUnroll() {
long sum = 0;
for (int i = 0; i < N; i++) {
sum += 1L << (i + 35) & 0x3f;
sum += 1L << (i + 52) & 0x3f;
sum += 1L << (i + 55) & 0x3f;
sum += 1L << (i + 57) & 0x3f;
sum += 1L << (i + 38) & 0x3f;
sum += 1L << (i + 13) & 0x3f;
sum += 1L << (i + 36) & 0x3f;
sum += 1L << (i + 19) & 0x3f;
sum += 1L << (i + 7) & 0x3f;
sum += 1L << (i + 48) & 0x3f;
sum += 1L << (i + 8) & 0x3f;
sum += 1L << (i + 0) & 0x3f;
sum += 1L << (i + 45) & 0x3f;
sum += 1L << (i + 2) & 0x3f;
sum += 1L << (i + 14) & 0x3f;
sum += 1L << (i + 44) & 0x3f;
sum += 1L << (i + 31) & 0x3f;
sum += 1L << (i + 6) & 0x3f;
sum += 1L << (i + 25) & 0x3f;
sum += 1L << (i + 18) & 0x3f;
sum += 1L << (i + 34) & 0x3f;
sum += 1L << (i + 41) & 0x3f;
sum += 1L << (i + 37) & 0x3f;
sum += 1L << (i + 32) & 0x3f;
sum += 1L << (i + 1) & 0x3f;
sum += 1L << (i + 53) & 0x3f;
sum += 1L << (i + 9) & 0x3f;
sum += 1L << (i + 16) & 0x3f;
sum += 1L << (i + 62) & 0x3f;
sum += 1L << (i + 4) & 0x3f;
sum += 1L << (i + 12) & 0x3f;
sum += 1L << (i + 46) & 0x3f;
sum += 1L << (i + 17) & 0x3f;
sum += 1L << (i + 29) & 0x3f;
sum += 1L << (i + 63) & 0x3f;
sum += 1L << (i + 51) & 0x3f;
sum += 1L << (i + 21) & 0x3f;
sum += 1L << (i + 24) & 0x3f;
sum += 1L << (i + 49) & 0x3f;
sum += 1L << (i + 40) & 0x3f;
sum += 1L << (i + 58) & 0x3f;
sum += 1L << (i + 59) & 0x3f;
sum += 1L << (i + 33) & 0x3f;
sum += 1L << (i + 61) & 0x3f;
sum += 1L << (i + 56) & 0x3f;
sum += 1L << (i + 42) & 0x3f;
sum += 1L << (i + 5) & 0x3f;
sum += 1L << (i + 23) & 0x3f;
sum += 1L << (i + 22) & 0x3f;
sum += 1L << (i + 43) & 0x3f;
sum += 1L << (i + 60) & 0x3f;
sum += 1L << (i + 15) & 0x3f;
sum += 1L << (i + 11) & 0x3f;
sum += 1L << (i + 27) & 0x3f;
sum += 1L << (i + 30) & 0x3f;
sum += 1L << (i + 54) & 0x3f;
sum += 1L << (i + 10) & 0x3f;
sum += 1L << (i + 3) & 0x3f;
sum += 1L << (i + 50) & 0x3f;
sum += 1L << (i + 28) & 0x3f;
sum += 1L << (i + 47) & 0x3f;
sum += 1L << (i + 20) & 0x3f;
sum += 1L << (i + 26) & 0x3f;
sum += 1L << (i + 39) & 0x3f;
}
return sum;
}
public static void main(final String[] args) throws IOException, RunnerException {
Main.main(args);
}
}
结果
# Run complete. Total time: 00:02:07
Benchmark Mode Cnt Score Error Units
LookupVsShift.testLookupUnroll thrpt 3 23,072 ± 7,674 ops/s
LookupVsShift.testShiftUnroll thrpt 3 20,834 ± 16,676 ops/s
结果
我觉得现在该基准比较了两者，并且开销不足以使差异可以忽略不计。 现在看来，查找似乎又快了一点。 我认为这仅仅是Danny_ds所说的，很难为如此快速的操作设计准确的基准...
2楼
您将需要比答案中更好的测试。
让我们看一下循环代码：
for (int i = 0; i < N; i++) {
final int idx = i % NUM_SQUARES;
final long value = 1L << idx;
sum += value;
}
对于cpu而言，移位是非常快的操作-它至少应与++或+=一样快。
因此，如果我们看一下代码，就会得到循环计数器（ i++ ）， sum +=和分支（ i < N ）。
%可能需要的cpu??周期是移位的10到20倍。
因此，为了更好地测试和对移位操作进行计时，我将删除%并以随机顺序（对于数组）在循环内部获得2的所有64次幂。
像这样：
for (int i = 0; i < N; i++) {
sum += 1L << 4;
sum += 1L << 7;
sum += 1L << 1;
// and so on
}
对于阵列版本，可以使用：
for (int i = 0; i < N; i++) {
sum += POWER_OF_TWOS[4];
sum += POWER_OF_TWOS[7];
sum += POWER_OF_TWOS[1];
// and so on
}
或使用变量代替常量，并使用位掩码代替％：
for (int i = 0; i < N; i++) {
final int idx = i & 0x3f;
sum += 1L << idx;
}
for (int i = 0; i < N; i++) {
final int idx = i & 0x3f;
sum += POWER_OF_TWOS[idx];
}
或者，如果优化器可能会被这个欺骗：
for (int i = 0; i < N; i++) {
final int idx = 0;
sum += 1L << (idx + 4);
sum += 1L << (idx + 17);
// ...
}
无论如何，移位操作实际上是非常快的操作，应该很容易在具有预先计算的值的数组上使用。