Scala:可变对象与不可变对象性能 - OutOfMemoryError

Question

我想比较Scala中的immutable.Map和mutable.Map的性能特征,以进行类似的操作(即将许多映射合并为一个映射.请参阅此问题).我有可变和不可变映射的类似实现(见下文).

作为测试,我生成了一个包含1,000,000单项Map [Int,Int]的List,并将此列表传递给我正在测试的函数.有了足够的内存,结果就不足为奇了:对于mutable.Map来说是~1200ms,对于immutable.Map来说是~1800ms,对于使用mutable.Map的命令式实现来说是~750ms - 不知道是什么导致了那里的巨大差异,但是随意对此也有评论.

让我感到惊讶的是,也许是因为我有点厚,是因为IntelliJ 8.1中的默认运行配置,两个可变实现都遇到了OutOfMemoryError,但是不可变集合没有.不可变测试确实完成了,但它的速度非常慢 - 大约需要28秒.当我增加最大JVM内存(大约200MB,不确定阈值在哪里)时,我得到了上面的结果.

无论如何,这是我真正想知道的:

为什么可变实现耗尽内存,但不可变实现却没有？ 我怀疑不可变版本允许垃圾收集器在可变实现之前运行并释放内存 - 并且所有这些垃圾收集都解释了不可变低内存运行的缓慢 - 但我想要更详细的解释比起那个来说.

以下实施.(注意:我并未声称这些是可能的最佳实现.请随意提出改进建议.)

  def mergeMaps[A,B](func: (B,B) => B)(listOfMaps: List[Map[A,B]]): Map[A,B] =
    (Map[A,B]() /: (for (m <- listOfMaps; kv <-m) yield kv)) { (acc, kv) =>
      acc + (if (acc.contains(kv._1)) kv._1 -> func(acc(kv._1), kv._2) else kv)
    }

  def mergeMutableMaps[A,B](func: (B,B) => B)(listOfMaps: List[mutable.Map[A,B]]): mutable.Map[A,B] =
    (mutable.Map[A,B]() /: (for (m <- listOfMaps; kv <- m) yield kv)) { (acc, kv) =>
      acc + (if (acc.contains(kv._1)) kv._1 -> func(acc(kv._1), kv._2) else kv)
    }

  def mergeMutableImperative[A,B](func: (B,B) => B)(listOfMaps: List[mutable.Map[A,B]]): mutable.Map[A,B] = {
    val toReturn = mutable.Map[A,B]()
    for (m <- listOfMaps; kv <- m) {
      if (toReturn contains kv._1) {
        toReturn(kv._1) = func(toReturn(kv._1), kv._2)
      } else {
        toReturn(kv._1) = kv._2
      }
    }
    toReturn
  }

Answer 1

嗯,这实际上取决于您使用的Map的实际类型.可能HashMap.现在,像这样的可变结构通过预先分配它期望使用的内存来获得性能.你加入了一百万张地图,所以最终的地图肯定会有点大.让我们看看如何添加这些键/值:

protected def addEntry(e: Entry) { 
  val h = index(elemHashCode(e.key)) 
  e.next = table(h).asInstanceOf[Entry] 
  table(h) = e 
  tableSize = tableSize + 1 
  if (tableSize > threshold) 
    resize(2 * table.length) 
} 

见2 *的resize线？HashMap每次空间耗尽时,mutable 增加一倍,而不可变的内存使用相当保守(尽管现有的密钥在更新时通常会占用两倍的空间).

现在,对于其他性能问题,您将在前两个版本中创建键和值列表.这意味着,在您加入任何地图之前,您已经Tuple2在内存中拥有了两次(键/值对)!加上开销List很小,但我们谈的是开销超过一百万个元素.

您可能想要使用投影,这可以避免这种情况.不幸的是,投影是基于Stream,对于我们在Scala 2.7.x上的目的而言,这不是很可靠.不过,请尝试这样做:

for (m <- listOfMaps.projection; kv <- m) yield kv

A Stream在需要之前不会计算值.垃圾收集器也应该收集未使用的元素,只要你不保留对Stream头部的引用,这在你的算法中似乎就是这种情况.

编辑

补充,for/yield理解需要一个或多个集合并返回一个新集合.通常有意义的是,返回的集合与原始集合的类型相同.因此,例如,在以下代码中,for-comprehension创建一个新列表,然后存储在其中l2.它不是val l2 =创建新列表,而是for-comprehension.

val l = List(1,2,3)
val l2 = for (e <- l) yield e*2

现在,让我们看一下前两个算法中使用的代码(减去mutable关键字):

(Map[A,B]() /: (for (m <- listOfMaps; kv <-m) yield kv)) 

foldLeft这里用/:同义词编写的运算符将在for-comprehension返回的对象上调用.请记住,:操作符末尾的a会反转对象和参数的顺序.

现在,让我们考虑一下这个foldLeft被调用的对象.这个理解中的第一个生成器是m <- listOfMaps.我们知道这listOfMaps是List [X]类型的集合,其中X在这里并不真正相关.理解a的结果List总是另一个List.其他发电机不相关.

所以,你拿这个List,获取每个中的所有键/值,Map这是其中的一个组成部分List,并List用所有这些创建一个新的.这就是为什么你要复制你拥有的一切.

(事实上,它甚至更糟,因为每个生成器创建一个新的集合;第二个生成器创建的集合只是每个元素的大小listOfMaps,并在使用后立即丢弃)

下一个问题 - 实际上,第一个问题,但更容易反驳答案 - 是如何使用projection帮助.

当你调用projectiona时List,它返回类型的新对象Stream(在Scala 2.7.x上).起初你可能认为这只会让事情变得更糟,因为你现在有三个副本List,而不是一个副本.但是a Stream不是预先计算的.这是懒惰的计算.

这意味着生成的对象,Stream不是List,而是一个可用于计算Stream何时需要的函数的副本.计算完成后,将保留结果,以便不需要再次计算.

此外,map,flatMap和filter的Stream所有返回一个新的Stream,这意味着你可以把它们结合在一起的所有未做的单个副本List产生它.由于for-comprehensions yield使用这些非常多的功能,使用Stream内部防止不必要的数据副本.

现在,假设你写了这样的东西:

val kvs = for (m <- listOfMaps.projection; kv <-m) yield kv
(Map[A,B]() /: kvs) { ... }

在这种情况下,你没有获得任何东西.分配Stream到后kvs,数据尚未复制.但是,一旦执行第二行,kvs将计算其每个元素,因此将保存数据的完整副本.

现在考虑原始形式::

(Map[A,B]() /: (for (m <- listOfMaps.projection; kv <-m) yield kv)) 

在这种情况下,在Stream计算它的同时使用它.让我们来简单看一下如何foldLeft对一个Stream定义:

override final def foldLeft[B](z: B)(f: (B, A) => B): B = { 
  if (isEmpty) z 
  else tail.foldLeft(f(z, head))(f) 
} 

如果Stream为空,则返回累加器.否则,计算新的储液器(f(z, head)),然后将其与功能传递给tail的Stream.

f(z, head)但是,一旦执行了,就没有剩余的参考head.或者,换句话说,没有在程序的任何位置将指向head的Stream,这意味着垃圾收集器可以收集它,从而释放内存.

最终结果是,for-comprehension生成的每个元素只是简单地存在,而你用它来计算累加器.这就是保存整个数据副本的方法.

最后,存在为什么第三种算法不能从中受益的问题.好吧,第三种算法不使用yield,因此不会复制任何数据.在这种情况下,projection仅使用添加间接层.