两段java代码的比较

第一个程序：

import java.util.ArrayList;
import java.util.List;

public class TailRecursionTest {
    public static void main(String[] args) {
        TailRecursionTest t = new TailRecursionTest();
        for (int i = 0; i < 10000; i++)
            t.a(0);
    }

    public void a(int j) {
        j++;
        List list = new ArrayList<Integer>(100000);
        // 对list进行处理
    }
}

 

    没啥特殊的，仅仅是为了测试，我们将a方法调用10000次，a方法创建一个有100000个元素的list的局部变量。
第二个程序：

 

import java.util.ArrayList;
import java.util.List;

public class TailRecursionTest2 {
    public static void main(String[] args) {
        TailRecursionTest2 t = new TailRecursionTest2();
        t.a(0);
    }

    public void a(int j) {
        System.out.println(j);
        j++;
        if (j == 10000)
            return;
        List list = new ArrayList<Integer>(100000);
        // 对list进行处理
        a(j);
    }
}

     也没啥特殊的，就是将循环换成了递归，a方法做的事情没变。两个都跑一下，程序1顺利结束，程序2出问题了，啥问题？如下：

161
162
163
164
165
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at java.util.ArrayList.<init>(Unknown Source)
    at TailRecursionTest2.a(TailRecursionTest2.java:17)
    at TailRecursionTest2.a(TailRecursionTest2.java:20)
    at TailRecursionTest2.a(TailRecursionTest2.java:20)
    at TailRecursionTest2.a(TailRecursionTest2.java:20)
    at TailRecursionTest2.a(TailRecursionTest2.java:20)

    我倒，才运行166次了，heap就满了。问题在哪呢？oh,yep，你肯定想到了，是不是重复创建list这个大集合引起的呢？它不是局部变量吗？怎么 也会溢出？是的，list是局部变量，在a的方法栈里引用着，指向heap上的大对象，更关键的问题在于，java是没有尾递归优化的，递归方法是不会使 用同一个栈帧，每一次递归调用，都将压入新的栈帧，并且这个栈帧上又new了一个list变量，引用着heap上新的一个大集合。随着栈深度的增加， jvm里维持着一条长长的方法调用轨迹以便你能回来，在方法没有返回之前，这些list变量一直被各自的栈帧引用着，不能被GC，你说，能不OOM吗？

    也许，你想到了个补救方法来挽救程序2，就是每次在处理完list后，我把它设置为null，不让栈帧继续引用着它，咱编写对gc友好的代码，这不就行了，试试：

import java.util.ArrayList;
import java.util.List;

public class TailRecursionTest2 {
    public static void main(String[] args) {
        TailRecursionTest2 t = new TailRecursionTest2();
        t.a(0);
    }

    public void a(int j) {
        System.out.println(j);
        j++;
        if (j == 10000)
            return;
        List list = new ArrayList<Integer>(100000);
        // 对list进行处理
        list = null;  //gc友好
        a(j);
    }
}

 

    得意洋洋，我跑一下看看，这次跑到4000多次，但是：

......
4289
4290
4291
4292
java.lang.StackOverflowError
    at sun.nio.cs.ext.DoubleByteEncoder.encodeArrayLoop(Unknown Source)
    at sun.nio.cs.ext.DoubleByteEncoder.encodeLoop(Unknown Source)
    at java.nio.charset.CharsetEncoder.encode(Unknown Source)

 

    没办法啊，人家sun的jdk就是不支持尾递归优化(据说传闻在jdk5的某个版本是有尾递归优化的），很不给你面子的栈溢出了。ibm的jdk据说支持尾递归优化，上面这个程序在ibm的jdk上可能可以正常结束，未经测试。

总结：在java里，递归最好咱还是别用，老老实实地while、for；就算递归了，最好递归方法不要new太大的对象，除非你能确定递归的深度不是那么大，否则OOM和堆栈溢出的阴影将笼罩着你。

评论

7 楼 dennis_zane 2008-06-01  

Eastsun 写道

  JDK不做尾部递归优化是有他的道理的。
  如果采用递归优化，显然有两条途径：
  1.在静态编译阶段做该优化。
　　　这样做的后果就是导致编译后的class字节码的语义发生了改变。就是从class文件反编译得不到原来的源代码了。
　2.在JIT阶段做该优化。
　　　这样可以避免编译过程中代码语义的变化。
　　　但会有其他问题，比较易见的一个是：如果在递归的某一层该方法抛出了一个异常，显然没做优化之前的堆栈轨迹与优化之后的堆栈轨迹是不一样的。
　　再比如下面这段代码：

public class TailRecursionTest {

  private static int loop(int i) {
    return loop(i);
  }

  public static void main(String[] args) {
    loop(0);
  }
}

尾部优化之后应该是：

public class TailRecursionTest {

  private static int loop(int i) {
    while (true) {
    }
  }

  public static void main(String[] args) {
    loop(0);
  }
}

显然两段代码运行的结果不一样了：第一段会导致堆栈溢出，而第二段能一直运行下去。

1、你说的第一点，貌似sun在jdk1.4还是1.5的编译器可以做尾递归优化，我一个同事那时候还做过测试，通过javap观察是通过invokedynamic指令实现的，现在用1.6再看，编译后的指令已经改成了invokestatic，去掉了尾递归优化。就语义的改变而言，我不认为有那么重要？需要反编译的场景很多吗？
2、嗯，这是个问题，可能在debug查错上做出误导。
就你举的代码例子，如果有尾递归优化，第一个程序不会堆栈溢出，行为其实跟程序2是一致的，尽管结构不一样。
楼上说在jdk6上程序2是可以正常的结束，可以证明ibm的jdk6是支持尾递归优化的，不知道是编译期优化，还是jit优化？又是基于何种考虑允许这种优化？

6 楼 devworks 2008-05-31  

第二个在ibm jdk 1.6.0正常结束

5 楼 Eastsun 2008-05-31  

http://bugs.sun.com./bugdatabase/view_bug.do?bug_id=4726340
这个bug是2002年提出的，讲的就是这件事。

4 楼 Eastsun 2008-05-31  

dennis_zane 写道

    没办法啊，人家sun的jdk就是不支持尾递归优化(据说传闻在jdk5的某个版本是有尾递归优化的），很不给你面子的栈溢出了。ibm的jdk据说支持尾递归优化，上面这个程序在ibm的jdk上可能可以正常结束，未经测试。

总结：在java里，递归最好咱还是别用，老老实实地while、for；就算递归了，最好递归方法不要new太大的对象，除非你能确定递归的深度不是那么大，否则OOM和堆栈溢出的阴影将笼罩着你。

  JDK不做尾部递归优化是有他的道理的。
  如果采用递归优化，显然有两条途径：
  1.在静态编译阶段做该优化。
　　　这样做的后果就是导致编译后的class字节码的语义发生了改变。就是从class文件反编译得不到原来的源代码了。
　2.在JIT阶段做该优化。
　　　这样可以避免编译过程中代码语义的变化。
　　　但会有其他问题，比较易见的一个是：如果在递归的某一层该方法抛出了一个异常，显然没做优化之前的堆栈轨迹与优化之后的堆栈轨迹是不一样的。
　　再比如下面这段代码：

public class TailRecursionTest {

  private static int loop(int i) {
    return loop(i);
  }

  public static void main(String[] args) {
    loop(0);
  }
}

尾部优化之后应该是：

public class TailRecursionTest {

  private static int loop(int i) {
    while (true) {
    }
  }

  public static void main(String[] args) {
    loop(0);
  }
}

显然两段代码运行的结果不一样了：第一段会导致堆栈溢出，而第二段能一直运行下去。

3 楼 nihongye 2008-05-31  

没细看，sorry,好像可以通过xss参数，支持更深的递归调用

2 楼 dennis_zane 2008-05-31  

nihongye 写道

引用

# java.lang.StackOverflowError 
#     at sun.nio.cs.ext.DoubleByteEncoder.encodeArrayLoop(Unknown Source) 
#     at sun.nio.cs.ext.DoubleByteEncoder.encodeLoop(Unknown Source) 
#     at java.nio.charset.CharsetEncoder.encode(Unknown Source) 

文章很好，但是最后面的错误面显是堆栈溢出吖，又不是oom

是丫，我说了是堆栈溢出了 结论再改下。

1 楼 nihongye 2008-05-31  

引用

# java.lang.StackOverflowError 
#     at sun.nio.cs.ext.DoubleByteEncoder.encodeArrayLoop(Unknown Source) 
#     at sun.nio.cs.ext.DoubleByteEncoder.encodeLoop(Unknown Source) 
#     at java.nio.charset.CharsetEncoder.encode(Unknown Source) 

文章很好，但是最后面的错误面显是堆栈溢出吖，又不是oom