Java:: Shift vs Multiply

Читая Effective Java 2nd edition обнаружил любопытную заметку:

The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance:
31*i==(i<<5)-i. Modern VMs do this sort of optimization automatically.

Я прекрасно помню, как Владимир Иванович Кучеренко, наш семинарист по мат.моделированию, рассказывал как они делали всевозможные оптимизационные финты типа

10 * x = (x << 3) + (x << 1)

что давало заметный прирост в производительности на существовавшей в 70ые годы аппаратной части.

Небольшой тест:

import java.util.Arrays;

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

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

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

  return System.currentTimeMillis() - t0;
 }

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

  for(int i = 0 ; i < COUNT; i++){
   long j = (i << 5) - i;
   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 double shiftMillis[] = new double[numPasses];
  final double multMillis[] = new double[numPasses];

  for (int i = 0; i < warmUpNumPasses + numPasses; i++) {
   final double shiftMillis0 = getShiftMillis();
   final double multMillis0 = getMultMillis();

   if (shiftMillis0 > 0 && multMillis0 > 0 && i >= warmUpNumPasses) {
    shiftMillis[i - warmUpNumPasses] = shiftMillis0;
    multMillis[i - warmUpNumPasses] = multMillis0;
   }
  }

  Arrays.sort(shiftMillis);
  Arrays.sort(multMillis);

  System.out.println("Shift times (ms): "  + toString(shiftMillis));
  System.out.println("Mult times (ms): "  + toString(multMillis));
 }
}

Sun JDK 1.6.0.14 -client:

java vm name:Java HotSpot(TM) Client VM
java version:1.6
Shift times (ms): [14.0, 14.0, 14.0, 14.0, 14.0, 14.0, 14.0, 15.0, 15.0, 15.0]
Mult times (ms): [14.0, 14.0, 14.0, 14.0, 14.0, 14.0, 15.0, 15.0, 15.0, 15.0]

Sun JDK 1.5.0.18 -client:

java vm name:Java HotSpot(TM) Client VM
java version:1.5
Shift times (ms): [49.0, 50.0, 50.0, 50.0, 50.0, 50.0, 50.0, 50.0, 50.0, 53.0]
Mult times (ms): [56.0, 57.0, 57.0, 57.0, 57.0, 57.0, 57.0, 58.0, 58.0, 58.0]

GCJ 4.3.3:

$ gcj Smth6.java -c -g -O
$ gcj --main=Smth6 -o Smth6 Smth6.o
$ ./Smth6
java vm name:GNU libgcj
java version:1.5
Shift times (ms): [0.001327, 0.001396, 0.001397, 0.001397, 0.001397, 0.001397, 0.001397, 0.001467, 0.001536, 0.001886]
Mult times (ms): [0.001327, 0.001327, 0.001327, 0.001396, 0.001397, 0.001397, 0.001397, 0.001397, 0.001397, 0.002514]

Blackdown JDK 1.4.2.03 -client:

java vm name:Java HotSpot(TM) Client VM
java version:1.4
Shift times (ms): [54.0, 54.0, 54.0, 55.0, 55.0, 55.0, 55.0, 55.0, 57.0, 57.0]
Mult times (ms): [58.0, 58.0, 58.0, 58.0, 58.0, 58.0, 58.0, 58.0, 59.0, 59.0]

и самое феноменальное
Blackdown JDK 1.4.2.03 -server:

java vm name:Java HotSpot(TM) Server VM
java version:1.4
Shift times (ms): [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
Mult times (ms): [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]

Sun JDK 1.6.0.14 -server:

java vm name:Java HotSpot(TM) Server VM
java version:1.6
Shift times (ms): [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
Mult times (ms): [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]

Начиная с Java 6 функция System.nanoTime() корректно работает и в GNU/Linux - адаптировав тестовый класс с использованием данной функции для более тонкого измерения:
Sun JDK 1.6.0.14 -server:

java vm name:Java HotSpot(TM) Server VM
java version:1.6
Shift times (ms): [0.001327, 0.001397, 0.001397, 0.001397, 0.001397, 0.001467, 0.001467, 0.001467, 0.001536, 0.001536]
Mult times (ms): [0.001327, 0.001327, 0.001397, 0.001466, 0.001467, 0.001467, 0.001467, 0.001467, 0.001536, 0.00468]

За исключением некоторых флюктуаций разницы между произведением и сдвигом не наблюдается в java 6+, в то время как разница постоянна для клиентских java 5 (и ниже) - к тому же - сравнивая абсолютные цифры, видно, что операции умножения и сдвига в java 6+ работают почти на порядок быстрее.

P.S. Одтельное спасибо Владиславычу за адаптацию теста и полезное замечание с «прогревом»