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

A

5

98

Two years after does-the-jvm-prevent-tail-call-optimizations, there seems to be a prototype implementation and MLVM has listed the feature as "proto 80%" for some time now.

Is there no active interest from Sun's/Oracle's side in supporting tail calls or is it just that tail calls are "[...] fated to come in second place on every feature priority list [...]" as mentioned at the JVM Language Summit?

I would be really interested if someone has tested a MLVM build and could share some impressions of how well it works (if at all).

Update: Note that some VMs like Avian support proper tail-calls without any issues.

Altimetry answered 1/9, 2010 at 9:7 Comment(9)

With the reported exodus of Sun people from Oracle, I would not expect that any of the current projects continue unless explicitly said so from Oracle :( – Guberniya 1/9, 2010 at 10:42

Note that your accepted answer is completely wrong. There is no fundamental conflict between tail call optimization and OOP and, of course, several languages like OCaml and F# have both OOP and TCO. – Pelaga 23/2, 2011 at 14:51

Well, calling OCaml and F# OOP languages is a bad joke in the first place. But yes, OOP and TCO have not much in common, except the fact that the runtime has to check that the method being optimized is not overridden/subclassed somewhere else. – Altimetry 23/2, 2011 at 22:58

+1 Coming from a C background, I always assumed that TCO was a given in any modern JVM. It never occurred to me to actually check and when I did the results were surprising... – Argumentative 5/12, 2011 at 21:41

@soc: "except the fact that the runtime has to check that the method being optimized is not overridden/subclassed somewhere else". Your "fact" is complete nonsense. – Pelaga 30/1, 2012 at 21:41

@soc: Note that your accepted answer is wrong for the reasons I explained in my comment beneath it. – Pelaga 30/1, 2012 at 21:42

With Scala being an object-functional language that runs on the JVM and performs tail call optimization, I believe most of what's said here is wrong and void? – Photojournalism 24/11, 2013 at 16:56

Scala's compiler does all the hard work for you, not the JVM. But because it is at compile-time, only the most simplest tail recursive scenarios can be optimized (e. g. anything involving dynamic dispatch, non-final methods, mutually recursive tail calls, etc). There are runtimes out there which support the “full level” of tail recursion, though. – Altimetry 26/11, 2013 at 2:11

possible duplicate of Does the JVM prevent tail call optimizations? – Kapellmeister 19/6, 2015 at 12:55

D

33

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.

Diglot answered 10/9, 2010 at 3:15 Comment(7)

FWIW, tail calls are not just about self-recursive functions as he implies. Tail calls are any function calls that appear in tail position. They do not have to be calls to self and they do not have to be calls to statically known locations (e.g. they can be virtual method calls). The problem he describes is a non-issue if tail call optimization is done properly in the general case and, consequently, his example works perfectly in object oriented languages that support tail calls (e.g. OCaml and F#). – Pelaga 23/2, 2011 at 14:50

"must be done dynamically by a JIT compiler" which means it must be done by the JVM itself rather than the Java compiler. But the OP is asking about the JVM. – Antibiotic 21/10, 2011 at 11:24

"in general, the transformation can't be made statically in an object-oriented language." This is a quote of course, but every time I see such excuse I would like to ask about numbers -- because I wouldn't be surprised if in practice in majority of cases it could be established at compile time. – Epigenous 4/2, 2012 at 10:37

The link to the cited article is now broken, though Google does have it cached. More importantly, the author's reasoning is faulty. The example given could be tail-call optimized, using static and not just dynamic compilation, if only the compiler inserted an instanceof check to see if this is an Example object (rather than a subclass of Example). – Rockie 23/9, 2012 at 19:33

For reference, the test class from the paper is

public class TailRecursionTest { private static int loop(int i) { return loop(i); } public static void main(String[] args) { loop(0); } }

– Danidania 27/11, 2013 at 22:23

just link to webarchive web.archive.org/web/20120506085636/http://www.ibm.com/… – Anglesite 29/1, 2015 at 22:30

@Epigenous In principle, tail call optimization (TCO) can always be done: Just pop local variables and parameters from the stack, push parameters for the tail call, make sure you keep the return address, and JMP instead of JSR to the new function. You lose the caller's data on the stack, so exception traces become less informative, so not doing this can be justified as a conscious decision. Also, unfortunate implementation choices can prevent anything from being doable. – Shwalb 28/12, 2018 at 10:15

M

34

One reason I've seen in the past for not implementing TCO (and it being seen as difficult) in Java is that the permission model in the JVM is stack-sensitive and thus tail-calls must handle the security aspects.

I believe this was shown to not be an obstacle by Clements and Felleisen [1] [2] and I'm pretty sure the MLVM patch mentioned in the question deals with it as well.

I realize this does not answer your question; just adding interesting information.

Marilee answered 23/2, 2011 at 21:29 Comment(1)

+1. Listen questions/responses at the end of this presentation of Brian Goetz youtube.com/watch?v=2y5Pv4yN0b0&t=3739 – Embrace 24/11, 2017 at 16:3

D

33

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.

Diglot answered 10/9, 2010 at 3:15 Comment(7)

FWIW, tail calls are not just about self-recursive functions as he implies. Tail calls are any function calls that appear in tail position. They do not have to be calls to self and they do not have to be calls to statically known locations (e.g. they can be virtual method calls). The problem he describes is a non-issue if tail call optimization is done properly in the general case and, consequently, his example works perfectly in object oriented languages that support tail calls (e.g. OCaml and F#). – Pelaga 23/2, 2011 at 14:50

"must be done dynamically by a JIT compiler" which means it must be done by the JVM itself rather than the Java compiler. But the OP is asking about the JVM. – Antibiotic 21/10, 2011 at 11:24

"in general, the transformation can't be made statically in an object-oriented language." This is a quote of course, but every time I see such excuse I would like to ask about numbers -- because I wouldn't be surprised if in practice in majority of cases it could be established at compile time. – Epigenous 4/2, 2012 at 10:37

The link to the cited article is now broken, though Google does have it cached. More importantly, the author's reasoning is faulty. The example given could be tail-call optimized, using static and not just dynamic compilation, if only the compiler inserted an instanceof check to see if this is an Example object (rather than a subclass of Example). – Rockie 23/9, 2012 at 19:33

For reference, the test class from the paper is

public class TailRecursionTest { private static int loop(int i) { return loop(i); } public static void main(String[] args) { loop(0); } }

– Danidania 27/11, 2013 at 22:23

just link to webarchive web.archive.org/web/20120506085636/http://www.ibm.com/… – Anglesite 29/1, 2015 at 22:30

@Epigenous In principle, tail call optimization (TCO) can always be done: Just pop local variables and parameters from the stack, push parameters for the tail call, make sure you keep the return address, and JMP instead of JSR to the new function. You lose the caller's data on the stack, so exception traces become less informative, so not doing this can be justified as a conscious decision. Also, unfortunate implementation choices can prevent anything from being doable. – Shwalb 28/12, 2018 at 10:15

N

17

Perhaps you know this already, but the feature is not as trivial as it may sound since the Java language actually exposes the stack trace to the programmer.

Consider the following program:

public class Test {

    public static String f() {
        String s = Math.random() > .5 ? f() : g();
        return s;
    }

    public static String g() {
        if (Math.random() > .9) {
            StackTraceElement[] ste = new Throwable().getStackTrace();
            return ste[ste.length / 2].getMethodName();
        }
        return f();
    }

    public static void main(String[] args) {
        System.out.println(f());
    }
}

Even though this has a "tail-call" it may not be optimized. (If it is optimized, it still requires book-keeping of the entire call-stack since the semantics of the program relies on it.)

Basically, this means that it's hard to support this while still being backward compatible.

Nalor answered 7/9, 2010 at 14:9 Comment(14)

Solution is easy. Keep a flag for functions that finger their stack (like g), and do not tailcall optimize any that call them. – Diurnal 7/9, 2010 at 14:28

Found the mistake in your thought: "requires book-keeping of the entire call-stack since the semantics of the program relies on it". :-) It's like the new "suppressed Exceptions". Programs relying on such things are bound to break. In my opinion the behavior of the program is absolutely correct: Throwing away stack frames is the thing tail calls are all about. – Altimetry 7/9, 2010 at 14:30

@Marco, but just about any method could throw an exception, from which the entire call-stack is bound to be available, right? Besides, you can't decide in advance which methods will indirectly call g in this case... think about polymorphism and reflection for instance. – Nalor 7/9, 2010 at 14:37

@soc, I'm not quite sure I follow you. What is suppressed exceptions? – Nalor 7/9, 2010 at 14:37

It is a side-effect caused by the addition of ARM in Java 7. It is an example that you can't rely on such things you showed above. – Altimetry 7/9, 2010 at 14:52

@soc, Just because some new features breaks some backward-compatibility, doesn't mean that it doesn't make any difference if other features breaks backward compatibility too... No, there is no mistake in my answer. The fact that the stack-trace is exposed in the API poses a problem for (soft) tail-call recursion and is one (of many) reasons why such feature is troublesome to add. – Nalor 8/9, 2010 at 8:2

It does not break, because there is nothing to be broken. There is no promise that stacktraces don't change and they do change from time to time (as I have shown above). Anyone relying on a certain stacktrace format is just wrong. – Altimetry 8/9, 2010 at 14:25

Fortunately, Sun is not as lunatic as you guys are. Behavior comparability is very important. Language spec is not everything. – Tapster 8/9, 2010 at 18:42

@irreputable: Look at the facts before calling other people lunatic. hint ARM in Java 7. – Altimetry 9/9, 2010 at 9:59

@soc: "It is a side-effect caused by the addition of ARM in Java 7". Wow, that's really interesting. – Pelaga 23/2, 2011 at 14:0

"the fact that the language exposes the call-stack makes it hard to implement this": does the language require that the stack-trace returned by getStackTrace() from a method x() that the source code shows is called from a method y() also shows that x() was called from y()? Becasue if there is some freedom there is no real issue. – Antibiotic 21/10, 2011 at 11:53

This is merely a matter of wording the spec of a single method, from "gives you all stack frames" to "gives you all active stackframes, leaving out the ones obsoleted by tail calls". Furthermore, one could make it a command line switch or a system property whether tail-call is honoured. – Bhatt 14/3, 2013 at 15:27

This does not preclude proper tail calls. An faster alternative implementation (compared to re-using the current stack frame) performs the call as normal, but allows garbage collection of uneccessary stack frames later on. – Motoring 3/4, 2015 at 19:17

How would the runtime figure out whether a stack frame is unnecessary? – Nalor 3/4, 2015 at 20:0

B

12

Java is the least functional language you could possibly imagine (well, OK, perhaps not!) but this would be a great advantage for JVM languages, like Scala, which are.

My observations are that making the JVM a platform for other languages has never seemed to be at the top of the priority list for Sun and I guess, now for Oracle.

Battat answered 1/9, 2010 at 9:11 Comment(6)

@Thorbjørn - I wrote a program to predict whether any given program would halt in a finite amount of time. It took me ages! – Battat 1/9, 2010 at 11:11

The first BASICs I used didn't have functions, but rather GOSUB and RETURN. I don't think LOLCODE is very functional, either (and you can take that in two senses). – Penitential 1/9, 2010 at 18:30

@David, functional != has functions. – Guberniya 1/9, 2010 at 18:54

@Thorbjørn Ravn Andersen: No, but it is kind of a prerequisite, wouldn't you say? – Penitential 1/9, 2010 at 19:24

OP didn't use the word Java, just JVM. – Diurnal 7/9, 2010 at 14:26

"making the JVM a platform for other languages has never seemed to be at the top of the priority list for Sun". They put considerably more effort into making the JVM a platform for dynamic languages than they did for functional languages. – Pelaga 23/2, 2011 at 14:56

C

0

It's not a Java problem... it's one of the JVM. Java is just the grand-grand-ol'-pa of JVM languages.

Making a TCO is jumping to the next Stack Frame while deleting the current one, in between the running program and current stack calling vars should be somewhere else... ;)

The best way would be to have a new special call opcode for a jump-call in other frames that makes the stuff. They already did that for the virtual call. Not really a problem in interpretation, JIT perhaps rises other problems, and the JVM is bloated enough.

In Java or other languages, as there no proper TCO, the other way is trampolining, but it adds a lot of code. Or using specific exceptions, but it messes a lot. And it is in your code, but not in others' libraries...

Ah! If Rich Hickey added a (recur...) stuff (it's not a function), it's because of lack of real TCO, he doesn't want people to think there was one. He could very easily make an automatic TCO in an internal tail call. It also helps to detect bad tail calls that are not in tail position.

There's also a (trampoline...) stuff for external TCO, but it's messy (as a trampoline), and is quite not used except in awful stack situations.

But yes, a lot of VM manage TCO. I've heard that CLR will. I've even seen a paying JVM that manages it (a time ago, don't remember...)

Trampolining example in js: https://codeinjavascript.com/2020/06/13/tail-call-optimization-tco/

An old Thesis on TCO on HotSpot VM with Frame overwrite: https://ssw.jku.at/Research/Papers/Schwaighofer09Master/schwaighofer09master.pdf

Cogitation answered 4/3, 2021 at 12:5 Comment(0)

Recommended topics

Hot tags