Уже давно определённые вещи из мира функционального программирования всё сильнее проникают в нефункциональные языки. Может показаться странным, что в Java смогли интегрировать лямбда-выражения, а вот оптимизацию хвостовой рекурсии (преобразование рекурсии в эквивалентный цикл) до сих пор не сделали, хотя она гораздо проще. Почему её нет?
Попробуем разобраться с причинами и посмотрим, что можно сделать своими руками.
В первую очередь, пример. Предлагаю не мучить в этот раз несчастный факториал и использовать другую функцию:
static int add(int x, int y) {
if (y == 0) return x;
return add(x ^ y, (x & y) << 1);
}
return
. Оптимизация заключается в том, чтобы при рекурсивном вызове не создавать новый кадр стэка, а переиспользовать текущий. Для этого нужно новые параметры положить на место старых и выполнить безусловный переход на первую инструкцию метода. В псевдокоде это будет выглядеть так:static int add(int x, int y) {
start: {
if (y == 0) return x;
(x, y) = (x ^ y, (x & y) << 1);
goto start;
}
}
static int add(int x, int y) {
while (true) {
if (y == 0) return x;
int _x = x ^ y;
int _y = (x & y) << 1;
x = _x;
y = _y;
}
}
GOTO
мы теряем множество кадров стэка с информацией о точках входа, которая должна у нас быть по спецификации.GOTO
, нужно точно знать, что по факту должен вызываться тот же метод. Это требование выполнено для:final
классов;invokespecial
. Данный вариант не может быть создан компилятором из исходного Java кода, так как invokespecial
доступен только для вызова методов суперкласса.try
блока, то мы не можем просто так взять и передать управление инструкции вне этого самого блока. Вот пример:static int f(boolean shouldThrow) {
if (shouldThrow) throw new RuntimeException();
try {
f(!shouldThrow);
} catch (Exception e) {
}
return -1;
}
f(false)
должен возвратить -1, но если сделать GOTO
в месте рекурсивного вызова, то мы получим RuntimeException
, а это явно отличается от того, что должно происходить при корректной оптимизации.ClassLoader
, изменения будут видны только в рантайме.static method
/ final method
/ final class
;try
блоков.static int gcd(int n, int m) {
try {
if (m == 0) return n;
} catch (Throwable t) {
// do nothing
}
return gcd(m, n % m);
}
static gcd(II)I
TRYCATCHBLOCK TryBlockStart TryBlockEnd CatchBlockStart java/lang/Throwable
TryBlockStart:
ILOAD 1
IFNE ElseBlock
ILOAD 0
TryBlockEnd:
IRETURN
CatchBlockStart:
ASTORE 2 // сохранение исключения во временную переменную - дефолтный пустой обработчик
ElseBlock:
ILOAD 1
ILOAD 0
ILOAD 1
IREM
INVOKESTATIC Main.gcd(II)I
IRETURN
try
блоков. У каждого описания есть 4 составляющих: метка начала блока, метка конца блока, метка обработчика исключения и дескриптор класса исключения. Эта информация позволяет нам однозначно определить инструкции, находящиеся внутри try
блоков, и не производить для них оптимизацию.INVOKE*
с дескриптором метода, совпадающим с самим методом (в данном случае ищется дескриптор gcd(II)I
метода класса Main
), за которыми непосредственно находится инструкция типа RETURN
.INVOKESTATIC
надо преобразовать из вызова в безусловный переход. Известно, что в момент вызова на стэке находятся все параметры. Для статических методов всё просто, нужно сохранить эти параметры обратно в локальные переменные и сделать безусловный переход в самое начало:static gcd(II)I
TRYCATCHBLOCK TryBlockStart TryBlockEnd CatchBlockStart java/lang/Throwable
StartLabel:
TryBlockStart:
ILOAD 1
IFNE ElseBlock
ILOAD 0
TryBlockEnd:
IRETURN
CatchBlockStart:
ASTORE 2
ElseBlock:
ILOAD 1
ILOAD 0
ILOAD 1
IREM
ISTORE 1
ISTORE 0
GOTO StartLabel
this
. Технически возможно найти в байткоде место вычисления этого объекта и проводить оптимизацию только тогда, когда это вычисление равно ALOAD 0
.this
(сделав ASTORE 0
). Как ни странно, такой подход работает, но я, в силу недостаточности знаний, не могу гарантировать, что JIT в этой ситуации будет вести себя корректно. Хотел бы узнать ответ в комментариях — есть ли тут какие-нибудь риски.К сожалению, не доступен сервер mySQL