Реализация механизма полиморфизма в Java

Что из себя представляет механизм полиморфизма в Java и как он работает? Если это зависит от реализации конкретной JVM, то хотелось бы увидеть это на примере какой-нибудь JVM, например HotSpot.
Для уточнения, в С++ полиморфизм реализуется за счет таблицы виртуальных функций для каждого класса, указатель на которую неявно хранится в каждом экземпляре класса. А как это сделано в Java?

Ответ

Полиморфизм метода, определённого в классе, достигается за счёт выбора по таблице виртуальных методов примерно как в C++. То есть накладные расходы на вызов — это взять у объекта classword (который записан в его заголовке), добавить к нему известное заранее смещение и вызвать метод по указанному адресу.
Полиморфизм метода, определённого в интерфейсе, достигается более сложным путём: в структуре описания класса ищется запись, относящаяся к данному интерфейсу, и в ней уже ищется нужный метод. То есть, скажем,
public static T getFirst(List list) { return list.get(0); }
public static T getFirst(AbstractList list) { return list.get(0); }
Первый случай может оказаться медленнее, потому что мы вызываем метод интерфейса. Хотя метод один и тот же, но разница есть. Даже в байткоде две разные инструкции — invokeinterface и invokevirtual.
JIT-компилятор HotSpot агрессивно использует технику девиртуализации. Естественно в обычный статический вызов превратится вызов final-метода или метода final-класса. Также если runtime-таблица типов говорит, что данный метод нигде не переопределён, вызов будет статическим:
public static T getFirst(ArrayList list) { return list.get(0); }
Хотя ArrayList не final-класс и метод get тоже не final, если мы знаем, что он не переопределён на данный момент ни в одном загруженном классе, мы можем сделать вызов статическим. Если будет загружен новый класс, который нарушит это условие, JIT-компилятор перекомпилирует этот метод.
Если есть варианты, используется профиль типов. К примеру, если этот код уже выполнялся 5000 раз и из них в 4990 случаях вызывался конкретный метод ArrayList.get, то JIT-компилированный код станет примерно таким:
public static T getFirst(List list) { if(list.getClass() == ArrayList.class) { return ((ArrayList)list).get(0); } // обновить профиль типов return list.get(0); }
Проверка list.getClass() == ArrayList.class весьма быстрая — это достать classword (по скорости как прочитать поле объекта) и сравнить с константой (на момент JIT-компиляции точно известен classword для класса ArrayList). Branch-prediction тоже хорошо отработает, если условие в подавляющем большинстве случаев выполняется.
Если из 5000 вызовов было 3000 ArrayList и 1990 LinkedList, код будет примерно таким:
public static T getFirst(List list) { if(list.getClass() == ArrayList.class) { return ((ArrayList)list).get(0); } else if(list.getClass() == LinkedList.class) { return ((LinkedList)list).get(0); } // обновить профиль типов return list.get(0); }
Это биморфный вызов. Если же популярных вариантов было больше двух, то тогда уж вызов останется честным виртуальным.
Разумеется, если вы в одном методе вызываете несколько методов неизвестного объекта, переданного параметром (или в цикле вызываете метод много раз), то тип проверяться будет только один раз.
Если вызов удалось девиртуализовать (хотя бы в биморфный вариант), то дальше агрессивно применяется инлайнинг (видал своими глазами как в один метод инлайнилось штук 70 других на глубину вызовов до 8-9: в первый инлайнится второй, в него третий и т. д.). Инлайнинг открывает дорогу к тонне других оптимизаций.
Как вы уже поняли, первоначально код выполняется во-первых, медленнее, а во-вторых в режиме профилирования. То есть при каждом вызове метода не просто происходит вызов, но и обновляется таблица статистики, где указывается, какой конкретно класс тут был. Когда статистика собрана, метод перекомпилируется с учётом неё. При этом если есть быстрая и медленная ветка, то медленная будет обновлять статистику дальше. Например, если сценарий использования программы поменялся, то метод может быть снова перекомпилирован.