内存充裕下的OOM (二), StringBuilder和均摊分析

/*

  *author: ahuaxuan

  *date: 2010-05-14

  */

介绍:

在前面的一篇文章中http://ahuaxuan.iteye.com/blog/662629, ahuaxuan遇到了一个在内存相对充裕的情况下发生OOM的场景,具体的文章见:

然后时隔不久,该问题再次出现,但是出现在不同的场景下,现象有非常雷同之处.但是这次更离谱:

在某个他人的项目中, eden区还有300m空间的时候发生了OOM. 

而在前面一篇文章中,ahuaxuan揭示了在jackrabbit原有的搜索模块中出现的问题,其中主要的问题是大的char[]对象需要扩容的时候,虽然在这个项目中和lucene没有任何关系,但是问题表现出来的现象非常相似,不出意外的话,应该也是大的char[]或者byte[]达到极限所带来的问题. 思考一下,我们常见的char[]的应用有哪些, 无非就是StringBuilder,StringBuffer.

从他的日志来看,问题主要出现在StringBuilder的expandCapacity方法上,看到log里的expandCapacity, ahuaxuan马上知道问题所在了.(问题很简单,一说大家就都明白了,但是为了显示出我们的学问,我们也要适时的更加深入一点,不能这么草草了事,是吧,开个玩笑),我们知道StringBuilder内部其实是维护了一个

/**

     * The value is used for character storage.

     */

    char value[];

 

 

而数组是无法扩容的,所以当数组空间不够的时候,将会创建一个更大的数组,然后把原来数组的数据全部都拷贝到新的数组中:

void expandCapacity(int minimumCapacity) {

	int newCapacity = (value.length + 1) * 2;

        if (newCapacity < 0) {

            newCapacity = Integer.MAX_VALUE;

        } else if (minimumCapacity > newCapacity) {

	    newCapacity = minimumCapacity;

	}

        value = Arrays.copyOf(value, newCapacity);

    }

 

 

接着再把新的数据追加到到新的char数组的后面.

public AbstractStringBuilder append(char str[]) { 

	int newCount = count + str.length;

	if (newCount > value.length)

	    expandCapacity(newCount);

        System.arraycopy(str, 0, value, count, str.length);

        count = newCount;

        return this;

    }

 

 

原理很简单,这里也许你要问,这样是不是性能的消耗很大??

其实这里有两个考虑:

1.如果算单次扩容,那么确实这里的代价会比较大.

2.如果算在整个StringBuilder的生命周期中,那么这个扩容操作只占整个生命周期的一小部分.

它的理论基础就是均摊理论,也就是说如过把这次扩容操作所消耗的代价平均分配到每次对这个StringBuilder的操作上,那么这个平均下来的代价的增长是微小的.

如果听到ahuaxuan上面山寨的解释不足以让你理解的话, 那这里再引用一下书上的原话来解释一下均摊的问题:

写道

均摊分析是对一组操作的分析。特别是均摊分析允许处理这样一种情况， n个操作在最差情况下的代价小于任何一个操作在最差情况下的代价的n倍。均摊分析并不是把注意力集中到每个操作的单独代价，然后再把他们加起来，而是看到整个一组操作的代价，再把整体的代价分摊到每一个单独的操作上去。

 

 

 

当然,同样的问题也会出现在StringBuffer, ArrayList等等我们常见的类中.

下面我们来详细考量一下该理论在StringBuilder类的空间复杂度和时间复杂度. 假设我们有100个char需要放到一个stringbuilder中,根据它的实现,一共会有3次”扩容”, 并且有100次append操作, 假设一次”扩容”(建更大的数组,然后执行拷贝) , 假设扩容的时间消耗是m, append操作的时间消耗是n, 那么我们在这次StringBuilder的使用过程中,总的时间消耗是cost= (3*m + 100 * n) / 100. 而且m >> n. 所以我们在使用StringBuilder的过程中,要思考的是如何降低cost的值.当然降低3 * m是最好的, 但是对于m我们无能为力, 那么就对’3’下手把, 如果我们已知我们char的总数,我们就可以把这个3降下来,只要通过StringBuilder sb = new StringBuilder(100),这样就可以避免了3次扩容, 这样cost = (100 * n) / 100 = n. 

这时间问题是我们避免3次扩容的最佳理由么, 不是! 为什么,因为看上去 (3*m + 100 * n) / 100 并不比 n高到哪里去,所以在ahuaxuan的case中,性能并不是这样的差. 既然时间复杂度还不是最佳理由, 我们的目光自然而然的转到空间复杂度上.

其实刚才书上的均摊定义对于StringBuilder之类的实现来说只解释了时间复杂度的问题,但是并没有涉及到空间复杂度. 由于我们并不能直接操作内存的分配,所以在jvm中问题要显得更加神秘一点(一般的java程序远对于计算机科学的理解还是非常有待提高的).

继续上面一个case, 第一次扩容时, char[16]不够,重新新建了一个 char[(16+1)*2], 第二次扩容char[(34 + 1) * 2], 第三次扩容char[(70 + 1)*2].这个时候一共产生了4个数组对象, char[16], char[34], char[70], char[142].其实我们只是append了100个char而已,我们消耗的空间最大却有可能达到262个char.

        262个char还不至于消耗多少空间,因为我们只做了100次append, 如果我们有1000k的char呢.

我们来算一下时间的消耗和空间消耗.总的扩容次数为16(1000k个char的情况下)

时间消耗: (16 * m + 1000k * n )/1000k

空间消耗: 34 + 70 + ..... + 294910 + 589822 + 1179646 = 2359244

再整个操作的生命周期内总共会消耗2359244个char的空间,但是由于我们的gc作用,所以同一时刻,我们最大的消耗至少为 589822+ 1179646 = 1769468. 空间消耗几乎至少翻倍(为啥是至少? 因为前面创建的char[]如果还没有被回收,那么消耗的空间就会更大,最大的会达到 2359244个char.如果是多线程在做这样的事情,那么消耗的空间数还要乘以线程数,比如说原来一条线程这样的操作只浪费了一个2M, 但是100条线程其实就浪费了200M这样的空间) 

再深入考虑, 难道我们这样做只是增加了空间的消耗吗? 绝不是. 我们还可以从JVM的角度再来考虑一下这个问题. 前面15个char[]的创建,对于jvm的young区的拷贝算法来说也是个不必要的负担,因为如果我们有100个线程在做这个任务,同一时间可能产生15 * 100 = 1500个多余的对象.在gc的时候,这些对象需要mark, copy(前面临时的charp[]至少要copy一次,也就是说它们必须进入一次from or to space),其实在一些场景下,这种操作完全避免,避免的手段就是给StringBuilder一个合理的值.

如果你恰好看过我的第一篇”内存充裕下的OOM”,那么也不难理解在某些情况下(比如说200M以上的文本, 想象一下最后的一次扩容需要多少的申请多少的容量??)StringBuilder也会出现”内存充裕下的OOM”了.

相信看了ahuaxuan的这篇文章之后,在使用StringBuilder的时候你会更胸有成竹了. 同样,在使用ArrayList, StringBuffer, 还有HashMap(不但要数组翻倍,还要resize)之类的实现时也有同样的问题.

总结, 本文ahuaxuan主要解释了以下问题.

在StringBuilder之类的实现在扩容的时候, 带来的

       1. 时间消耗.

       2. 空间消耗.

       3. 对jvm的影响.

通过这几个方面的剖析可以让我们更好的使用java SDK中类似的实现类.写出性能更高,更健壮的代码.

      当然古人说授之以鱼不如授之以鱼, 事实上凡是以数组作为数据结构实现的类中,基本上都存在均摊的问题,同时也都存在对JVM有不必要影响的因素,所以需要大家更多的深入理解我们常用的类.

to be continue

 

评论

21 楼 ahuaxuan 2010-06-15  

找到了wiki上的解释:

http://en.wikipedia.org/wiki/Amortized_analysis

20 楼 ahuaxuan 2010-05-28  

C_J 写道

ahuaxuan 写道

C_J 写道

记错了，是2byte。
不是操作char的链表，当然操作是entry的

entry的问题我在12楼已经阐述过了, 100m会变成多少,你可以算一下的100M * 5,64位机上更加夸张了,所以用entry是行不通的

是否能行通，一看你内存开多大，二看如果处理这100M，用缓冲区的好处是既可以按照策略清理内存和分阶段处理。

当然你开一定大小数组大小，也是一样可以，只不过每次都开一定大小是缺乏灵活性的，需要采取一定策略能动态计算合适大小。

这不是内存开多大的问题, 在内存固定的情况下, 显然使用链表需要比使用char[]消耗5倍的空间, 而stringbuilder只有在扩容的时候才需要消耗2倍的空间, 而用链表,100m的数据要消耗500m的空间, 这个显然是不能用链表的,

我们再换个角度, 如果说可以使用链表, 请问你有没有见过用链表来组织char的这样的用法和数据结构

我们再换个角度, 如果用链表来组织char,那么我要把char换成string的时候, 需要什么操作,这一点也是考虑的重点.

从上面三个角度来考虑, 使用链接结构来存储char是不合适的, 而且事实证明也没有人这样做

19 楼 C_J 2010-05-27  

ahuaxuan 写道

C_J 写道

记错了，是2byte。
不是操作char的链表，当然操作是entry的

entry的问题我在12楼已经阐述过了, 100m会变成多少,你可以算一下的100M * 5,64位机上更加夸张了,所以用entry是行不通的

是否能行通，一看你内存开多大，二看如果处理这100M，用缓冲区的好处是既可以按照策略清理内存和分阶段处理。

当然你开一定大小数组大小，也是一样可以，只不过每次都开一定大小是缺乏灵活性的，需要采取一定策略能动态计算合适大小。

18 楼 ahuaxuan 2010-05-27  

C_J 写道

记错了，是2byte。
不是操作char的链表，当然操作是entry的

entry的问题我在12楼已经阐述过了, 100m会变成多少,你可以算一下的100M * 5,64位机上更加夸张了,所以用entry是行不通的

17 楼 C_J 2010-05-27  

记错了，是2byte。
不是操作char的链表，当然操作是entry的

16 楼 ahuaxuan 2010-05-27  

C_J 写道

ahuaxuan 写道

ray_linn 写道

tomyz0223 写道

基本上看完了，基本理解，扩容容易造成空间的浪费，唯一的问题是有时候合理的值很难确定，尤其你在你们项目中的场景，有的doc只有100K，有的有100M，这个情况就很难定出合理的值了，订的太大，造成空间浪费，太小，扩容，造成更大的空间浪费。

总得说来，不错的问题，可以搜集起来了，分析的非常透彻。

用链表罗。。。

这个场景下用链表会占更大的空间, 因为链表有pre和next引用,每个引用4bytes, 一个char才占两个byte的空间, 但加上引用的话,一个char要消耗10个bytes了, 还要加上包装对象占的一些空间, 内存使用又高了很多. 所以字符操作,或者byte操作,一般没有人用链表来实现对应的数据结构

这种情况应该用链表，只是带回收的链表结果，更专业的说是pool。
如果不需要一次性装入的话，就用缓冲，类似SAX解析XML文件。
如果需要一次性装入的话，就只能放入内存，但用完后回收内存，类似DOM解析XML文件。

另外你都要装一个100M的东西了，就不会在乎那一点点空间了，对了，JVM里char大小统一好像都是4字节，为了跨平台。

不才, 我还没有见过处理char的链表, 要不再详细说说?

一个char是几个byte其实你上网一查就知道了

15 楼 C_J 2010-05-27  

ahuaxuan 写道

ray_linn 写道

tomyz0223 写道

基本上看完了，基本理解，扩容容易造成空间的浪费，唯一的问题是有时候合理的值很难确定，尤其你在你们项目中的场景，有的doc只有100K，有的有100M，这个情况就很难定出合理的值了，订的太大，造成空间浪费，太小，扩容，造成更大的空间浪费。

总得说来，不错的问题，可以搜集起来了，分析的非常透彻。

用链表罗。。。

这个场景下用链表会占更大的空间, 因为链表有pre和next引用,每个引用4bytes, 一个char才占两个byte的空间, 但加上引用的话,一个char要消耗10个bytes了, 还要加上包装对象占的一些空间, 内存使用又高了很多. 所以字符操作,或者byte操作,一般没有人用链表来实现对应的数据结构

这种情况应该用链表，只是带回收的链表结果，更专业的说是pool。
如果不需要一次性装入的话，就用缓冲，类似SAX解析XML文件。
如果需要一次性装入的话，就只能放入内存，但用完后回收内存，类似DOM解析XML文件。

另外你都要装一个100M的东西了，就不会在乎那一点点空间了，对了，JVM里char大小统一好像都是4字节，为了跨平台。

14 楼 ahuaxuan 2010-05-27  

强强爱妍妍 写道

我的思路: 翻倍分配可以设置一个上限. 比如翻到长度超过10M了,下次就最多加上10M. 明显的每次都翻倍,到很大的值就不合理了.

是的, 翻倍的因子可以动态调整是最比较好的.
其实只要知道的了原理, 即使不写自己的StringBuilder也总是可以解决问题的. 关键是如果不知道原理, 有问题的代码就出来了.

13 楼 强强爱妍妍 2010-05-26  

我的思路: 翻倍分配可以设置一个上限. 比如翻到长度超过10M了,下次就最多加上10M. 明显的每次都翻倍,到很大的值就不合理了.

12 楼 ahuaxuan 2010-05-26  

ray_linn 写道

tomyz0223 写道

基本上看完了，基本理解，扩容容易造成空间的浪费，唯一的问题是有时候合理的值很难确定，尤其你在你们项目中的场景，有的doc只有100K，有的有100M，这个情况就很难定出合理的值了，订的太大，造成空间浪费，太小，扩容，造成更大的空间浪费。

总得说来，不错的问题，可以搜集起来了，分析的非常透彻。

用链表罗。。。

这个场景下用链表会占更大的空间, 因为链表有pre和next引用,每个引用4bytes, 一个char才占两个byte的空间, 但加上引用的话,一个char要消耗10个bytes了, 还要加上包装对象占的一些空间, 内存使用又高了很多. 所以字符操作,或者byte操作,一般没有人用链表来实现对应的数据结构

11 楼 ray_linn 2010-05-26  

tomyz0223 写道

基本上看完了，基本理解，扩容容易造成空间的浪费，唯一的问题是有时候合理的值很难确定，尤其你在你们项目中的场景，有的doc只有100K，有的有100M，这个情况就很难定出合理的值了，订的太大，造成空间浪费，太小，扩容，造成更大的空间浪费。

总得说来，不错的问题，可以搜集起来了，分析的非常透彻。

用链表罗。。。

10 楼 ahuaxuan 2010-05-24  

beneo 写道

gc一般不是paralledOld，是paralled. paralledOld能够在young,old两个带同时paralled收集，使用了这个参数后，eden会变得少一些，不也符合你的实际情况么？

newRatio 是我的笔误，应该是timeRatio，其实我的想法是那CPU换空间。

我表达的原意是一般我们在部署的时候都会选择paralledOld,并不是jvm默认是paralledOld

9 楼 beneo 2010-05-23  

ahuaxuan 写道

beneo 写道

我猜测如果再append(new String("xxx"))的时候，可能会又更好地效果

此外我觉得不一定gc只能用cms，还可以试试ParallelOld，或者NewRatio，好机器+好代码才行

谢谢你的回复, 但是你的回复中有两个错误
一, 不能用new String("xxx"), 谁都知道这个会产生多余的对象出来的阿. 你的意思应该是append(char[])是把, 但是没有用的, StringBuilder的扩容算法摆在那里阿.

二, 而且gc一般都是parallelOld, 只有响应速度要求非常高的应用需要cms, 而那个newRatio也不是gc算法.只是一个控制内存的分配比例的参数而已:

3.2 The Young Generation
The bigger the young generation the less minor GC's, but this implies a smaller tenured generation which increases the frequency of major collections.
You need to look at your application and determine how long your objects live for to tune this.
-XX:NewRatio=3 - the young generation will occupy 1/4 the overall heap
-XX:NewSize - Size of the young generation at JVM init. Calculated automatically if you specify -XX:NewRatio
-XX:MaxNewSize - The largest size the young generation can grow to (unlimited if this value is not specified at command line)

new String("xxx"),虽然产生了新的对象，但是的确避免了一些诸如split, subString这类方法的内存溢出，

gc一般不是paralledOld，是paralled. paralledOld能够在young,old两个带同时paralled收集，使用了这个参数后，eden会变得少一些，不也符合你的实际情况么？

newRatio 是我的笔误，应该是timeRatio，其实我的想法是那CPU换空间。

8 楼 ahuaxuan 2010-05-23  

beneo 写道

我猜测如果再append(new String("xxx"))的时候，可能会又更好地效果

此外我觉得不一定gc只能用cms，还可以试试ParallelOld，或者NewRatio，好机器+好代码才行

谢谢你的回复, 但是你的回复中有两个错误
一, 不能用new String("xxx"), 谁都知道这个会产生多余的对象出来的阿. 你的意思应该是append(char[])是把, 但是没有用的, StringBuilder的扩容算法摆在那里阿.

二, 而且gc一般都是parallelOld, 只有响应速度要求非常高的应用需要cms, 而那个newRatio也不是gc算法.只是一个控制内存的分配比例的参数而已:

3.2 The Young Generation
The bigger the young generation the less minor GC's, but this implies a smaller tenured generation which increases the frequency of major collections.
You need to look at your application and determine how long your objects live for to tune this.
-XX:NewRatio=3 - the young generation will occupy 1/4 the overall heap
-XX:NewSize - Size of the young generation at JVM init. Calculated automatically if you specify -XX:NewRatio
-XX:MaxNewSize - The largest size the young generation can grow to (unlimited if this value is not specified at command line)

7 楼 beneo 2010-05-22  

我猜测如果再append(new String("xxx"))的时候，可能会又更好地效果

此外我觉得不一定gc只能用cms，还可以试试ParallelOld，或者NewRatio，好机器+好代码才行

6 楼 diandian 2010-05-22  

写的不错，转走了

5 楼 ahuaxuan 2010-05-21  

tomyz0223 写道

好文章，排排版更好，不排版，我有点头痛。

好,有空我重新排一下, 排的不好也老是被人踩, 呵呵

4 楼 idealab 2010-05-21  

从JVM的角度讲解问题，这种解决问题的思路我喜欢。

3 楼 tomyz0223 2010-05-20  

基本上看完了，基本理解，扩容容易造成空间的浪费，唯一的问题是有时候合理的值很难确定，尤其你在你们项目中的场景，有的doc只有100K，有的有100M，这个情况就很难定出合理的值了，订的太大，造成空间浪费，太小，扩容，造成更大的空间浪费。

总得说来，不错的问题，可以搜集起来了，分析的非常透彻。

2 楼 tomyz0223 2010-05-20  

好文章，排排版更好，不排版，我有点头痛。