97

在dos-the-jvm-prevent-tail-call-optimizations两年后，似乎有一个原型 实现，并且MLVM已经将该功能列为“原型 80%”已有一段时间了。

Sun/Oracle 方面对支持尾调用没有积极的兴趣，还是只是尾调用“[...]注定要在每个功能优先级列表中排在第二位[...]”，正如JVM中提到的那样语言峰会？

如果有人测试了 MLVM 构建并且可以分享一些关于它工作得如何的印象（如果有的话），我会非常感兴趣。

更新： 请注意，像Avian这样的一些虚拟机支持正确的尾调用，没有任何问题。

4

5 回答 5

33

诊断 Java 代码：提高 Java 代码的性能( alt ) 解释了 JVM 不支持尾调用优化的原因。

但是，尽管众所周知如何将尾递归函数自动转换为简单循环，但 Java 规范并不要求进行这种转换。据推测，它不是必需的一个原因是，一般来说，不能在面向对象的语言中静态地进行转换。相反，从尾递归函数到简单循环的转换必须由 JIT 编译器动态完成。

然后给出了一个不会转换的 Java 代码示例。

因此，如清单 3 中的示例所示，我们不能期望静态编译器在保留语言语义的同时对 Java 代码执行尾递归转换。相反，我们必须依赖 JIT 的动态编译。根据 JVM，JIT 可能会也可能不会这样做。

然后它提供了一个测试，您可以使用它来确定您的 JIT 是否执行此操作。

当然，由于这是 IBM 论文，它包含一个插件：

我用几个 Java SDK 运行了这个程序，结果令人惊讶。在 Sun 的 Hotspot JVM 1.3 版上运行表明 Hotspot 不执行转换。在默认设置下，我的机器上的堆栈空间会在不到一秒的时间内用完。另一方面，IBM 的 1.3 版 JVM 正常运行，表明它确实以这种方式转换了代码。

于 2010-09-10T03:15:45.083 回答
32

我过去看到没有在 Java 中实现 TCO（并且被认为很困难）的一个原因是 JVM 中的权限模型是堆栈敏感的，因此尾调用必须处理安全方面的问题。

我相信 Clements 和 Felleisen [1] [2] 证明这不是一个障碍，我很确定问题中提到的 MLVM 补丁也可以处理它。

我意识到这并不能回答您的问题；只是添加有趣的信息。

  1. http://www.ccs.neu.edu/scheme/pubs/esop2003-cf.pdf
  2. http://www.ccs.neu.edu/scheme/pubs/cf-toplas04.pdf
于 2011-02-23T21:29:33.310 回答
15

也许您已经知道这一点，但该功能并不像听起来那么简单，因为 Java 语言实际上向程序员公开了堆栈跟踪。

考虑以下程序：

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());
    }
}

即使这有一个“尾调用”，它也可能没有被优化。（如果它被优化，它仍然需要记录整个调用堆栈，因为程序的语义依赖于它。）

基本上，这意味着在保持向后兼容的同时很难支持这一点。

于 2010-09-07T14:09:52.670 回答
13

Java 是您可以想象的功能最少的语言（好吧，好吧，也许不是！）但这对于 JVM 语言来说将是一个很大的优势，例如Scala。

我的观察是，让 JVM 成为其他语言的平台似乎从来都不是 Sun 的首要任务，我猜现在是 Oracle。

于 2010-09-01T09:11:45.903 回答
0

这不是 Java 问题……它是 JVM 之一。Java只是JVM语言的grand-grand-ol'-pa。

制作 TCO 是在删除当前堆栈帧的同时跳转到下一个堆栈帧，在正在运行的程序和当前堆栈调用 vars 之间应该在其他地方... ;)

最好的方法是在其他帧中为跳转调用创建一个新的特殊调用操作码，以实现这些东西。他们已经为虚拟通话做到了。解释不是问题，JIT 可能会引发其他问题，JVM 已经够臃肿了。

在Java或其他语言中，由于没有合适的TCO，另一种方式是蹦床，但它增加了很多代码。或者使用特定的例外，但这会造成很多麻烦。它在您的代码中，但不在其他人的库中......

啊! 如果 Rich Hickey 添加了（重复...）东西（它不是函数），那是因为缺乏真正的 TCO，他不希望人们认为有一个。他可以很容易地在内部追尾电话中进行自动 TCO。它还有助于检测不在尾部位置的不良尾部调用。

还有一个用于外部 TCO 的（蹦床......）东西，但它很乱（作为蹦床），并且除了在糟糕的堆栈情况下完全不使用。

但是，是的，很多 VM 管理 TCO。我听说CLR会。我什至见过一个付费的 JVM 来管理它（前段时间，不记得了……）

js中的蹦床示例：https ://codeinjavascript.com/2020/06/13/tail-call-optimization-tco/

一篇关于 HotSpot VM 上的 TCO 的旧论文，带有帧覆盖：https ://ssw.jku.at/Research/Papers/Schwaighofer09Master/schwaighofer09master.pdf

于 2021-03-04T12:05:36.950 回答