/*
*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内部其实是维护了一个
<span style="font-size: medium;">/**
* The value is used for character storage.
*/
char value[];</span>而数组是无法扩容的,所以当数组空间不够的时候,将会创建一个更大的数组,然后把原来数组的数据全部都拷贝到新的数组中:
<span style="font-size: medium;">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);
}</span>接着再把新的数据追加到到新的char数组的后面.
<span style="font-size: medium;">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;
}
</span>其实这里有两个考虑:
1.如果算单次扩容,那么确实这里的代价会比较大.
2.如果算在整个StringBuilder的生命周期中,那么这个扩容操作只占整个生命周期的一小部分.
它的理论基础就是均摊理论,也就是说如过把这次扩容操作所消耗的代价平均分配到每次对这个StringBuilder的操作上,那么这个平均下来的代价的增长是微小的.
如果听到ahuaxuan上面山寨的解释不足以让你理解的话, 那这里再引用一下书上的原话来解释一下均摊的问题:
当然,同样的问题也会出现在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
