您的位置: 首页  >  文章  >  List.subList方法导致的StackOverflowError

List.subList方法导致的StackOverflowError

分类: 文章 • 2024-08-06 08:28:46

0x1.异常概览

java.lang.StackOverflowError
java.util.AbstractList$SubAbstractList.listIterator(AbstractList.java:308)
java.util.AbstractList$SubAbstractList.listIterator(AbstractList.java:308)
......
java.util.AbstractList$SubAbstractList.listIterator(AbstractList.java:308)
java.util.AbstractList$SubAbstractList.listIterator(AbstractList.java:308)
java.util.AbstractList$SubAbstractList.iterator(AbstractList.java:301)
java.util.AbstractCollection.toArrayList(AbstractCollection.java:349)
java.util.AbstractCollection.toArray(AbstractCollection.java:339)
java.util.Collections.sort(Collections.java:1863)

此crash只出现于Android 4.4及以下系统（<=JDK 6），而5.0（>=JDK 7）及以上版本系统未出现。

0x2.分析与解决

1)由于是特定系统版本bug，故上androidxref查看对应系统版本源码。（Android 4.4）
2)再观崩溃堆栈，Collections.sort(Collections.java:1863)方法中，会调用List.toArray方法再进行排序。Collections.sort如下：
List.subList方法导致的StackOverflowError
Question：直观上看代码，mNewCommingUsersTemp是一个ArrayList，ArrayList自己实现了toArray，不应该走到AbstractCollection.toArray(AbstractCollection.java:339)，而且StackOverflow是由于AbstractList$SubAbstractList.listIterator(AbstractList.java:308)递归调用发生的。
Answer：所以可以肯定mNewCommingUsersTemp的引用指向应该从ArrayList对象变为了一个实现了List接口的其他对象。mNewCommingUsersTemp重新赋值就这一句：mNewCommingUsersTemp = mNewCommingUsersTemp.subList(0, NEW_COMMING_LIST_MAX_SIZE)，所以基本锁定到subList的锅了。
3)关于subList方法。
mNewCommingUsersTemp一开始是个ArrayList对象，所以去找找源码中的subList方法，发现ArrayList并没有subList方法，在其父类AbstractList中找到了实现。
List.subList方法导致的StackOverflowError
也就是每次subList方法都会新建个SubAbstractList对象，而它的实现方式是，引用父list，并记录sub的位置而已：
List.subList方法导致的StackOverflowError

所以多次subList的过程是，sub多少次，就有多少个SubAbstractList对象：
ArrayList --> SubAbstractList A --> SubAbstractList B --> SubAbstractList C --> …
4)Collections.sort为何崩溃
再次回到错误堆栈，AbstractList$SubAbstractList.listIterator(AbstractList.java:308)产生了递归调用，实现如下：
List.subList方法导致的StackOverflowError
fullList就是SubAbstractList的parent，所以迭代SubAbstractList C时，自然要从SubAbstractList C --> SubAbstractList B --> SubAbstractList A --> ArrayList 进行迭代
5)解决方案
mNewCommingUsersTemp = mNewCommingUsersTemp.subList(0, NEW_COMMING_LIST_MAX_SIZE);
更改为
mNewCommingUsersTemp = new ArrayList<>(mNewCommingUsersTemp.subList(0, NEW_COMMING_LIST_MAX_SIZE));
将SubList转换为ArrayList，避免多次sub导致递归的问题。

0x3.思考与拓展

1)Android 5.0 以上(>=JDK 7)为什么不崩溃？
JDK 7以上的ArrayList重新实现了AbstractList的subList方法，依旧会产生新的SubList对象。
List.subList方法导致的StackOverflowError

但是ArrayList自己实现了一套SubList，未再使用AbstractListSubAbstractList。而ArrayListSubAbstractList。 而ArrayListSubListListIterator几乎重新实现，listIterator方法不同于AbstractListListIterator几乎重新实现，listIterator方法不同于AbstractListSubAbstractList$SubAbstractListIterator，不会再递归，故不回Stack Overflow。源码节选如下：
List.subList方法导致的StackOverflowError

2)JDK 7 ArrayList$SubList.remove方法如下：
List.subList方法导致的StackOverflowError

JDK 6 AbstractList$SubAbstractList.remove方法如下：
List.subList方法导致的StackOverflowError
两方法实现基本相同，都会调用parent进行向上递归，是否会Stack Overflow？
答案：是的。
写Demo（循环）进行验证：
List.subList方法导致的StackOverflowError
一加5T Android 8：当栈达到8M时，会Stack Overflow，而此时深度大约90000次。如果1秒2次subList，需要10个多小时才能达到这个深度。
索尼Z1 Android 4.4：深度大约500次，就会Stack Overflow。
所以，高JDK版本可能对方法堆栈机制进行了重新设计。
虽然高JDK版本很难崩溃，但有个隐患，深度越深，SubList对象进行add、remove时会越来越耗时，导致应用卡顿！

相关推荐