4 августа 2012 г.

HotSpot OSR

Довольно старая уже, но от этого ничуть не менее интересная статья в блоге Cliff Click (это главный инженер Azul) про тонкости JIT-компиляции.

Клифф рассказывает чем отличается "обычная" компиляция метода, и компиляция в режиме On-the-stack-Replacement (OSR), и почему эту разницу стоит иметь в виду.

Обычная компиляция случается когда JVM обнаруживает, что какой-то метод достаточно горячий, чтобы его имело смысл скомпилировать. Для этого с каждым методом связывается счетчик, который считает число вызовов метода, и число обратных переходов (backedge) (т.е. переходов "назад" по потоку инструкций) внутри метода (sic!). Вторая часть может показаться непонятной, но это просто способ считать итерации циклов, если они в методе есть. Таким образом метод будет считаться горячим не только если он часто вызывается, но и если сам он вызывается не очень часто, но внутри него есть достаточно "тяжелые" циклы.

Когда счетчик перевалит за какой-то порог (скажем, 10 000) — последовательность байт-кодов метода ставится в очередь на компиляцию. При первой же возможности JIT до нее доберется, скомпилирует, и заменит ссылку в таблице методов на оптимизированную версию. И при очередном, 11 042-м вызове исполнение пойдет уже в скомпилированный и оптимизированный метод.

Здесь все круто, но есть одно "но": чтобы подменить интерпретируемую версию компилированной нужно "выйти и снова зайти" — выполнение метода должно завершиться, и тогда очередной вызов этого метода будет уже выполнять скомпилированный код. А что делать, если внутри метода тяжелые циклы — ждать пока он в интерпретируемом режиме завершится? "Клинический" случай это когда я прямо в main написал какой-то сложный алгоритм с тройной вложенности циклом — получается, у меня вообще нет шансов увидеть его скомпилированным.

Чтобы JIT в таких ситуациях не ударял в грязь лицом, ему нужно уметь заменять версии метода на лету, прямо по ходу его выполнения. Именно такая махинация и называется подменой "на стеке", On the Stack Replacement, OSR.

Надо сразу сказать, что задача эта в общем случае очень нетривиальна, ведь скомплированная версия должна полностью "принять в наследство" от интерпретируемой текущее состояние выполнения. Но скомпилированная и интерпретируемая версии кода могут (и почти наверняка будут) очень по-разному это состояние хранить. Клифф приводит в пример простейший цикл вычисления хэш-кода строки: hash = hash*31 + ary[i]; — состояние интерпретатора будет состоять из hash, arr, i, в то время как JIT скорее всего будет хранить что-то вроде hash, p = A+12+i*2, и инкрементить p+=2 на каждой итерации. Если здесь переход вам кажется несложным, то представьте, что будет если JIT еще и развернет (unroll) цикл? Получается, для OSR мало сгенерировать сам код метода — нужно еще и сгенерировать код-"адаптер", который сможет преобразовать состояние интерпретатора в тот вид, который нужен скомпилированной версии. Но генерация такого адаптера для произвольной точки кода будет очень сложной. Проще заранее фиксировать некий набор safepoint-ов, в которых только и можно "переключаться" — тогда задача становится обозримой.

Собственно, "обычный" (не-OSR) компилятор использует в качестве таких safepoint-ов границы между методами. OSR же добавляет возможность переключаться на backedge-ах циклов.

До сих пор была довольно общеизвестная информация, ее давно и много где можно встретить. А вот что интересно: поскольку обычная и OSR компиляция стартуют с разных точек в коде, то для одного и того же метода в режиме обычной и OSR компиляции JIT получает на вход разные последовательности байткодов. OSR получает как бы "вывернутую" изнутри наружу версию кода. И результат компиляции может довольно сильно отличаться. Клифф сначала приводит простой пример: вот так выглядит код метода с простым циклом
i=0;
    loop:
    if(P) goto done;
      S3; A[i++];
    goto loop; // <<--- OSR HERE
    done:
    S2;
А так он будет выглядеть для JIT-а в случае OSR компиляции:
A=value on entry from interpreter;
    i=value on entry from interpreter;
    goto loop;
    loop:
    if(P) goto done;
      S3; A[i++];
    goto loop;
    done:
Здесь пока все довольно прозрачно: это все еще очевидно цикл прохода по массиву с шагом 1, и все оптимизации к нему все еще применимы. Но вот если взять вложенный цикл все становится сложнее:
loop1:
    if(P1) goto done1;
      S1; i=0;
      loop2:
      if(P2) goto done2;
        S3; A[i++];
      goto loop2; // <<--- OSR HERE
      done2:
      S2;
    goto loop1;
    done1:
Если представить себе, как будет выглядеть этот цикл с точки зрения OSR (это требует некоторого напряжения):
A=...value on entry from interpreter...
    i=...value on entry from interpreter...
    goto loop2;
    loop2:
    if(P2) goto done2;
      S3; A[i++];
    goto loop2;
      done2:
      S2;
      goto loop1;
      loop1:
      if(P1) goto done1;
      S1; i=0;
    goto loop2;
    done1:
   ....
Здесь уже не так-то просто разглядеть структуру цикла по массиву. Чуть упростив
A=...value on entry from interpreter...
    i=...value on entry from interpreter...
    loop2:
      if(P2) {
        S2;
        if(P1) goto done1;
        S1; i=0;
      } else {
        S3; A[i++];
      }
    goto loop2;
    done1:
    ....
В чем здесь проблема? — проблема в том, что эвристики компилятора уже не узнают здесь "итерацию по массиву". А значит у нас не будет range check elimination, и, возможно, еще каких-то вкусных плюшек. Производительность этого кода может быть раза в 2-3 хуже, чем не-OSR версии.

Что можно сделать, чтобы избежать такой ситуации? Клифф рекомендует вместо "цикл внутри цикла внутри цикла" организовывать код как "цикл внутри функции внутри цикла внутри функции" -- т.е. выделять каждый потенциально тяжелый цикл в отдельный метод. Во-первых, так увеличивается вероятность, что внутренний цикл будет скомпилирован в не-OSR режиме, а во-вторых, метод с одним циклом, даже вывернутый наизнанку OSR-ом, все равно остается достаточно простым для компилятора.

Мне здесь кажется важным вот что: совет Клиффа, если его самого чуть упросить, говорит просто "не делайте слишком много работы в одном методе". То есть требования производительности здесь идут рука об руку с требованиями чистоты и простоты кода. Пишите простой, достаточно мелко-гранулированный код — и, чаще всего, он и работать будет быстро.