拉斯卡拉：可变对不可改变的对象的性能-OutOfMemoryError

Question

我想比较的性能特征的不可改变的。地图和可变的。地图在卡拉一个类似的工作(即，许多地图合并成一个单一的。看看 这个问题).我有什么出现类似的实现对于这两种可变和不可改变地图(见下文)。

作为一个测试，我产生的一个列表，其中包含1,000,000个单个项目的地[Int,Int]，并通过了这个名单成的职能是我的测试。有足够的存储器，结果并不令人吃惊的:~1200毫秒用于可变的。地图，~1800ms为不可改变的。地图，并~750ms为一个必要实施使用可变的。地图-不确定什么样的账户的巨大差异，但是随时评论这一点。

什么让我感到吃惊的一点，也许是因为我有点厚，是，与默认的运行配置架构来达成8.1，既可实现打OutOfMemoryError，但不可改变的集合，也没有。不可变的试验有没有运行，以完成，但它这样做非常缓慢--这需要大约28秒钟。当我增加了max 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

好吧，这真的取决于什么样的实际类型的地图使用。大概 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 增长通过增加一倍，每次它跑出来的空间，而不可改变的一个是很保守的存储器的使用(虽然现有的钥匙通常会占有两次空间时更新)。

现在，作为对其他性问题，创建一个列表中的关键和价值中的前两个版本。这意味着，在你加入任何地图，你已经有每 Tuple2 (key/value pairs)在存储器两次！外加开销 List, ，这是很小的，但我们谈论的是超过一百万元素时代的开销。

你可能需要使用投影，这可以避免的。不幸的是，预测的依据是 Stream, ，这并不是非常可靠我们的目的，上卡拉2.7.x.仍然，试试这个代替：

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

一个 Stream 不计算价值，直到它是必要的。垃圾收集器应该收集未使用的元素，因为只要你不保持一个参考 Stream's头，这似乎是这种情况在你的算法。

编辑

补充，用/收益率的理解，需要一个或多个集合和返回的一个新的集合。因为它往往是有道理的，回返的收藏是相同的类型作为原始的集合。因此，例如，以下代码，对于理解创建一个新的名单，然后将其存储内 l2.它不是 val l2 = 创造新名单，但是对的理解。

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 操作员，这里写它的 /: 同义词，将调用于返回的对象为理解。记得一个 : 在结束一个操作者颠倒了目的和参数。

现在，让我们考虑什么样的对象是这样的，在哪 foldLeft 被称为。第一次发生在这个理解是 m <- listOfMaps.我们知道 listOfMaps 是的集合类型列出[X]，其中X是不是真的有关在这里。结果一个用于理解上的 List 总是另一个 List.其他的发电机是不相关的。

那么，你拿着这个 List, ，获得所有关键/价值观的内部每 Map 这是一个组成部分 List, ，并作出新的 List 与所有这一切。这就是为什么你是重复你拥有的一切。

(事实上，它甚至更糟糕的是，因为每个发电机创造了一个新的收集；该集创建的第二个发电机只是大小的每一个元素 listOfMaps 虽然，并立即废弃使用之后)

下一个问题--实际上，第一位的，但它是更容易转化的答案--如何使用 projection 帮助。

当你打电话 projection 上 List, 它返回新对象的类型 Stream (在卡拉2.7.x)。在第一个你可能会认为这只会让事情更糟糕的是，因为你现在有三个副本 List, ，而不是一个单一的。但一个 Stream 不是预先计算。它是 懒洋洋地 计算。

这意味着什么的是，由此产生的对象， Stream, 不是复制的 List, ，而是一个功能，可以用来计算的 Stream 当要求。一旦计算，结果将被保留，因此，它不需要计算一次。

此外， map, flatMap 和 filter 的 Stream 所有返回一个新的 Stream, 这意味着你可以把它们都在一起而不做出一个单的副本 List 这创造了他们。由于为解析与 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, 和这意味着垃圾收集器可以收集，因此释放的记忆。

最终的结果是，每个元素的产生过于理解，将存在只是简单地说，当你用它来计算的累加器。这是你如何保存保持一份你的整个数据。

最后，还有为什么问题的第三算法并不能从中受益。好了，第三算法不使用 yield, ，因此没有副本的任何数据的任何正在取得进展。在这种情况下，使用 projection 只增添了一个间接层。