Пост из серии «будни перформанс-инженеров». Иногда в проектах возникает необходимость сделать т.н. multiple dispatch: возможность вызвать конкретный метод, основываясь на типах аргументов.
Например, есть два метода:
class Caller {
public void doSomethingNasty(A aInstance) { ... };
public void doSomethingNasty(B aInstance) { ... }
}Когда точный тип аргумента известен во время компиляции, проблем никаких нет: это обычная перегрузка методов и компилятор может точно выбрать, какой из методов звать. Но что если этот тип становится известным только во время исполнения?
class A extends Base { ... }
class B extends Base { ... }
class Caller {
public void pleaseDoThat(Base instance) {
doSomethingNasty(instance); // compile error
}
}
В Java подобный код вызовет ошибку компиляции, ибо нефиг. Что делать, если всё-таки надо? Значит, нужно в рантайме определить нужный метод.
Для этого есть три базовых варианта:
- Double dispatch
class Base {
abstract void dispatch(Caller caller);
}
class A {
void dispatch(Caller caller) {
caller.dispatch(this); // this.getClass() is definitely A.class
}
}
class B {
void dispatch(Caller caller) {
caller.dispatch(this); // this.getClass() is definitely B.class
}
}
class Caller {
public void pleaseDoThat(Base instance) {
instance.dispatch(this);
}
public void dispatch(A aInstance) {
doSomethingNasty(aInstance);
}
public void dispatch(B bInstance) {
doSomethingNasty(bInstance);
}
public void doSomethingNasty(A aInstance) { ... };
public void doSomethingNasty(B aInstance) { ... };
}
- Цепочка instanceof'ов.
class Caller {
public void pleaseDoThat(Base instance) {
if (instance instanceof A) {
doSomethingNasty((A)instance);
} else
if (instance instanceof B) {
doSomethingNasty((B)instance);
}
}
public void doSomethingNasty(A aInstance) { ... };
public void doSomethingNasty(B aInstance) { ... };
}
- Reflection
class Caller {
private Map<String, Method> methods;
public void setup() {
methods.put("A", Caller.class.getMethod("doSomethingNasty", A.class));
methods.put("B", Caller.class.getMethod("doSomethingNasty", B.class));
}
public void pleaseDoThat(Base instance) {
Method m = map.get(instance.getClass().getName());
m.invoke(this, instance);
}
public void doSomethingNasty(A aInstance) { ... };
public void doSomethingNasty(B aInstance) { ... }l
}
Есть другие вариации на эту тему, включая:
- Тащить за собой Enum'ы.
enum ExactType { A, B };
class Base {
ExactType getType();
}
class A extends Base {
ExactType getType() {
return ExactType.A;
}
}
class B extends Base {
ExactType getType() {
return ExactType.B;
}
}
class Caller {
public void pleaseDoThat(Base instance) {
switch(instance.getType()) {
case A: doSomethingNasty((A)instance); break;
case B: doSomethingNasty((B)instance); break;
}
}
public void doSomethingNasty(A aInstance) { ... };
public void doSomethingNasty(B aInstance) { ... }
} - Цепочка instanceof'ов, но без else (довольно странная идея, но такое я тоже видел)
- Reflection через JSR292/MethodHandle.
Все эти методы обладают своими плюсами и минусами.
Возможные проблемы:
- Появился новый класс в иерархии, например, C extends Base. Определили Caller.doSomethingNasty(C cInstance).
- double dispatch скомпилировался и отработал нормально
- instanceof скомпилировался, но проигнорировал все вызовы с C, надо бежать по коду и исправлять везде
- enum потребовал новой константы в enum, но опять надо бежать по коду и исправлять switch'и
- reflection скомпилировался, проигнорировал С, надо бежать и везде в Map'ы засовывать новый метод
- Сложные иерархии. Допустим, A extends B, B extends Base
- double dispatch отработал нормально
- instanceof для bInstance типа B получил (bInstance instanceof A) == true и вызвал не свой метод
- enum отработал нормально
- reflection отработал нормально
На основании этого мне кажется, что наиболее безопасным способом является double dispatch. Называйте меня ООП-пуристом, если хотите.
Однако всё это лирика, меня интересуют вопросы производительности. Поэтому настала пора взять и измерить, что на этой нашей Sun JDK быстрее. Меня интересует не столько, какой из этих способов быстрее, а то, как HotSpot себя ведёт на этих вариантах. В реальных проектах выигрыш производительности сильно зависит от приложения, и там первую скрипку играют скорее доводы о безопасной поддержке кода, а не каждой последней капле перформанса.
Отдельной строкой повторю: эти результаты не являются поводом переписывать существующий код из соображений производительности, но на них интересно посмотреть для лучшего понимания происходящего внутри JVM.
Я делаю довольно сложный тест, в котором есть:
interface MyCallable {}
class CallableImpl1 implements MyCallable { ... }
class CallableImpl2 implements MyCallable { ... }
class CallableImpl3 implements MyCallable { ... }
class CallableImpl4 implements MyCallable { ... }
class CallableImpl5 implements MyCallable { ... }
class CallableImpl6 implements MyCallable { ... }
class CallableImpl7 implements MyCallable { ... }
class CallableImpl8 implements MyCallable { ... }
/**
Это цель нашего multiple dispatch
*/
class Receiver {
void accept(CallableImpl1 impl); { ... }
void accept(CallableImpl2 impl); { ... }
void accept(CallableImpl3 impl); { ... }
void accept(CallableImpl4 impl); { ... }
void accept(CallableImpl5 impl); { ... }
void accept(CallableImpl6 impl); { ... }
void accept(CallableImpl7 impl); { ... }
void accept(CallableImpl8 impl); { ... }
}
/**
Цель этого товарища: вызвать соответствующий метод у Receiver.
Разные реализации этого интерфейса в тесте и измеряются.
Dispatcher'у кормится List<MyCallable>, в котором перемешаны инстансы CallableImpl{1..8}.
*/
interface Dispatcher {
void call(MyCallable target);
}Конфигурация такая:
- Intel Xeon (Westmere-EP), 3.0 Ghz, 2x6x2 = 24 HW threads, SLES 11 x86_64
- JDK 7b138, x86_64, -server -d64 -Xmx512m -Xms512m
- измеряется пропускная способность: количество вызовов в единицу времени на 24 потоках
- каждый тест запускался в своей JVM, прогрев в 1 минуту, потом 20 итераций по 10 секунд
- в теле Receiver.accept() стоит простой инкремент, так что измеряется не «чистый» вызов, иначе JIT бы просто удалил этот вызов к чёртовой бабушке
Запускаем:
(я опустил доверительные интервалы, т.к. не сумел научить gnuplot рисовать barchart с errorbar'ами) (по оси X — количество типов CallableImpl. 1 ресивер = только CallableImpl1, 2 ресивера = пополам CallableImpl1 и CallableImpl2, и т.д.)
Картинка говорит о многом, в общем-то:
- Производительность double dispatch зависит от того, сколько ресиверов в instance.dispatch((Caller)this). В случае мономорфного (только 1 ресивер) или биморфного (только 2 ресивера) вызова, HotSpot отлично девиртуализует этот вызов: делает typecheck и вызов конкретного метода. Немудрено, что в таких режимах double dispatch ведёт себя так же, как и цепочка instanceof'ов. Мегаморфные вызовы HotSpot не девиртуализует (пока ещё, гы-гы), чтобы не захламлять код.
- Цепочка instanceof-else выиграла по всем параметрам: заинлайнились вызовы соответствующих accept(...).
- Enum'ы проиграли из-за того, что взятие конкретного MyCallable.getType() — виртуальный вызов, а дальше см. п. (а).
- Reflection проиграл прямому вызову из-за тонны обвязок внутри. Проиграл, однако, не очень сильно. Интересно, что на 1-2-морфных вызовах он работает шустрее: вклеивание Method.invoke(...) тому причина.
- MethodHandle, к моему удивлению, продолбал Reflection'у. Мне лень на это сейчас смотреть, подожду релиза по-новее.
Однако, на каждую гайку найдётся свой болт с левой резьбой. Я померил случай, когда все ресиверы вызываются равновероятно. В реальных приложениях это нечастая ситуация (кроме visitor pattern, пожалуй). Там чаще доминирует какой-то конкретный ресивер. Не верите? Возьмите debug JDK и запуститесь с -XX:+TraceTypeProfile.
Так вот, общие рассуждения показывают, что даже обладая профилем, т.е. реальной частотой ресиверов, не каждый случай может быть оптимизирован.
- при double dispatch JIT девиртуализует вызов instance.dispatch((Caller)this) на основании профиля, и вызовет метод для наиболее частого ресивера — WIN!
- в цепочках instanceof информация о профиле сама по себе бесполезна, ибо переставлять if'ы без анализа предикатов нельзя — FAIL
- в enum вызов getType() девиртуализуется на основании профиля, но дальше всё зависит от удачности предсказания переходов в switch — FAIL
- в reflection полная жесть, ничего по профилю предсказать нельзя — FAIL!
Для того, чтобы эти рассуждения проверить, модифицируем тест так, чтобы наиболее частым был один из ресиверов. При этом имеет смысл проверять три варианта:
- Наиболее частый ресивер — первый! В этом случае instanceof'ы должны себя показать во всей красе. Назовём этот случай «best case».
- Наиболее частый ресивер — последний. Instanceof'ы должны курить в сторонке. Назовём этот случай «worst case».
- Наиболее частый ресивер — посередине. Назовём этот случай «average case». Не путать с предыдущим экспериментом!
Запускаем:
Ну, и что мы здесь видим?
- double dispatch когда сумел воспользовался профилем, а когда просто поставил виртуальный вызов, который стоит константу
- производительность instanceof'ов падает: чем больше ресиверов, тем медленее. Сдаётся мне, что если ресиверов будет >20, то он начнёт лихо проигрывать double dispatch'у
- производительность enum'ов упала сразу на биморфных вызовах, и дальше тащится в хвосте
- reflection тоже профилем не пользуется
Вот картинка попроще, double dispatch против цепочки instanceof'ов, на uniform/best/average/worst-случаях, соответственно.
Сырые данные и тесты
Сам тест доступен здесь. Его нужно будет запустить в какой-нибудь обвязке, которая прогревает, считает перформанс и проч. К сожалению, наша родная сюита ещё не в open source, так что придётся попотеть самому.
Полный лог бенчмарка доступен там же, можете проверить его на вшивость.
Если кому-то вдруг захочется по-другому данные нарисовать, разобранные данные можно скачать отсюда. В столбцах: номер эксперимента, количество receiver-ов, тип dispatcher-а, средний throughput, stdev.
Выводы
А какие выводы вы хотите? Пишите безопасный код.
Пишете микробенчмарки? Проводите тщательный анализ результатов. Я только на четвёртый раз получил правдоподобные результаты, предыдущие три раза находил то баг в микробенчмарке, то неправильный режим работы, то слишком мало времени и профиль размыт, етц. И да, микробенчмарки созданы именно для такой деятельности: исследовать corner case'ы, а не делать далеко идущие выводы.
Как перформансник я сделал вывод, что надо внимательно посмотреть на код вокруг и посмотреть, не начали ли все кругом делать мегаморфные вызовы, и не пора ли в Hotspot'е делать мегаморфную девиртуализацию.
Комментариев нет:
Отправить комментарий