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 = 2ⁿ, где 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]

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]

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.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]