scala雾中风景(20): MutableList迭代器的bug

上一篇,这个问题还没完,泽斌给出这个问题是因另一个问题引发的:Scala 的 for each,为什么会有且仅有一次 recursion? 引用原问题:

Scala 2.10/2.11 中,运行

val l = MutableList(16)

for (i<-l) {
    val p = i/2
    if (!(l contains p)) { 
        l += p 
    }
}

l

得到的是

MutableList[Int](16, 8, 4)

如果是返回 (16, 8)(如同 JavaScript 或 PHP)的话我能理解。或者是返回 (16, 8, 4, 2, 1, 0)(如同 Python 或 Ruby) 我也能够理解。但是返回 (16, 8, 4) 是为什么呢?

这得看看MutableList的迭代器实现了, 它在scala.collection.LinearSeqOptimized里面:

override /*IterableLike*/
def foreach[B](f: A => B) {
    var these = this
    while (!these.isEmpty) {
      f(these.head)
      these = these.tail
    }
}

不太容易直接看出来这块的问题,断点的时候发现这里会导致调试器在展示值时调用toString引起异常,我是复制了一份MutableList的代码在foreach里增加一些打印信息发现的。

我们在repl下模拟这个迭代过程,刚开始foreach的时候元素只有1个,对16进行处理,追加一个新元素8:

scala> val l = scala.collection.mutable.MutableList(16)
l: scala.collection.mutable.MutableList[Int] = MutableList(16)

scala> l += 8
res0: l.type = MutableList(16, 8)

这个追加的行为对应foreach里面的f(these.head)这一句,之后把指针指向后续链表节点:

scala> var these = l.tail
these: scala.collection.mutable.MutableList[Int] = MutableList(8)

因为刚开始var these=this,所以这次these=these.tail会得到链表的第二个元素8,然后传入8,原链表又被追加了一个元素4:

scala> l += 4
res1: l.type = MutableList(16, 8, 4)

接着继续移动指针,但这次these对象已经不是this而是单节点链表,取它的tail会得到空,导致foreach终止。所以最终原链表里有3个元素:

scala> these = these.tail
these: scala.collection.mutable.MutableList[Int] = MutableList()

虽然,这里的these与原链表是复用的,它size虽然为0,但实际可以访问后续元素:

scala> these(0)
res3: Int = 4

我觉得应该算是MutableList迭代器的bug了,它不应该使用LinearSeqOptimized里的实现,那个里面的逻辑没有考虑到集合长度可变的情况。

scala雾中风景(19): MutableList与mutable.LinkedList的问题

群里看到的问题:

scala> import scala.collection._

scala> val l = mutable.MutableList(1,2)
l: scala.collection.mutable.MutableList[Int] = MutableList(1, 2)

scala> val t = l.tail
t: scala.collection.mutable.MutableList[Int] = MutableList(2)

scala>  l += 3
res0: l.type = MutableList(1, 2, 3)

scala> t.length
res1: Int = 1

这里显示 t 的长度没有问题,但显示t的值的时候,却不是预期的:

scala> t
res2: scala.collection.mutable.MutableList[Int] = MutableList(2, 3)

怎么把l列表后来增加的3也给包含进去了。这要看这个MutableListtail方法的实现是怎么回事了。

scala.collection.mutable.MutableList里为了实现scala.collection.GenTraversableLike特质里的head, tail等方法,是通过链表scala.collection.mutable.LinkedList来存储数据。它的tail方法实现如下:

override def tail: MutableList[A] = {
    val tl = new MutableList[A]
    tailImpl(tl)
    tl
}

// this method must be private for binary compatibility
private final def tailImpl(tl: MutableList[A]) {
    require(nonEmpty, "tail of empty list")
    tl.first0 = first0.tail
    tl.len = len - 1
    tl.last0 = if (tl.len == 0) tl.first0 else last0
}

这里面要看看 tl.first0 = first0.tail 的实现是什么,在LinkedListLike里:

override def tail: This = {
    require(nonEmpty, "tail of empty list")
    next
}

它直接返回当前链表的下一个节点引用。所以当原链表末尾附加新的值时,这个 tl 链表也是可以引用到的,因为它们是复用的。

不过因为对这个tl的len设置过了,所以迭代的时候,并不会越界。并且toString方法也不会多展示不属于它的数据的:

scala> t.toString
res14: String = MutableList(2)

scala> t.foreach(print)
2

但在repl的展示上,就没有做的很严谨了,它没有调用这个对象的toString来展示它的值,而是自己把这个节点及链表后续节点的值都展示了:

scala> t
res15: scala.collection.mutable.MutableList[Int] = MutableList(2, 3)

这应该算是repl展示层面的不严谨吧。不过MutableList的实现也不太严谨,这个t虽然length是1,但后边节点如果有值的话也是可以索引到的:

scala> t(0)
res17: Int = 2

scala> t(1)
res18: Int = 3

scala> l += 4
res19: l.type = MutableList(1, 2, 3, 4)

scala> t(2)
res20: Int = 4

这也算是一个陷阱吧,mutable的集合在使用的时候要清楚它的场景和限制。

通过List.apply方法构造List的背后逻辑

通过List伴生对象的apply方法来创建实例: List("A","B") 过程发生了什么

首先,List伴生对象的apply方法接收的是一个可变参数列表,即数组:

override def apply[A](xs: A*): List[A] = xs.toList

而我们传入的Array("A","B")数组会被隐式转换为 WrappedArray 的子类型,这是在LowPriorityImplicits里定义的:

// Since the JVM thinks arrays are covariant, one 0-length Array[AnyRef]
// is as good as another for all T <: AnyRef.  Instead of creating 100,000,000
// unique ones by way of this implicit, let's share one.

implicit def wrapRefArray[T <: AnyRef](xs: Array[T]): WrappedArray[T] = {
    if (xs eq null) null
    else if (xs.length == 0) WrappedArray.empty[T]
    else new WrappedArray.ofRef[T](xs)
}

随后对这个WrappedArray 的子类型ofRef[String]类型,调用 toList 方法

不过在进行toList时用到了隐式参数CanBuildFrom,我们先看一下List伴生对象中定义的,用于生成CanBuildFrom信息的隐式方法:

/** $genericCanBuildFromInfo */
implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, List[A]] =
    ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]]

现在来追踪toList的执行过程,在父类TraversableOncetoList方法里调用了to方法,而这个to方法里有声明一个隐式参数。

用隐式参数CanBuildFrom构造了一个List类型的容器,把数据填充进去,再返回result

里面的隐式参数:

implicit cbf: CanBuildFrom[Nothing, A, Col[A @uV]] 

先不用管里面难懂的类型参数,编译在寻找对应的隐式参数值时,通过上面的 to[List]声明的目标类型是List,所以从List的伴生对象中去寻找,通过 canBuildFrom隐式函数得到了需要的参数,它是把一个可复用的对象造型成我们需要的CBF类型:

ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]]

ReusableCBF的意思是可复用的CanBuildFrom,它在 GenTraversableFactory里定义:

通过这个CBF隐式参数帮我们构造了一个新的容器,然后把当前集合里的数据放进去,最后再调用新容器的result来得到List

通过断点,发现 b.result 时进入了 ListBuffer.toList 的代码里,也就是说这个隐式参数构造出来的新容器类型是 ListBuffer 的子类型。

最终,它返回ListBuffer类里的start成员,这个start是一个 :: 类型(List的子类)

不正当使用HashMap导致cpu 100%的问题追究

因最近hashmap误用引起的死循环又发生了一些案例,左耳朵浩子写了一篇blog 疫苗:Java HashMap的死循环,看了一下,大家的分析如出一辙。这篇blog也是好几年前写的了,之前在平台技术部的博客上贴过,随着组织结构的调整,那个博客可能不再维护,把这篇文章在这儿也保存一下。

李鹏同学在blog里写了篇关于HashMap死锁模拟的文章: http://blog.csdn.net/madding/archive/2010/08/25/5838477.aspx 做个纠正,那个不是死锁问题,而是死循环。

这个问题,我们以前讨论过。 校长之前的博客和淘宝的毕玄的《分布式Java应用:基础与实践》一书中都提到过 velocity导致cpu 100% 的bug,起因是HashMap的使用不当所致。

在之前的邮件列表里,校长提出过这个问题,当时我没仔细看,不清楚这个问题究竟是对 HashMap的误用,还是HashMap的潜在问题, 当时感觉不太可能是HashMap自身的问题,否则问题大了。应该是属于在并发的场景下错误的 使用了HashMap。昨天看了李鹏的blog后,觉得这个事情还是应该搞清楚一下;虽然我推测是链表形成闭环,但 没有去证明过。从网上找了一下: http://blog.csdn.net/autoinspired/archive/2008/07/16/2662290.aspx 里面也有提到:

产生这个死循环的根源在于对一个未保护的共享变量 — 一个”HashMap”数据结构的操作。当在 所有操作的方法上加了”synchronized”后,一切恢复了正常。检查”HashMap”(Java SE 5.0)的源 码,我们发现有潜在的破坏其内部结构最终造成死循环的可能。在下面的代码中,如果我们使得 HashMap中的entries进入循环,那 么”e.next()”永远都不会为null。
不仅get()方法会这样,put()以及其他对外暴露的方法都会有这个风险,这算jvm的bug吗?应该说不是的,这个现象很早以前就报告出来了(详细见: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6423457)。Sun的工程师并不认为这 是bug,而是建议在这样的场景下应用”ConcurrentHashMap”,在构建可扩展的系统时应将这点 纳入规范中。

这篇翻译提到了对HashMap的误用,但它没有点破HashMap内部结构在什么样误用情况下怎么被 破坏的;我想要一个有力的场景来弄清楚。再从李鹏的blog来看,用了2个线程来put就模拟出来了,最后堆栈是在 transfer 方法上(该方法是数据扩容时将数据从旧容器转移到新容器)。 仔细分析了一下里面的代码,基本得出了原因,证明了我之前的推测。

假设扩容时的一个场景如下(右边的容器是一个长度 2 倍于当前容器的数组) 单线程情况。

我们分析数据转移的过程,主要是链表的转移。

执行过一次后的状态:

最终的结果:

两个线程并发情况下,扩容时可能会创建出 2 个新数组容器

顺利的话,最终转移完可能是这样的结果

但并发情况下,出现死循环的可能场景是什么呢? 还要详细的分析一下代码,下面的代码中重点在 do/while 循环结构中(完成链 表的转移)。

// 扩容操作,从一个数组转移到另一个数组
void transfer(Entry[] newTable) { 
    Entry[] src = table;
    int newCapacity = newTable.length; 
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j]; 
        if (e != null) {
            src[j] = null; 
            do {
                Entry<K,V> next = e.next; //假设第一个线程执行到这里 
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null); // 可能导致死循环
        }
    }
}

2 个线程并发情况下, 当线程 1 执行到上面第 9 行时,而线程 2 已经完成了一 轮 do/while 操作,那么它的状态如下图:
(上面的数组时线程 1 的,已经完成了链表数据的转移;下面的是线程 2 的,它 即将开始进行对链表数据的转移,此时它记录 E1 和 E2 的首位已经被线程 1 翻 转了)

后续的步骤如下:

1) 插入 E1 节点,E1 节点的 next 指向新容器索引位置上的值(null 或 entry)

2) 插入 E2 节点,E2 的 next 指向当前索引位置上的引用值 E1

3)因为 next 不为 null,链表继续移动,此时 2 节点之间形成了闭环。造成了 死循环。

上面只是一种情况,造成单线程死循环,双核 cpu 的话占用率是 50%,还有导致 100%的情况,应该也都是链表的闭环所致。

最终,这并不是 HashMap 的问题,是使用场景的不当,在并发情况下选择非线程 安全的容器是没有保障的。

相关阅读:深入剖析ConcurrentHashMap(1)深入剖析ConcurrentHashMap(2)