14 июн. 2009 г.

Java: Mod vs Bit mask

Идея провести сравнение производительности mod с битовой маской натолкнули два обстоятельства
  • использование данного оптимизационного финта в java.util.HashMap
  • пример из Java Puzzlers, Puzzle #1, в котором вместо некорректной реализации метода по определению нечётности числа
public static boolean isOdd(int i) {
return i % 2 == 1;
}
предлагалось использовать этот:
public static boolean isOdd(int i) {
return i % 2 != 0;
}

Несложно показать, что
i mod k = i & (k - 1), при k = 2n, где i, n ∈ N

Измерять мы будем схожим способом с тем, как измеряли производительность Операции битового сдвига с произведением:
import java.util.Arrays;

public final class Smth {
private static final int COUNT = 1 << 24;

private static int factor;
private static int factor2;

private static long getModMillis() {
final long t0 = System.currentTimeMillis();

for(int i = 0 ; i < COUNT; i++){
long j = i % factor;
if (j > 0){
// nothing, just for jit
}
}

return System.currentTimeMillis() - t0;
}

private static long getBitMaskMillis() {
final long t0 = System.currentTimeMillis();

for(int i = 0 ; i < COUNT; i++){
long j = i & factor2;
if (j > 0){
// nothing, just for jit
}
}

return System.currentTimeMillis() - t0;
}

public static String toString(final double[] d){
final StringBuffer builder = new StringBuffer("[");
for(int i = 0; i < d.length; i++){
if (i > 0)
builder.append(", ");
builder.append(d[i]);
}
builder.append("]");
return builder.toString();
}

public static final void main(String[] args) {
System.out.println("java vm name:" + System.getProperty("java.vm.name"));
System.out.println("java version:" + System.getProperty("java.specification.version"));
final int warmUpNumPasses = 10;
final int numPasses = 10;
final int steps = 10;

final double bitMaskMillis[] = new double[steps];
final double modMillis[] = new double[steps];

for(int k = 0; k < steps; k++){
factor = 1 << (k + 1);
factor2 = factor - 1;
for (int i = 0; i < warmUpNumPasses + numPasses; i++) {
final double bitMaskMillis0 = getBitMaskMillis();
final double modMillis0 = getModMillis();

if (bitMaskMillis0 > 0 && modMillis0 > 0 && i >= warmUpNumPasses) {
bitMaskMillis[k] += bitMaskMillis0;
modMillis[k] += modMillis0;
}
}
bitMaskMillis[k] /= numPasses;
modMillis[k] /= numPasses;
}

Arrays.sort(bitMaskMillis);
Arrays.sort(modMillis);

System.out.println("Bit mask times (ms): " + toString(bitMaskMillis));
System.out.println("Mod times (ms): " + toString(modMillis));
}
}

Sun JDK 1.6.0.14 -client:
java vm name:Java HotSpot(TM) Client VM
java version:1.6
Bit mask times (ms): [18.3, 18.3, 18.3, 18.4, 18.5, 18.6, 18.6, 18.8, 22.3, 26.0]
Mod times (ms): [186.4, 186.4, 190.3, 264.1, 264.1, 264.2, 264.2, 267.8, 269.2, 274.7]

Sun JDK 1.6.0.14 -client


Blackdown JDK 1.4.2.03 -client:
java vm name:Java HotSpot(TM) Client VM
java version:1.4
Bit mask times (ms): [42.2, 42.4, 42.4, 42.5, 42.6, 42.6, 42.7, 43.2, 43.8, 45.5]
Mod times (ms): [184.2, 187.9, 193.2, 258.0, 258.1, 258.2, 258.2, 258.3, 261.8, 266.1]

Blackdown JDK 1.4.2.03 -client


Sun JDK 1.5.0.18 -client:
java vm name:Java HotSpot(TM) Client VM
java version:1.5
Bit mask times (ms): [45.0, 45.2, 45.3, 45.4, 45.4, 45.7, 46.0, 46.0, 46.1, 90.8]
Mod times (ms): [184.0, 184.1, 186.5, 263.1, 263.9, 263.9, 264.0, 265.0, 265.9, 266.3]

Sun JDK 1.5.0.18 -client


и адаптированный тест в серверном варианте с измерением в наносекундах:
Sun JDK 1.6.0.14 -server:
java vm name:Java HotSpot(TM) Server VM
java version:1.6
Bit mask times (ms): [0.001348, 0.001383, 0.00139, 0.00139, 0.00139, 0.001397, 0.001397, 0.001404, 0.001411, 0.001439]
Mod times (ms): [0.001334, 0.001348, 0.001355, 0.001355, 0.001362, 0.001362, 0.001369, 0.001383, 0.001383, 0.001488]

Sun JDK 1.6.0.14 -server

1 комментарий:

Alexander N. Neuron комментирует...

я то думал, что sopln ушли в прошлое =)