performance - Scala:可变对象与不可变对象(immutable对象)性能 - OutOfMemoryError

Question

我想在scala中比较不可变的.map和可变的.map的性能特征，以便进行类似的操作（即将多个映射合并为一个映射）。请参见）。对于可变映射和不可变映射，我有类似的实现（见下文）。
作为一个测试，我生成了一个包含1000000个单项映射[int，int]的列表，并将这个列表传递到我测试的函数中。有了足够的内存，结果就不足为奇了：对于mutable.map，大约1200毫秒；对于unmutable.map，大约1800毫秒；对于使用mutable.map的命令式实现，大约750毫秒；map——不确定是什么造成了巨大的差异，但也可以对此发表评论。
让我有点吃惊的是，也许因为我有点厚，在Intellij8.1中使用默认的运行配置时，两个可变的实现都遇到了内存不足错误，但不可变的集合没有。不变的测试确实运行到了完成，但它运行得非常缓慢——大约需要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

嗯，这真的取决于你使用的地图的实际类型。可能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的开销，这是很小的，但是我们讨论的是超过一百万个元素乘以开销。
您可能希望使用投影，这样可以避免这种情况。不幸的是，投影基于scala 2.7.x上的Stream，这对于我们的目的来说不是很可靠。但是，请尝试以下方法：

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

在需要某个值之前，Stream不会计算该值。垃圾收集器也应该收集未使用的元素，只要您不保留对Stream头的引用，这在您的算法中似乎是如此。
编辑
作为补充，for/yield理解需要一个或多个集合并返回一个新集合。只要有意义，返回的集合与原始集合具有相同的类型。例如，在下面的代码中，for construction创建了一个新列表，然后将其存储在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是类型列表[x]的集合，其中x在这里并不真正相关。对一个理解的结果总是另一个理解的结果。其他发电机不相关。
所以，你取这个，得到每个listOfMaps中的所有键/值，它是这个List的一个组成部分，然后用所有这些创建一个新的List。这就是为什么你要复制你所有的东西。
（事实上，这甚至比这更糟，因为每个生成器都创建了一个新的集合；第二个生成器创建的集合只是每个元素的大小，虽然小于cc>但在使用后会立即丢弃）
下一个问题——实际上，第一个问题，但更容易颠倒答案——是使用List有何帮助。
当您在Map上调用List时，它将返回类型为List的新对象（在scala 2.7.x上）。起初，您可能认为这只会使事情变得更糟，因为现在您将拥有三份listOfMaps而不是一份。但aprojection不是预先计算的。它是懒散计算的。
这意味着生成的对象，即projection不是List的副本，而是一个可以在需要时用来计算Stream的函数。计算后，结果将保留，这样就不需要再次计算。
另外，List、Stream和Streamof aListall返回一个新的Stream，这意味着您可以将它们链接在一起，而无需制作创建它们的map的单个副本。因为对于理解flatMap使用这些功能，所以在内部使用filter可以防止不必要的数据复制。
现在，假设你写了这样的东西：

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

在这种情况下，你什么也得不到。将Stream分配给Stream后，数据尚未被复制。不过，一旦执行了第二行，KVS将计算出它的每个元素，因此，它将保存数据的完整副本。
现在考虑一下原始形式：

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

在这种情况下，在计算List的同时使用它。让我们简单地看看如何定义yieldfor aStream

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

如果Stream为空，只需返回蓄能器。否则，计算一个新的累加器（kvs），然后将它和函数传递给Stream的foldLeft。
但是，一旦执行了Stream之后，就不会有任何对Stream的引用了。或者，换句话说，程序中的任何地方都不会指向f(z, head)的tail，这意味着垃圾收集器可以收集它，从而释放内存。
最终的结果是，for-understruction生成的每个元素在您使用它计算累加器时只会短暂地存在。这就是保存整个数据副本的方法。
最后，还有一个问题，为什么第三种算法不能从中受益。好吧，第三种算法不使用Stream，因此没有任何数据的副本。在这种情况下，使用f(z, head)只会添加一个间接层。