Why Does the Jvm Still Not Support Tail-Call Optimization

Why does the JVM still not support tail-call optimization?

Diagnosing Java Code: Improving the Performance of Your Java Code (alt) explains why the JVM does not support tail-call optimization.

But although it is well known how to automatically transform a tail-recursive function into a simple loop, the Java specification doesn't require that this transformation be made. Presumably, one reason it is not a requirement is that, in general, the transformation can't be made statically in an object-oriented language. Instead, the transformation from tail-recursive function to simple loop must be done dynamically by a JIT compiler.

It then gives an example of Java code that won't transform.

So, as the example in Listing 3 shows, we cannot expect static compilers to perform transformation of tail recursion on Java code while preserving the semantics of the language. Instead, we must rely on dynamic compilation by the JIT. Depending on the JVM, the JIT may or may not do this.

Then it gives a test you can use to figure out if your JIT does this.

Naturally, since this is an IBM paper, it includes a plug:

I ran this program with a couple of
the Java SDKs, and the results were
surprising. Running on Sun's Hotspot
JVM for version 1.3 reveals that
Hotspot doesn't perform the
transformation. At default settings,
the stack space is exhausted in less
than a second on my machine. On the
other hand, IBM's JVM for version 1.3
purrs along without a problem,
indicating that it does transform the
code in this way.

Does the JVM prevent tail call optimizations?

This post: Recursion or Iteration? might help.

In short, tail call optimization is hard to do in the JVM because of the security model and the need to always have a stack trace available. These requirements could in theory be supported, but it would probably require a new bytecode (see John Rose's informal proposal).

There is also more discussion in Sun bug #4726340, where the evaluation (from 2002) ends:

I believe this could be done nonetheless, but it is not a small task.

Currently, there is some work going on in the Da Vinci Machine project. The tail call subproject's status is listed as "proto 80%"; it is unlikely to make it into Java 7, but I think it has a very good chance at Java 8.

Why can't tail calls be optimized in JVM-based Lisps?

Real TCO works for arbitrary calls in tail position, not just self calls, so that code like the following does not cause a stack overflow:

(letfn [(e? [x] (or (zero? x) (o? (dec x))))
        (o? [x] (e? (dec x)))]
  (e? 10))

Clearly you'd need JVM support for this, since programs running on the JVM cannot manipulate the call stack. (Unless you were willing to establish your own calling convention and impose the associated overhead on function calls; Clojure aims to use regular JVM method calls.)

As for eliminating self calls in tail position, that's a simpler problem which can be solved as long as the entire function body gets compiled to a single JVM method. That is a limiting promise to make, however. Besides, recur is fairly well liked for its explicitness.

Tail Call Optimisation in Java

Why can't Java use the same approach ?

I can't say which approach will be used, but it's better-explained in Project Loom's proposal:

As adding the ability to manipulate call stacks to the JVM will undoubtedly be required, it is also the goal of this project to add an even lighter-weight construct that will allow unwinding the stack to some point and then invoke a method with given arguments (basically, a generalization of efficient tail-calls). We will call that feature unwind-and-invoke, or UAI. It is not the goal of this project to add an automatic tail-call optimization to the JVM.

As far as I've heard, work has not yet begun on tail calls, as Fibers and Continuations seem to currently be a higher priority.

Does Java 8 have tail call optimization?

As far as I know Java 8 does not have tail call optimization. Afaik it isn't related to the actual compiler trick, because that one is simple, but to preserve a callstack for security purposes. But I guess it would be possible with a bytecode rewriter.

I get a StackOverFlowException on this code because my JVM doesn't support tail call optimizaion, right?

No JVM that I'm aware of supports tail call optimization. This is not an oversight. Apparently this optimization has significant consequences for Java reflection and Java security managers.

References:

• "Tail calls in the VM" by John Rose @ Oracle.
• Bug 4726340 - RFE: Tail Call Optimization

Why is tail call optimization not occurring here?

VSadov provides the explicit reason for this in his response:

Generally JIT emits tail calls when it finds that profitable.

In addition, he goes on to state:

This is a part that is not expressible in C#. Unlike inlining, which
can be forced via attributes, tailcalling cannot be currently forced.
If one needs to write the code like emitted by EmitMethodCall, he
cannot use C#.

So the answer is that while tailcalls are definitely available and used, there is no way to either predict when they will be used or force them to be used in C#.

Does java support and optimize away tail-recursive calls?

Java supports tail-recursive calls, but AFAIK it doesn't optimize them away. I think it's the Scala compiler that is simply capable of this, not the JVM itself. Check out the @tailrec annotation in Scala to see what more the compiler is capable of :)

But regardless of whether Java/JVM optimizes tail-recursion away, your function would be harder to optimize than necessary.

Look at this:

int sum(List<Integer> integers) {
    return sum(integers, 0);
}

int sum(List<Integer> integers, int sumSoFar) {
    if (integers.isEmpty())
        return sumSoFar;
    else
        return sum(
                integers.subList(1, integers.size()),
                sumSoFar + integers.get(0)
        );
}

See, I've added an overloaded sum with a so-far calculated sum parameter. This way when you recur in the else branch you don't need the actual stack frame any more - you got all you need as function arguments in the recursive call.

In your snippet the stack frame would probably have to exist as long as the recursive call..

Why won't the Scala compiler apply tail call optimization unless a method is final?

Consider the following interaction with the REPL. First we define a class with a factorial method:

scala> class C {
         def fact(n: Int, result: Int): Int =
           if(n == 0) result
           else fact(n - 1, n * result)
       }
defined class C

scala> (new C).fact(5, 1)
res11: Int = 120

Now let's override it in a subclass to double the superclass's answer:

scala> class C2 extends C {
         override def fact(n: Int, result: Int): Int = 2 * super.fact(n, result)
       }
defined class C2

scala> (new C).fact(5, 1)
res12: Int = 120

scala> (new C2).fact(5, 1)

What result do you expect for this last call? You might be expecting 240. But no:

scala> (new C2).fact(5, 1)
res13: Int = 7680

That's because when the superclass's method makes a recursive call, the recursive call goes through the subclass.

If overriding worked such that 240 was the right answer, then it would be safe for tail-call optimization to be performed in the superclass here. But that isn't how Scala (or Java) works.

Unless a method is marked final, it might not be calling itself when it makes a recursive call.

And that's why @tailrec doesn't work unless a method is final (or private).

UPDATE: I recommend reading the other two answers (John's and Rex's) as well.

why scala doesn't make tail call optimization?

The Scala standard library has an implementation of trampolines in scala.util.control.TailCalls. So revisiting your implementation... When you build up the nested calls with continuation(func(t)), those are tail calls, just not optimized by the compiler. So, let's build up a T => TailRec[T], where the stack frames will be replaced with objects in the heap. Then return a function that will take the argument and pass it to that trampolined function:

import util.control.TailCalls._
def n_times_trampolined[T](func: T => T, count: Int): T => T = {
  @annotation.tailrec
  def n_times_cont(cnt: Int, continuation: T => TailRec[T]): T => TailRec[T] = cnt match {
    case _ if cnt < 1 => throw new IllegalArgumentException(s"count was wrong $count")
    case 1 => continuation
    case _ => n_times_cont(cnt - 1, t => tailcall(continuation(func(t))))
  }
  val lifted : T => TailRec[T] = t => done(func(t))
  t => n_times_cont(count, lifted)(t).result
}

---

Related Topics