JIT-компилятор оптимизирует не круто, а очень круто

Недавно Лукас Эдер заинтересовался в своём блоге ^[1], способен ли JIT-компилятор Java оптимизировать такой код, чтобы убрать ненужный обход списка из одного элемента:

// ... а тут мы "знаем", что список содержит только одно значение
for (Object object : Collections.singletonList("abc")) {
    doSomethingWith(object);
}

Вот мой ответ: JIT может даже больше. Мы будем говорить про HotSpot JVM 64 bit восьмой версии. Давайте рассмотрим вот такой простой метод, который считает суммарную длину строк из переданного списка:

static int testIterator(List<String> list) {
    int sum = 0;
    for (String s : list) {
        sum += s.length();
    }
    return sum;
}

Многим Java-программистам известно, что этот код полностью эквивалентен следующему:

static int testIterator(List<String> list) {
    int sum = 0;
    Iterator<String> it = list.iterator();
    while(it.hasNext()) {
        String s = it.next();
        sum += s.length();
    }
    return sum;
}

Разумеется, в общем случае в list может оказаться всё что угодно и поэтому JIT-компилятору придётся сгенерировать честные виртуальные вызовы на месте iterator(), hasNext() и next(), что, конечно, не очень быстро. Но что случится, если мы всегда будем вызывать этот метод, подавая ему на вход singletonList? Давайте добавим простенький метод main():

public class Test {
    static int res = 0;

    public static void main(String[] args) {
        for (int i = 0; i < 100000; i++) {
            res += testIterator(Collections.singletonList("x"));
        }
        System.out.println(res);
    }
}

Здесь мы вызываем наш testIterator в цикле достаточное количество раз, чтобы скомпилировать метод JIT-компилятором C2. Как некоторые из вас уже знают, в виртуальной машине HotSpot есть два JIT-компилятора: C1 (клиентский) и C2 (серверный). В 64-битной версии Java 8 с настройками по умолчанию они работают совместно. Сперва метод компилируется с помощью C1 (который компилирует быстро, но создаёт не очень оптимальный код). При этом в код добавляются дополнительные инструкции, которые собирают некоторую статистику (это называется "профилирование"). Это, конечно, замедляет выполнение, но пригождается в дальнейшем. Среди различных профилей собирается профиль типов. В нашем случае JVM внимательно следит, какой тип имеет параметр list при каждом вызове. И тут виртуальная машина замечает, что в 100% случаев на входе был список типа Collections$SingletonList ^[2] (который возвращает метод singletonList).

Когда количество вызовов метода достигает некоторого порога, метод перекомпилируется компилятором C2, которому доступен собранный профиль. C2 делает разумное предположение, что раз до сих пор всегда был SingletonList, то и далее он будет часто попадаться. А значит, iterator() точно вызовет метод singletonIterator() ^[3]. Но там уже нетривиальный объект, который, к примеру, содержит поле hasNext, чтобы отследить, что его не вызвали дважды, и кинуть если надо NoSuchElementException. Способен ли C2 с этим побороться?

Чтобы узнать ответ, мы можем попросить JIT-компилятор вывести ассемблер сгенерированный для методов. Для этого нам потребуется установить hsdis ^[4]. Потом можно воспользоваться удобными инструментами вроде JITWatch ^[5] или написать JMH ^[6]-бенчмарк и воспользоваться опцией -perfasm. Но здесь у нас пример простой, поэтому мы обойдёмся без сторонних инструментов и просто запустим виртуальную машину с такими волшебными параметрами:

$ java -XX:+UnlockDiagnosticVMOptions -XX:+PrintCompilation -XX:+PrintAssembly Test >output.txt

Будьте осторожны: вывод этой команды может напугать маленьких детей. Но порывшись в нём, вы найдёте код, сгенерированный для нашего метода testIterator. Вот что сгенерировал C2 на платформе Intel x64 с кучей до 4 Гб:

  # {method} {0x0000000055120518} 'testIterator' '(Ljava/util/List;)I' in 'Test'
  # parm0:    rdx:rdx   = 'java/util/List'
  #           [sp+0x20]  (sp of caller)
  0x00000000028e7560: mov    %eax,-0x6000(%rsp)
  0x00000000028e7567: push   %rbp
  0x00000000028e7568: sub    $0x10,%rsp         ;*synchronization entry
                                                ; - Test::testIterator@-1 (line 15)

  0x00000000028e756c: mov    0x8(%rdx),%r10d    ; implicit exception: dispatches to 0x00000000028e75bd
  0x00000000028e7570: cmp    $0x14d66a20,%r10d  ;   {metadata('java/util/Collections$SingletonList')}
  0x00000000028e7577: jne    0x00000000028e75a0  ;*synchronization entry
                                                ; - java.util.Collections::singletonIterator@-1
                                                ; - java.util.Collections$SingletonList::iterator@4
                                                ; - Test::testIterator@3 (line 16)

  0x00000000028e7579: mov    0x10(%rdx),%ebp    ;*getfield element
                                                ; - java.util.Collections$SingletonList::iterator@1
                                                ; - Test::testIterator@3 (line 16)

  0x00000000028e757c: mov    0x8(%rbp),%r11d    ; implicit exception: dispatches to 0x00000000028e75c9
  0x00000000028e7580: cmp    $0x14d216d0,%r11d  ;   {metadata('java/lang/String')}
  0x00000000028e7587: jne    0x00000000028e75b1
  0x00000000028e7589: mov    %rbp,%r10          ;*checkcast
                                                ; - Test::testIterator@24 (line 16)

  0x00000000028e758c: mov    0xc(%r10),%r10d    ;*getfield value
                                                ; - java.lang.String::length@1
                                                ; - Test::testIterator@30 (line 17)

  0x00000000028e7590: mov    0xc(%r10),%eax     ;*synchronization entry
                                                ; - Test::testIterator@-1 (line 15)
                                                ; implicit exception: dispatches to 0x00000000028e75d5
  0x00000000028e7594: add    $0x10,%rsp
  0x00000000028e7598: pop    %rbp
  0x00000000028e7599: test   %eax,-0x27b759f(%rip)        # 0x0000000000130000
                                                ;   {poll_return}
  0x00000000028e759f: retq   
  ... // дальше холодные пути

Первое, что бросается в глаза — это краткость кода. С вашего позволения я прокомментирую, что тут происходит:

// Стандартный стековый фрейм - подобным образом начинается всякий JIT-компилированный метод
mov    %eax,-0x6000(%rsp)
push   %rbp
sub    $0x10,%rsp         
// Загружаем идентификатор класса объекта из переменной list (указатель на объект пришёл в метод в регистре rdx).
// Идентификатор класса лежит в объекте по смещению 0x8. Это похоже на вызов list.getClass().
// При этом здесь происходит неявная проверка на null. Если окажется, что передали в метод null,
// процессор сгенерирует аппаратное исключение в связи с обращением по запрещённому адресу.
// Исключение перехватит виртуальная машина и заботливо транслирует его в NullPointerException
mov    0x8(%rdx),%r10d
// Сравниваем list.getClass() с идентификатором класса Collections$SingletonList. Этот идентификатор не меняется
// за время работы JVM и, конечно, JIT его знает, поэтому это просто сравнение с константой
cmp    $0x14d66a20,%r10d
// Если list - это не SingletonList, выпрыгиваем на холодный путь
jne    0x00000000028e75a0
// Читаем приватное поле Collections$SingletonList.element в регистр rbp. Хотя указатели 64-битные, при размере кучи 
// меньше 4 Гб верхние 32 бита всегда нули, поэтому виртуальная машина их не хранит и копирует только 32 нижних бита в ebp
mov    0x10(%rdx),%ebp
// Читаем идентификатор класса элемента и сверяем его с идентификатором класса String (аналогично тому, что выше)
mov    0x8(%rbp),%r11d
cmp    $0x14d216d0,%r11d
// Если элемент списка - не строка, выпрыгиваем наружу на холодный путь (там будет создано и выброшено ClassCastException)
jne    0x00000000028e75b1
// Читаем приватное поле String.value в регистр r10. Это массив char[], в котором хранится сама строка
mov    %rbp,%r10
mov    0xc(%r10),%r10d
// Читаем длину массива в регистр eax, который стандартно используется для передачи возвращаемого значения метода
mov    0xc(%r10),%eax
// Восстановление стекового фрейма
add    $0x10,%rsp
pop    %rbp
// Проверка на safe-point. С её помощь JVM может забрать контроль у скомпилированного кода, например, для сборки мусора.
test   %eax,-0x27b759f(%rip)
// Выход из метода
retq   

Если кому-то всё ещё сложно это понять, давайте перепишем на псевдокоде:

if (list.class != Collections$SingletonList) {
  goto SLOW_PATH;
}
str = ((Collections$SingletonList)list).element;
if (str.class != String) {
  goto EXCEPTIONAL_PATH;
}
return ((String)str).value.length;

Видите? На горячем пути нет ни цикла, ни выделения памяти под итератор, ни одного вызова метода. Всего лишь несколько разыменований и две быстрые проверки (которые всегда были ложны, поэтому предсказание ветвлений в процессоре отработает на ура). JIT-компилятор заинлайнил всё, что можно, понял, что итератор из метода не убегает, избавился от выделения памяти, развернул цикл и даже смог удалить флаг hasNext и связанные с ним проверки, статически доказав, что они не нужны! Сложение и переменная sum также испарились. И тем не менее, метод полностью корректен. Если окажется, что при следующем вызове ему передадут не singletonList, а что-то другое, он просто уйдёт на холодный путь (который, конечно, значительно медленнее). Остальные исключительные ситуации тоже обрабатываются. Можно передать null вместо list или подсунуть в список не строку (слава type erasure) — всё это будет обработано в соответствии с семантикой языка.

Что же произойдёт, если сценарий работы программы изменится? Предположим, через некоторое время мы вообще перестали передавать в этот метод singletonList и передаём теперь всякие другие списки. На медленном пути виртуальная машина продолжает собирать статистику. Если она обнаружит, что медленный путь происходит сильно часто, JIT-компилятор перекомпилирует метод, убрав специальную обработку singletonList и вставив сразу честные виртуальные вызовы. Может ещё, кстати, сделать две ветки, если вы используете только две разные реализации списков. Этим JIT отличается от приложений скомпилированных заранее: исполняемый машинный код вашей программы может меняться, следуя за изменениями в её поведении.

Автор: lany

Источник ^[7]