10 июн. 2009 г.

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.6.0.14 -client


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]

Sun JDK 1.5.0.18 -client


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]

GCJ 4.3.3


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 -client



и самое феноменальное
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]

Blackdown JDK 1.4.2.03 -server


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]

Sun JDK 1.6.0.14 -server


Начиная с 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]

Sun JDK 1.6.0.14 -server


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

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

Комментариев нет: