Пост из серии "будни перформанс-инженеров". Иногда в проектах возникает необходимость сделать т.н. 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 подобный код вызовет ошибку компиляции, ибо нефиг. Что делать, если всё-таки надо? Значит, нужно в рантайме определить нужный метод.

Для этого есть три базовых варианта:

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) { ... };
}
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) { ... };
}
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 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) { ... }
}

Все эти методы обладают своими плюсами и минусами.

Возможные проблемы: <ol><li>Появился новый класс в иерархии, например, C extends Base. Определили Caller.doSomethingNasty(C cInstance). <ul> <li>double dispatch скомпилировался и отработал нормально</li> <li>instanceof скомпилировался, но проигнорировал все вызовы с C, надо бежать по коду и исправлять везде</li> <li>enum потребовал новой константы в enum, но опять надо бежать по коду и исправлять switch’и</li> <li>reflection скомпилировался, проигнорировал С, надо бежать и везде в Map’ы засовывать новый метод</li> </ul></li> <li> Сложные иерархии. Допустим, A extends B, B extends Base <ul> <li>double dispatch отработал нормально</li> <li>instanceof для bInstance типа B получил (bInstance instanceof A) == true и вызвал не свой метод</li> <li>enum отработал нормально</li> <li>reflection отработал нормально</li> </ul></li> </ol> На основании этого мне кажется, что наиболее безопасным способом является double dispatch. Называйте меня ООП-пуристом, если хотите.

Однако всё это лирика, меня интересуют вопросы производительности. Поэтому настала пора взять и измерить, что на этой нашей Sun JDK быстрее. Меня интересует не столько, какой из этих способов быстрее, а то, как HotSpot себя ведёт на этих вариантах. В реальных проектах выигрыш производительности сильно зависит от приложения, и там первую скрипку играют скорее доводы о безопасной поддержке кода, а не каждой последней капле перформанса.

Отдельной строкой повторю: <b>эти результаты не являются поводом переписывать существующий код из соображений производительности</b>, но на них интересно посмотреть для лучшего понимания происходящего внутри JVM.

Я делаю довольно сложный тест, в котором есть:

<source lang="java"> 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);
}</source>

Конфигурация такая: <ul> <li>Intel Xeon (Westmere-EP), 3.0 Ghz, 2x6x2 = 24 HW threads, SLES 11 x86_64</li> <li>JDK 7b138, x86_64, -server -d64 -Xmx512m -Xms512m</li> <li>измеряется пропускная способность: количество вызовов в единицу времени на 24 потоках</li> <li>каждый тест запускался в своей JVM, прогрев в 1 минуту, потом 20 итераций по 10 секунд</li> <li>в теле Receiver.accept() стоит простой инкремент, так что измеряется не "чистый" вызов, иначе JIT бы просто удалил этот вызов к чёртовой бабушке</li> </ul> Запускаем: <img src="http://people.apache.org/~shade/articles/devirt-habr/uniform.png" alt="image"/> (я опустил доверительные интервалы, т.к. не сумел научить gnuplot рисовать barchart с errorbar’ами) (по оси X — количество типов CallableImpl. 1 ресивер = только CallableImpl1, 2 ресивера = пополам CallableImpl1 и CallableImpl2, и т.д.)

Картинка говорит о многом, в общем-то: <ol> <li>Производительность double dispatch зависит от того, сколько ресиверов в <i>instance.dispatch((Caller)this)</i>. В случае мономорфного (только 1 ресивер) или биморфного (только 2 ресивера) вызова, HotSpot отлично девиртуализует этот вызов: делает typecheck и вызов конкретного метода. Немудрено, что в таких режимах double dispatch ведёт себя так же, как и цепочка instanceof’ов. Мегаморфные вызовы HotSpot не девиртуализует (пока ещё, гы-гы), чтобы не захламлять код.</li> <li>Цепочка instanceof-else выиграла по всем параметрам: заинлайнились вызовы соответствующих accept(…​).</li> <li>Enum’ы проиграли из-за того, что взятие конкретного <i>MyCallable.getType()</i>-- виртуальный вызов, а дальше см. п. (а).</li> <li>Reflection проиграл прямому вызову из-за тонны обвязок внутри. Проиграл, однако, не очень сильно. Интересно, что на 1-2-морфных вызовах он работает шустрее: вклеивание <i>Method.invoke(…​)</i> тому причина.</li> <li>MethodHandle, к моему удивлению, продолбал Reflection’у. Мне лень на это сейчас смотреть, подожду релиза по-новее.</li> </ol> Однако, на каждую гайку найдётся свой болт с левой резьбой. Я померил случай, когда все ресиверы вызываются равновероятно. В реальных приложениях это нечастая ситуация (кроме visitor pattern, пожалуй). Там чаще доминирует какой-то конкретный ресивер. Не верите? Возьмите <a href="http://download.java.net/jdk7/">debug JDK</a> и запуститесь с <b>-XX:+TraceTypeProfile</b>.

Так вот, общие рассуждения показывают, что даже обладая профилем, т.е. реальной частотой ресиверов, не каждый случай может быть оптимизирован. <ul> <li>при double dispatch JIT девиртуализует вызов instance.dispatch((Caller)this) на основании профиля, и вызовет метод для наиболее частого ресивера - <b>WIN!</b></li> <li>в цепочках instanceof информация о профиле сама по себе бесполезна, ибо переставлять if’ы без анализа предикатов нельзя - <b>FAIL</b></li> <li>в enum вызов <i>getType()</i> девиртуализуется на основании профиля, но дальше всё зависит от удачности предсказания переходов в switch - <b>FAIL</b></li> <li>в reflection полная жесть, ничего по профилю предсказать нельзя - <b>FAIL!</b></li> </ul> Для того, чтобы эти рассуждения проверить, модифицируем тест так, чтобы наиболее частым был один из ресиверов. При этом имеет смысл проверять три варианта: <ol> <li>Наиболее частый ресивер — первый! В этом случае instanceof’ы должны себя показать во всей красе. Назовём этот случай <b>"best case"</b>.</li> <li>Наиболее частый ресивер — последний. Instanceof’ы должны курить в сторонке. Назовём этот случай <b>"worst case"</b>.</li> <li>Наиболее частый ресивер — посередине. Назовём этот случай <b>"average case"</b>. Не путать с предыдущим экспериментом!</li> </ol> Запускаем: <img src="http://people.apache.org/~shade/articles/devirt-habr/profiles.png" alt="image"/>

Ну, и что мы здесь видим? <ul> <li>double dispatch когда сумел воспользовался профилем, а когда просто поставил виртуальный вызов, который стоит константу</li> <li>производительность instanceof’ов падает: чем больше ресиверов, тем медленее. Сдаётся мне, что если ресиверов будет >20, то он начнёт лихо проигрывать double dispatch’у</li> <li>производительность enum’ов упала сразу на биморфных вызовах, и дальше тащится в хвосте</li> <li>reflection тоже профилем не пользуется</li></ul> Вот картинка попроще, double dispatch против цепочки instanceof’ов, на uniform/best/average/worst-случаях, соответственно.

<img src="http://people.apache.org/~shade/articles/devirt-habr/dd-vs-iofe.png" alt="image"/>

<h2>Сырые данные и тесты</h2> Сам тест доступен <a href="http://people.apache.org/~shade/articles/devirt-habr/DispatchTest.java">здесь</a>. Его нужно будет запустить в какой-нибудь обвязке, которая прогревает, считает перформанс и проч. К сожалению, наша родная сюита ещё не в open source, так что придётся попотеть самому.

<a href="http://people.apache.org/~shade/articles/devirt-habr/log.gz">Полный лог</a> бенчмарка доступен там же, можете проверить его на вшивость.

Если кому-то вдруг захочется по-другому данные нарисовать, разобранные данные можно скачать <a href="http://people.apache.org/~shade/articles/devirt-habr/predata.data.gz">отсюда</a>. В столбцах: номер эксперимента, количество receiver-ов, тип dispatcher-а, средний throughput, stdev.

<h2>Выводы</h2> А какие выводы вы хотите? Пишите безопасный код.

Пишете микробенчмарки? Проводите тщательный анализ результатов. Я только на четвёртый раз получил правдоподобные результаты, предыдущие три раза находил то баг в микробенчмарке, то неправильный режим работы, то слишком мало времени и профиль размыт, етц. И да, микробенчмарки созданы именно для такой деятельности: исследовать corner case’ы, а не делать далеко идущие выводы.

Как перформансник я сделал вывод, что надо внимательно посмотреть на код вокруг и посмотреть, не начали ли все кругом делать мегаморфные вызовы, и не пора ли в Hotspot’е делать мегаморфную девиртуализацию.<img src="http://shipilev.net/marker.png" width=1 height=1>