elizarov


Блог Романа Елизарова


Previous Entry Share Next Entry
Цена полиморфизма в Java или фактическая полиморфность имеет значение
elizarov

Полиморфизм это один из китов объектно-ориентированного программирования. Язык Java использует полиморфизм повсеместно и не создает программистам преграды для его использования в своем коде. Там есть два типа полиморфных вызовов — интерфейсный вызов и виртуальный вызов. Как и многие другие возможности языков программирования высокого уровня, они имеют свою цену с точки зрения производительности кода. Это значит, что если вы пишете код ориентированный на достижение максимальной производительности, то вам необходимо понимать что это за цена, в каких каких случаях её приходится платить, а в каких нет, где можно себе её позволить, а где нет.

Язык Javа в настоящее время имеет весьма продвинутую реализацию виртуальной машины и очень хороший оптимизирующий компилятор. Сам факт использования интерфейсных или виртуальных вызовов не означает какое-либо замедление работы программы, если фактически используется только одна реализация вызываемого метода. Я наглядно это показал в заметке "Java vs C++ на целых числах". Напомню, что там замерялось время работы такого цикла:

    private int runIteration() { 
        int sum = 0; 
        for (int i = 0, n = list.size(); i < n; i++) 
            sum += list.getInt(i); 
        return sum; 
    }

Здесь в цикле идут интерфейсные вызовы метода getInt через простой интерфейс IntList, который я сделал для этих заметок. А из заметки "Смотрим на ассемблерный код работающего Java приложения" видно, что этот вызов в данном случае вообще ничего не стоит — его просто нет в результирующем машинном коде. Все измерения я производил каждый раз запуская тестовую программу так, чтобы замерялось время работы одной конкретной реализации, и HotSpot компилятор не только встроил реализацию метода getInt прямо в тело цикла, но и развернул цикл.

Однако, я предусмотрел возможность и запуска нескольких реализаций (передавая список их имен в командной строке), которой сейчас и воспользуюсь. При этом в каждом проходе тестирования последовательно замеряется время работы каждой из реализаций. Я возьму самую быструю реализацию интерфейса IntList через int[] и буду замерять время работы метода runIteration в расчете на одну итерацию как отдельно, так и при наличии еще одной, двух или трех других реализаций. Для этих целей я взял ViaByteBuffer1 и ViaByteBuffer2 из этой заметки и ViaByteBuffer3 отсюда. Получаются вот такие результаты (в наносекундах затрачиваемых в среднем на одну итерацию цикла для реализации через int[]):

Размер1234
1 0000.463.448.938.90
10 0000.483.348.768.80
100 0000.503.429.008.89
1 000 0000.743.469.048.99
10 000 0000.783.428.989.04

При двух различных реализациях метода getInt внутри JVM скорость выполнения снижается в несколько раз, при трех реализациях снижается еще более чем в два раза, но при четырех дальнейшего замедления нет.

Дело в том, что в дополнение к случаю мономорфного вызова, когда реализация всего одна и её можно встроить прямо в точку вызова, HotSpot распознает специально случай биморфного вызова, когда есть две фактических реализации, и генерирует код для быстрой проверки класса объекта (в нашем случае переменной list) и условного перехода к нужной реализации. Три и более реализаций считаются HotSpot-ом полиморфным вызовом для которого создается код полноценного интерфейсного или виртуального вызова, который, как мы видим на примере выше, относительно дорого обходится.

Полная картина, на самом деле, несколько сложней, ибо HotSpot учитывает не только количество загруженных в JVM классов, которые реализуют тот или иной метод, но и собирает динамический профиль исполнения для анализа того, какие реализации фактически используются в той или иной точке кода. Если загрузить, сконструировать и даже заполнить данными все четыре реализации IntList, но прогонять тесты только для первой, то результаты будут такие же, как и в случае единственной загруженной реализации.

Более того, если переделать IntList из интерфейса в абстрактный класс и провести такой же тест, то будет видно, что скорость работы мономорфного и биморфного вызова не изменится, а вот полиморфный виртуальный вызов будет работать несколько быстрей чем полиморфный интерфейсный вызов (в общем случае, полиморфный интерфейсный вызов будет работать тем медленней, чем больше интерфейсов реализует данный класс):

Размер1234
1 0000.473.247.527.54
10 0000.493.307.597.58
100 0000.513.307.547.60
1 000 0000.763.407.807.77
10 000 0000.783.397.717.66

При дизайне и анализе производительности кода, который полагается на полиморфизм, очень важно учитывать тот факт, что скорость его исполнения будет зависеть не только от того, как написан интересный вам кусок кода, но может зависеть и от всего остального кода разрабатываемого вами программного обеспечения. Производительность будет зависеть от того, как именно используются ваш код, какая фактическая степень полиморфизма будет в том или ином вызове.


  • 1
Очень интересно. Спасибо!

Хорошая статья, мои наблюдения и эмпирические объяснения (на основе анализа кода v8) согласуются с ней. А недавно нашел http://en.wikipedia.org/wiki/Inline_caching , общие детали реализации тоже описаны.
Еще добавлю, что изведение дубликатов кода может приводить к замедлению его выполнения, когда типы параметров становятся более абстрактными. На практике приходилось уменьшать полиморфизм критических путей в коде написанием специализированной версий.

  • 1
?

Log in

No account? Create an account