内存充裕下的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

 

评论

1 楼 annegu 2010-05-19  

写的真好！原来从来没考虑过这些～