Saturday, June 19, 2010

Что день грядущий нам готовит или новые вкусности JDK7

Релиз JDK7 уже совсем близко и настало время поковыряться да посмотреть, что же нового он нам несет. Начнем с долгожданного и интересного пакета по имени java.dyn.
Классы в этом пакете служат для реализации JSR 292 (invokedynamic support). Та самая поддержка динамического вызова методов в Java которая должна существенно улучшить производительность новых языков программирования работающих поверх JVM (Scala, Jruby итд)
Многие элементы JSR 292 доступны и для Java программистов. Взять, к примеру, классы MethodHandle и MethodType.
MethodHandle позволяет нам получить ссылку на метод и вызвать его. В принципе, и раньше мы могли сделать тоже самое с помощью Reflection API. Утверждается, однако, что MethodHandle, работает быстрее поскольку поддерживается на уровне инструкций JVM.
Перейдем сразу к коду:

  
import java.dyn.MethodType;
import java.dyn.MethodHandle;
import java.dyn.MethodHandles;
import java.io.PrintStream;
….
MethodType type = MethodType.methodType(Void.TYPE, String.class);
MethodHandle handle = MethodHandles.lookup().findVirtual(PrintStream.class, "println", type);
handle.<void>invoke(System.out, "Hello!");

Что здесь происходит? Сначала мы создаем тип метода, который собираемся вызвать. Потом получаем ссылку handle на сам метод, в нашем случае это метод println(String s) класса PrintStream. И, наконец, вызываем этот метод, передавая в качестве первого параметра объект у которого будет вызван метод.
Особенно интересно то, что если заглянуть в класс MethodHandle то никакого метода invoke там нет. Вот оно, волшебство invokedynamic.
Спускаясь на землю, то есть на жесткий диск и процессор реального компьютера, нам придется немного попрыгать с бубном, чтобы запустить этот код. Для начала, нужно будет jvm дополнительные параметры. Ведь несмотря на то, что invokedynamic официально включен в jdk7, эта функциональность до сих пор считается экспериментальной.
Итак, запускаем
  
javac ./MethodHandleTest.java
java -XX:+UnlockExperimentalVMOptions -XX:+EnableMethodHandles -XX:+EnableInvokeDynamic MethodHandle

Получаем ошибку внутри JVM.
  
Invalid layout of java.dyn.CallSite at target
# A fatal error has been detected by the Java Runtime Environment …

Если вы, как и я, видите эту ошибку, значит разработчики все еще не озаботились исправлением несовместимости версий JVM и классов JDK. Поэтому нам самим придется скачать и добавить в bootclasspath jar-ник Качаем отсюда http://blogs.sun.com/jrose/resource/jsr292/hs19-b01-jsr292-patch.jar Кладем куда угодно на диске, и запускаем:
  
java -XX:+UnlockExperimentalVMOptions -XX:+EnableMethodHandles -XX:+EnableInvokeDynamic
-Xbootclasspath/p:<Путь к скачанному файлу>hs19-b01-jsr292-patch.jar MethodHandle

Hello!


Ура! Теперь всё работает.
В чем же разница? Мы и раньше могли сделать точно так же используя Reflection API:
  
import java.lang.reflect.Method;
import java.io.PrintStream;
...
Method handle = PrintStream.class.getDeclaredMethod("println", new Class[]{String.class});
handle.invoke(System.out, "Hello Reflection!");

Я решил проверить, а так ли в действительности хороша производительность, как нам обещали:
  
import java.dyn.MethodType;
import java.dyn.MethodHandle;
import java.dyn.MethodHandles;
import java.lang.reflect.Method;
import java.lang.reflect.InvocationTargetException;

public class PerformanceTest {
public static final int CNT = 100000;

public static void main(String[] args) throws InvocationTargetException, NoSuchMethodException, IllegalAccessException {
long t0 = System.currentTimeMillis();
reflectionAPITest();
System.out.println("Reflection API " + (System.currentTimeMillis()-t0));
t0 = System.currentTimeMillis();
methodHandlerTest();
System.out.println("Method handler " + (System.currentTimeMillis()-t0));

}

private static void reflectionAPITest() throws NoSuchMethodException, InvocationTargetException, IllegalAccessException {
PerformanceTest target = new PerformanceTest();
for(int i=0; i<CNT; i++){
Method handle = PerformanceTest.class.getDeclaredMethod("increment", new Class[]{int.class});
handle.invoke(target, i);
}
}

private static void methodHandlerTest() {
PerformanceTest target = new PerformanceTest();
for(int i=0; i<CNT; i++){
MethodType type = MethodType.methodType(Integer.TYPE, Integer.TYPE);
MethodHandle handle = MethodHandles.lookup().findVirtual(PerformanceTest.class, "increment", type);
handle.<int>invoke(target, i);
}
}

public int increment(int i){
return i+1;
}
}

Хмм, все оказывается далеко не так гладко:
Reflection API 388
Method handler 821
Получается, что старый, добрый Reflection API почти вдвое быстрее чем новый MethodHandler.
К счастью, ситуация меняется радикально хэндл используется повторно. Так же, для сравнения, я добавил прямой вызов метода:
  
import java.dyn.MethodType;
import java.dyn.MethodHandle;
import java.dyn.MethodHandles;
import java.lang.reflect.Method;
import java.lang.reflect.InvocationTargetException;

public class PerformanceTest {
public static final int CNT = 10000000;

public static void main(String[] args) throws InvocationTargetException, NoSuchMethodException, IllegalAccessException {
long t0 = System.currentTimeMillis();
reflectionAPITest();
System.out.println("Reflection API " + (System.currentTimeMillis()-t0));
t0 = System.currentTimeMillis();
methodHandlerTest();
System.out.println("Method handler " + (System.currentTimeMillis()-t0));
t0 = System.currentTimeMillis();
directCall();
System.out.println("Direct call " + (System.currentTimeMillis()-t0));

}

private static void directCall() {
PerformanceTest target = new PerformanceTest();
for(int i=0; i<CNT; i++){
target.increment(i);
}
}

private static void reflectionAPITest() throws NoSuchMethodException, InvocationTargetException, IllegalAccessException {
PerformanceTest target = new PerformanceTest();
Method handle = PerformanceTest.class.getDeclaredMethod("increment", new Class[]{int.class});
for(int i=0; i<CNT; i++){
handle.invoke(target, i);
}
}

private static void methodHandlerTest() {
PerformanceTest target = new PerformanceTest();
MethodType type = MethodType.methodType(Integer.TYPE, Integer.TYPE);
MethodHandle handle = MethodHandles.lookup().findVirtual(PerformanceTest.class, "increment", type);
for(int i=0; i<CNT; i++){
handle.<int>invoke(target, i);
}
}

public int increment(int i){
return i+1;
}
}

Пришлось увеличить количество итераций, и результат впечатляет:
Reflection API 1793
Method handler 347
Direct call 20
Теперь MethodHandle работает во много раз быстрее. И пускай на порядок медленней чем непосредственный вызов, все же это лучше чем вызов через Reflection API.
Что же, не будем торопиться заменять все reflection-вызовы на MethodHandler. В некоторых случаях, однако, это может оказаться очень полезным.

Спасибо за внимание, особенно тем, кто дочитал до конца. В своей следующей заметке о JDK7 я расскажу о самом странном классе InvokeDynamic. Всем хорошего дня!

Tuesday, June 1, 2010

Динамическое программирование на Хаскеле, часть 2

Этот пост является продолжением моего предыдущего поста про использование Haskell в динамическом программировании.
Давайте немного усложним задачу. Пусть теперь нам требуется не просто вернуть минимальное количество монет, которое требуется чтобы разменять заданную сумму, а нужно вернуть список монет.
Как это реализуется с точки зрения DP? В предыдущем решении для каждой суммы мы сохраняли оптимальное значение. Теперь нам нужно дополнительно хранить список монет, приведших к данному значению. Решение в лоб: связать с каждым элементом массива список в котором будет хранится полный перечень используемых монет. Этот подход не очень рационален с точки зрения используемой памяти. Куда лучше хранить лишь дельту. То есть, для каждой суммы мы храним значение последней добавленной монеты. Тогда, после того как решение найдено, мы можем пройти по этим дельтам в обратную сторону и собрать все монеты которые были использованы. Итак, переходим от слов к делу.
Решение на императивном языке Java будет выглядеть следующим образом:
  
public int[] change(int[] coins, int s) {
int[] dp = new int[s + 1];
int[] backtrack = new int[s + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for ( int i = 1; i <= s; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i && dp[i - coins[j]] + 1 < dp[i]) {
dp[i] = dp[i - coins[j]] + 1;
backtrack[i] = i - coins[j];
}

}
}
int[] res = new int[dp[s]];
int i = s;
int n = 0;
while(i!=0){
res[n++] = i-backtrack[i];
i = backtrack[i];
}
return res;
}


Как написать аналогичное решение на Haskell? Достаточно просто. Для этого на помощь нам приходят кортежи (они же туплы). Очень удобная структура данных имеющаяся в любом функциональном языке программирования.
По сути, кортеж, это просто набор элементов. Элементы могут быть одного а могут быть разных типов. Объявляются кортежи в Haskell очень просто:

  
let a = (1, 2)


a – это кортеж из двух элементов 1 и 2.
Чтобы достать элемент из кортежа, мы можем использовать функции fst, snd или pattern matching.
Теперь собственно решение. Идея та же, что и в императивном подходе. Только теперь мы не заводим дополнительный массив, а прямо в исходном массиве храним кортежи со связкой: оптимальное значение – величина последней монеты.
  
import Array
import Data.List


minl :: [(Int, Int)] -> (Int, Int)
minl [] = (0, 0)
minl xs = minimumBy (\x y -> compare (fst x) (fst y)) xs

changeValues :: [Int] -> Int -> [Int]
changeValues xs n = extract dp n
where
dp = listArray (0,n) [ cell i | i<-[0..n]]
cell 0 = (0, 0)
cell i = minl [(succ$fst (dp!(i-x)), x) | x<-xs, i>=x]
extract dp 0 = []
extract dp n = (snd (dp!n)):(extract dp (n-(snd (dp!n))))


Пришлось добавить функцию extract которая достает из массива dp величины монет (т.е., вторые элементы) и складывает их в результирующий список.