2008-05-31
两段java代码的比较
关键字: 递归 oom第一个程序：
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和堆栈溢出的阴影将笼罩着你。
- 17:36
- 浏览 (426)
- 论坛浏览 (7492)
- 评论 (27)
- 分类: java
- 相关推荐
评论
在我的电脑上，第二个示例正常结束。
java -version
java version "1.5.0_13"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0_13-b05-237)
Java HotSpot(TM) Client VM (build 1.5.0_13-119, mixed mode, sharing)
java -version
java version "1.5.0_13"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0_13-b05-237)
Java HotSpot(TM) Client VM (build 1.5.0_13-119, mixed mode, sharing)
faithyacht
2008-06-05
回复
我觉得编译器对这个优化置之不理还是很有道理的。
像这种线性的累加当然可以for或while循环,但是当碰到一棵时, 不用递归用while或for循环怎么来完成呢?
用一个while再一个栈来完成, 那也是递归啊!
用一个while再一个栈来完成, 那也是递归啊!
dennis_zane 写道
leelj 写道
import java.util.ArrayList;
import java.util.List;
public class TailRecursionTest {
public static void main(String[] args) {
TailRecursionTest t = new TailRecursionTest();
t.a(0);
}
public void a(int j) {
System.out.println(j);
j++;
if (j<10000) //if (j!=10000) 也可以
return;
List list = new ArrayList<Integer>(100000);
a(j);
}
}
递归 ，学习，以上我把if条件小改动了下，可以成功，不知道怎么解释：）
无语了，0<10000，一次还没跑完。
^_^ 有意思
dennis_zane
2008-06-05
回复
leelj 写道
import java.util.ArrayList;
import java.util.List;
public class TailRecursionTest {
public static void main(String[] args) {
TailRecursionTest t = new TailRecursionTest();
t.a(0);
}
public void a(int j) {
System.out.println(j);
j++;
if (j<10000) //if (j!=10000) 也可以
return;
List list = new ArrayList<Integer>(100000);
a(j);
}
}
递归 ，学习，以上我把if条件小改动了下，可以成功，不知道怎么解释：）
无语了，0<10000，一次还没跑完。
import java.util.ArrayList;
import java.util.List;
public class TailRecursionTest {
public static void main(String[] args) {
TailRecursionTest t = new TailRecursionTest();
t.a(0);
}
public void a(int j) {
System.out.println(j);
j++;
if (j<10000) //if (j!=10000) 也可以
return;
List list = new ArrayList<Integer>(100000);
a(j);
}
}
递归 ，学习，以上我把if条件小改动了下，可以成功，不知道怎么解释：）
dennis_zane
2008-06-05
回复
Lucas Lee 写道
一般来说没有大问题的。除非很大的递归。这个一般也可以当作性能问题考虑，不用太早考虑，更用不着把一切递归的方法都改成循环。
嗯，这仅仅是对OOM问题的分析做多一种设想。
sailor_sky
2008-06-03
回复
以前遇到过这种问题, 最后还是改成循环调用解决的 ,
kenan161621
2008-06-03
回复
楼上的楼上的代码好长
我以前写的递归基本上没有创建大的对象，所以没有碰到此问题，今天楼主提出来了，以后恐怕得多注意了
我以前写的递归基本上没有创建大的对象，所以没有碰到此问题，今天楼主提出来了，以后恐怕得多注意了
俺这个递归运行良好，如果从root object开始执行（一个XML的root element），大约100多个对象实例
package byd.biz;
import javax.ejb.Stateless;
import java.lang.reflect.Field;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.util.ArrayList;
import java.util.List;
import java.util.logging.Level;
import java.util.logging.Logger;
import javax.ejb.TransactionAttribute;
import javax.ejb.TransactionAttributeType;
import javax.persistence.EntityManager;
import javax.persistence.PersistenceContext;
/**
*
* @author ll258583
*/
@Stateless(name = "xoServiceBean")
public class xoServiceBean implements xoServiceLocal {
@PersistenceContext(unitName = "xoServicePU")
private EntityManager em;
/**
* Set JAXB object's value to the EntityBean object
* @param jxo
* @param eto
*/
@TransactionAttribute(TransactionAttributeType.REQUIRES_NEW)
public void x2o(Object jxo, Object eto) {
System.out.println("------------------------------------------------------------------");
System.out.println(eto.getClass().getName());
//validate if two papramater are matchable
if (eto.getClass().getPackage().getName().equals("byd.entity") && jxo.getClass().getPackage().getName().equals("byd.xoMapping.pip4A3") && eto.getClass().getName().substring(12).equals(jxo.getClass().getName().substring(21))) {
Field[] etoDeclaredFields = eto.getClass().getDeclaredFields();
Field[] jxoDeclaredFields = jxo.getClass().getDeclaredFields();
for (int i = 0; i < etoDeclaredFields.length; i++) {
for (int j = 0; j < jxoDeclaredFields.length; j++) {
Field etoField = etoDeclaredFields[i];
Class etoFieldType = etoField.getType();
String etoFieldName = etoField.getName();
Field jxoField = jxoDeclaredFields[j];
String jxoFieldName = jxoField.getName();
try {
if (etoFieldName.toLowerCase().equals(jxoFieldName.toLowerCase())) {
if (etoFieldType.getName().equals("java.lang.String")) {
//in case of basic type(java.lang.String) filed
System.out.println(etoFieldName + " : " + etoFieldType.getName());
Class<?>[] paras = null;
Object[] args = null;
Method jxoGetMethod = jxo.getClass().getDeclaredMethod("get" + jxoFieldName.substring(0, 1).toUpperCase() + jxoFieldName.substring(1), paras);
String value = (String) jxoGetMethod.invoke(jxo, args);
if (value != null) {
Method etoSetMethod = eto.getClass().getDeclaredMethod("set" + etoFieldName.substring(0, 1).toUpperCase() + etoFieldName.substring(1), etoFieldType);
etoSetMethod.invoke(eto, value);
} else {
System.out.println("STRING IS NULL");
}
} else if (etoFieldType.getName().equals("java.util.List")) {
//in case of java.util.List field
System.out.println(etoFieldName + " : " + etoFieldType.getName());
Class<?>[] paras = null;
Object[] args = null;
Method jxoGetMethod = jxo.getClass().getDeclaredMethod("get" + jxoFieldName.substring(0, 1).toUpperCase() + jxoFieldName.substring(1), paras);
Method etoGetMethod = eto.getClass().getDeclaredMethod("get" + etoFieldName.substring(0, 1).toUpperCase() + etoFieldName.substring(1), paras);
List jxoMemberList = (List) jxoGetMethod.invoke(jxo, args);
if (jxoMemberList.size() != 0 && jxoMemberList != null) {
List etoMemberList = (List) etoGetMethod.invoke(eto, args);
etoMemberList = new ArrayList();
for (Object jxm : jxoMemberList) {
Class C = Class.forName("byd.entity._" + jxm.getClass().getName().substring(21));
Object etm = C.newInstance();
this.x2o(jxm, etm);
etoMemberList.add(etm);
}
} else {
System.out.println("LIST IS EMPTY OR NULL");
}
} else if (etoFieldType.getName().equals("java.util.ArrayList")) {
//in case of java.util.ArrayList<String>() field
System.out.println(etoFieldName + " : " + etoFieldType.getName());
Class<?>[] paras = null;
Object[] args = null;
Method jxoGetList = jxo.getClass().getDeclaredMethod("get" + jxoFieldName.substring(0, 1).toUpperCase() + jxoFieldName.substring(1), paras);
List<String> stringList_1 = (List<String>) jxoGetList.invoke(jxo, args);
if (stringList_1 != null && stringList_1.size() != 0) {
Method etoGetList = eto.getClass().getDeclaredMethod("get" + etoFieldName.substring(0, 1).toUpperCase() + etoFieldName.substring(1), paras);
ArrayList stringList_2 = (ArrayList) etoGetList.invoke(eto, args);
stringList_2 = new ArrayList<String>();
for (String str_1 : stringList_1) {
String str_2 = new String(str_1);
stringList_2.add(str_2);
}
} else {
System.out.println("ArrayList<String> IS NULL OR EMPTY");
}
} else {
//in case of other class type field
System.out.println(etoFieldName + " : " + etoFieldType.getName());
Class<?>[] paras = null;
Object[] args = null;
Method jxoGetMethod = jxo.getClass().getDeclaredMethod("get" + jxoFieldName.substring(0, 1).toUpperCase() + jxoFieldName.substring(1), paras);
Object nextJxo = jxoGetMethod.invoke(jxo, args);
if (nextJxo != null) {
// Method etoGetMethod = eto.getClass().getDeclaredMethod("get" + etoFieldName.substring(0, 1).toUpperCase() + etoFieldName.substring(1), paras);
Method etoSetMethod = eto.getClass().getDeclaredMethod("set" + etoFieldName.substring(0, 1).toUpperCase() + etoFieldName.substring(1), etoFieldType);
Object nextEto = etoFieldType.newInstance();
etoSetMethod.invoke(eto, nextEto);
this.x2o(nextJxo, nextEto);
} else {
System.out.println(jxoFieldName + " IS NULL");
}
}
}
} catch (ClassNotFoundException ex) {
Logger.getLogger(xoServiceBean.class.getName()).log(Level.SEVERE, null, ex);
} catch (InstantiationException ex) {
Logger.getLogger(xoServiceBean.class.getName()).log(Level.SEVERE, null, ex);
} catch (IllegalAccessException ex) {
Logger.getLogger(xoServiceBean.class.getName()).log(Level.SEVERE, null, ex);
} catch (IllegalArgumentException ex) {
Logger.getLogger(xoServiceBean.class.getName()).log(Level.SEVERE, null, ex);
} catch (InvocationTargetException ex) {
Logger.getLogger(xoServiceBean.class.getName()).log(Level.SEVERE, null, ex);
} catch (NoSuchMethodException ex) {
Logger.getLogger(xoServiceBean.class.getName()).log(Level.SEVERE, null, ex);
} catch (SecurityException ex) {
Logger.getLogger(xoServiceBean.class.getName()).log(Level.SEVERE, null, ex);
}
}
}
} else {
// throw new UnmatchableException();
System.out.println("UnmatchableException");
}
//persist the entityBean object's value
System.out.println("Persist : " + eto.getClass().getName());
em.persist(eto);
}
/**
* Set EntityBean's value to the JAXB object
* @param eto
* @param jxo
*/
@TransactionAttribute(TransactionAttributeType.REQUIRES_NEW)
public void o2x(Object eto, Object jxo) {
System.out.println("------------------------------------------------------------------");
System.out.println(eto.getClass().getName());
//validate if two papramater are matchable
if (eto.getClass().getPackage().getName().equals("byd.entity") && jxo.getClass().getPackage().getName().equals("byd.xoMapping.pip4A3") && eto.getClass().getName().substring(12).equals(jxo.getClass().getName().substring(21))) {
Field[] etoDeclaredFields = eto.getClass().getDeclaredFields();
Field[] jxoDeclaredFields = jxo.getClass().getDeclaredFields();
for (int i = 0; i < jxoDeclaredFields.length; i++) {
for (int j = 0; j < etoDeclaredFields.length; j++) {
Field jxoField = jxoDeclaredFields[i];
String jxoFieldName = jxoField.getName();
Field etoField = jxoDeclaredFields[j];
String etoFieldName = etoField.getName();
try {
if (etoFieldName.toLowerCase().equals(jxoFieldName.toLowerCase())) {
if (jxoField.getType().getName().equals("java.lang.String")) {
//in case of basic type(java.lang.String) filed
System.out.println(jxoField.getName() + " : " + jxoField.getType().getName());
Class<?>[] paras = null;
Object[] args = null;
Method etoGet = eto.getClass().getDeclaredMethod("get" + etoFieldName.substring(0, 1).toUpperCase() + etoFieldName.substring(1), paras);
String value = (String) etoGet.invoke(eto, args);
if (value != null) {
Method jxoSet = jxo.getClass().getDeclaredMethod("set" + jxoFieldName.substring(0, 1).toUpperCase() + jxoFieldName.substring(1), jxoField.getType());
jxoSet.invoke(jxo, value);
} else {
System.out.println("STRING IS NULL");
}
} else if (jxoField.getType().getName().equals("java.util.List")) {
//in case of collection(java.util.List) field
System.out.println(jxoField.getName() + " : " + jxoField.getType().getName());
Class<?>[] paras = null;
Object[] args = null;
Method etoGetList = eto.getClass().getDeclaredMethod("get" + etoFieldName.substring(0, 1).toUpperCase() + etoFieldName.substring(1), paras);
List etoList = (List) etoGetList.invoke(eto, args);
if (etoList.size() != 0 && etoList != null) {
Method jxoGetList = jxo.getClass().getDeclaredMethod("get" + jxoFieldName.substring(0, 1).toUpperCase() + jxoFieldName.substring(1), paras);
List jxoList = (List) jxoGetList.invoke(jxo, args);
jxoList = new ArrayList();
for (Object etm : etoList) {
Class C = Class.forName("byd.xoMapping.pip4A3." + etm.getClass().getName().substring(12));
Object jxm = C.newInstance();
this.o2x(etm, jxm);
jxoList.add(jxm);
}
} else {
System.out.println("LIST IS NULL OR EMPTY");
}
} else if (etoField.getType().getName().equals("java.util.ArrayList")) {
//in case of ArrayList<String> field
System.out.println(jxoField.getName() + " : " + jxoField.getType().getName());
Class<?>[] paras = null;
Object[] args = null;
Method etoGetList = eto.getClass().getDeclaredMethod("get" + etoFieldName.substring(0, 1).toUpperCase() + etoFieldName.substring(1), paras);
ArrayList<String> stringList_1 = (ArrayList<String>) etoGetList.invoke(jxo, args);
if (stringList_1 != null && stringList_1.size() != 0) {
Method jxoGetList = jxo.getClass().getDeclaredMethod("get" + jxoFieldName.substring(0, 1).toUpperCase() + jxoFieldName.substring(1), paras);
List stringList_2 = (List) jxoGetList.invoke(jxo, args);
stringList_2 = new ArrayList<String>();
for (String str_1 : stringList_1) {
String str_2 = new String(str_1);
stringList_2.add(str_2);
}
} else {
System.out.println("ArrayList<String> IS NULL OR EMPTY");
}
} else {
//in case of other class type field
Class<?>[] paras = null;
Object[] args = null;
Object arg = null;
Method etoGet = eto.getClass().getDeclaredMethod("get" + etoFieldName.substring(0, 1).toUpperCase() + etoFieldName.substring(1), paras);
Object nextEto = etoGet.invoke(jxo, arg);
if (nextEto != null) {
Method jxoSet = jxo.getClass().getDeclaredMethod("set" + etoFieldName.substring(0, 1).toUpperCase() + etoFieldName.substring(1), jxoField.getType());
Object nextJxo = jxoField.getType().newInstance();
jxoSet.invoke(jxo, nextJxo);
this.o2x(nextEto, nextJxo);
} else {
System.out.println(etoFieldName + " IS NULL");
}
}
}
} catch (InstantiationException ex) {
Logger.getLogger(xoServiceBean.class.getName()).log(Level.SEVERE, null, ex);
} catch (IllegalAccessException ex) {
Logger.getLogger(xoServiceBean.class.getName()).log(Level.SEVERE, null, ex);
} catch (ClassNotFoundException ex) {
Logger.getLogger(xoServiceBean.class.getName()).log(Level.SEVERE, null, ex);
} catch (IllegalArgumentException ex) {
Logger.getLogger(xoServiceBean.class.getName()).log(Level.SEVERE, null, ex);
} catch (InvocationTargetException ex) {
Logger.getLogger(xoServiceBean.class.getName()).log(Level.SEVERE, null, ex);
} catch (NoSuchMethodException ex) {
Logger.getLogger(xoServiceBean.class.getName()).log(Level.SEVERE, null, ex);
} catch (SecurityException ex) {
Logger.getLogger(xoServiceBean.class.getName()).log(Level.SEVERE, null, ex);
}
}
}
} else {
// throw new UnmatchableException();
System.out.println("UnmatchableException");
}
}
}
Eastsun 写道
Java doesn't support this optimization for a number of reasons, including：
* the security model requires stack frame information
* reflection relies on "stack crawling"
* stack traces would be incomplete
* debugging would be problematic
* the security model requires stack frame information
* reflection relies on "stack crawling"
* stack traces would be incomplete
* debugging would be problematic
You have the points.
BTW: It seems FF3 RC1 is not well supported by JavaEye.
Java doesn't support this optimization for a number of reasons, including：
* the security model requires stack frame information
* reflection relies on "stack crawling"
* stack traces would be incomplete
* debugging would be problematic
* the security model requires stack frame information
* reflection relies on "stack crawling"
* stack traces would be incomplete
* debugging would be problematic
dennis_zane
最近加入圈子
最新评论
-
一封邮件
咋我没收到呢....
-- by yangzhihuan -
漂亮的代码
说得比较深.看的时候,觉得句句都正中心坎.看完之后,好像没啥收获.还是要自己试过 ...
-- by yangzhihuan -
广州opensource camp小记
貌似你那件open source camp的T-shirt背后很多广告滴说.
-- by yangzhihuan -
HDFS用户指南(翻译）
文章不错，有没有详细介绍安装PIG和使用PIG的文章呀！期待LZ的继续。。。。。
-- by LIMIMGJIE -
java package的设计原则
哈哈，dennis_zane 对程序设计很有心得嘛！ 学习了...
-- by zhao3546
评论排行榜