Scala:可变与不可变对象性能-OutOfMemoryError [英] Scala: Mutable vs. Immutable Object Performance - OutOfMemoryError

问题描述

我想比较Scala中immutable.Map和mutable.Map的性能特征，以进行类似的操作(即，将许多地图合并为一个地图.请参见解决方案

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

 受保护的def addEntry(e:条目){val h = index(elemHashCode(e.key))e.next = table(h).asInstanceOf [Entry]表(h)= etableSize = tableSize + 1如果(tableSize>阈值)调整大小(2 * table.length)} 

在 resize 行中看到 2 * 吗?可变的 HashMap 会在每次空间用尽时增加一倍，而不变的则在内存使用方面非常保守(尽管现有的密钥在更新时通常会占用两倍的空间).

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

您可能希望使用投影，这样可以避免这种情况.不幸的是，投影是基于 Stream 的，对于我们在Scala 2.7.x上的用途而言，这不是很可靠.不过，请尝试以下方法:

(m <-listOfMaps.projection; kv <-m)的

 产生kv 

Stream 直到需要时才计算值.只要您不引用 Stream 的头部(在您的算法中就是这种情况)，垃圾收集器也应该收集未使用的元素.

编辑

作为补充，for/yield理解将获取一个或多个集合并返回一个新集合.在合理的情况下，返回的集合与原始集合的类型相同.因此，例如，在下面的代码中，要理解的内容将创建一个新列表，然后将其存储在 l2 中.创建新列表的不是 val l2 = ，而是理解.

  val l = List(1,2,3)val l2 =对于(e <-l)产量e * 2 

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

 (Map [A​​，B]()/:(对于(m<-listOfMaps; kv< -m)产生kv)) 

foldLeft 运算符(此处以其/:代名词编写)将在由理解返回的对象上调用.请记住，运算符末尾的:会反转对象和参数的顺序.

现在，让我们考虑一下这是什么对象，在其上调用 foldLeft .这种理解的第一个生成器是 m<-listOfMaps .我们知道 listOfMaps 是List [X]类型的集合，其中X在这里实际上并不相关.对 List 的理解结果始终是另一个 List .其他生成器无关.

因此，您获取此 List ，获取每个 Map 内的所有键/值，该Map/code是此 List 的组成部分，然后进行具有所有这些的新 List .这就是为什么您要复制所有内容的原因.

(实际上，这甚至更糟，因为每个生成器都会创建一个新集合；第二个生成器创建的集合只是 listOfMaps 的每个元素的大小，并且使用后立即被丢弃)

下一个问题-实际上是第一个问题，但更容易将答案取反-是 projection 的使用有何帮助.

在 List 上调用 projection 时，它将返回类型为 Stream 的新对象(在Scala 2.7.x上).起初，您可能会认为这只会使情况变得更糟，因为现在您将拥有 List 的三个副本，而不是一个副本.但是 Stream 并未预先计算.它是懒惰计算的.

这意味着生成的对象 Stream 不是 List 的副本，而是可用于计算的函数 Stream (如果需要).计算后，结果将保留下来，因此无需再次计算.

另外， Stream 的 map ， flatMap 和 filter 都返回一个新的 Stream ，这意味着您可以将它们链接在一起，而无需复制创建它们的 List 的单个副本.由于对 yield 的理解使用了这些功能，因此在内部使用 Stream 可以防止不必要的数据复制.

现在，假设您编写了这样的内容:

  val kvs = for(m<-listOfMaps.projection; kv< -m)产生kv(Map [A​​，B]()/:kvs){...} 

在这种情况下，您什么都得不到.将 Stream 分配给 kvs 后，数据尚未被复制.不过，一旦执行了第二行，kvs将计算出其每个元素，因此将保存数据的完整副本.

现在考虑原始形式::

 (Map [A​​，B]()/:(对于(m<-listOfMaps.projection; kv< -m)产生kv)) 

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

 覆盖最终的def foldLeft [B](z:B)(f:(B，A)=> B):B = {如果(isEmpty)z否则tail.foldLeft(f(z，head))(f)} 

如果 Stream 为空，则只需返回累加器即可.否则，计算一个新的累加器( f(z，head))，然后将其和函数传递给 Stream 的 tail ./p>

一旦执行了 f(z，head)，就不会剩下对 head 的引用.换句话说，程序中的任何地方都不会指向 Stream 的 head ，这意味着垃圾回收器可以收集它，从而释放内存./p>

最终结果是，由理解产生的每个元素都会短暂存在，而您可以使用它来计算累加器.这就是节省保存整个数据副本的方式.

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

I wanted to compare the performance characteristics of immutable.Map and mutable.Map in Scala for a similar operation (namely, merging many maps into a single one. See this question). I have what appear to be similar implementations for both mutable and immutable maps (see below).

As a test, I generated a List containing 1,000,000 single-item Map[Int, Int] and passed this list into the functions I was testing. With sufficient memory, the results were unsurprising: ~1200ms for mutable.Map, ~1800ms for immutable.Map, and ~750ms for an imperative implementation using mutable.Map -- not sure what accounts for the huge difference there, but feel free to comment on that, too.

What did surprise me a bit, perhaps because I'm being a bit thick, is that with the default run configuration in IntelliJ 8.1, both mutable implementations hit an OutOfMemoryError, but the immutable collection did not. The immutable test did run to completion, but it did so very slowly -- it takes about 28 seconds. When I increased the max JVM memory (to about 200MB, not sure where the threshold is), I got the results above.

Anyway, here's what I really want to know:

Why do the mutable implementations run out of memory, but the immutable implementation does not? I suspect that the immutable version allows the garbage collector to run and free up memory before the mutable implementations do -- and all of those garbage collections explain the slowness of the immutable low-memory run -- but I'd like a more detailed explanation than that.

Implementations below. (Note: I don't claim that these are the best implementations possible. Feel free to suggest improvements.)

  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
  }

解决方案

Well, it really depends on what the actual type of Map you are using. Probably HashMap. Now, mutable structures like that gain performance by pre-allocating memory it expects to use. You are joining one million maps, so the final map is bound to be somewhat big. Let's see how these key/values get added:

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) 
} 

See the 2 * in the resize line? The mutable HashMap grows by doubling each time it runs out of space, while the immutable one is pretty conservative in memory usage (though existing keys will usually occupy twice the space when updated).

Now, as for other performance problems, you are creating a list of keys and values in the first two versions. That means that, before you join any maps, you already have each Tuple2 (the key/value pairs) in memory twice! Plus the overhead of List, which is small, but we are talking about more than one million elements times the overhead.

You may want to use a projection, which avoids that. Unfortunately, projection is based on Stream, which isn't very reliable for our purposes on Scala 2.7.x. Still, try this instead:

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

A Stream doesn't compute a value until it is needed. The garbage collector ought to collect the unused elements as well, as long as you don't keep a reference to the Stream's head, which seems to be the case in your algorithm.

EDIT

Complementing, a for/yield comprehension takes one or more collections and return a new collection. As often as it makes sense, the returning collection is of the same type as the original collection. So, for example, in the following code, the for-comprehension creates a new list, which is then stored inside l2. It is not val l2 = which creates the new list, but the for-comprehension.

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

Now, let's look at the code being used in the first two algorithms (minus the mutable keyword):

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

The foldLeft operator, here written with its /: synonymous, will be invoked on the object returned by the for-comprehension. Remember that a : at the end of an operator inverts the order of the object and the parameters.

Now, let's consider what object is this, on which foldLeft is being called. The first generator in this for-comprehension is m <- listOfMaps. We know that listOfMaps is a collection of type List[X], where X isn't really relevant here. The result of a for-comprehension on a List is always another List. The other generators aren't relevant.

So, you take this List, get all the key/values inside each Map which is a component of this List, and make a new List with all of that. That's why you are duplicating everything you have.

(in fact, it's even worse than that, because each generator creates a new collection; the collections created by the second generator are just the size of each element of listOfMaps though, and are immediately discarded after use)

The next question -- actually, the first one, but it was easier to invert the answer -- is how the use of projection helps.

When you call projection on a List, it returns new object, of type Stream (on Scala 2.7.x). At first you may think this will only make things worse, because you'll now have three copies of the List, instead of a single one. But a Stream is not pre-computed. It is lazily computed.

What that means is that the resulting object, the Stream, isn't a copy of the List, but, rather, a function that can be used to compute the Stream when required. Once computed, the result will be kept so that it doesn't need to be computed again.

Also, map, flatMap and filter of a Stream all return a new Stream, which means you can chain them all together without making a single copy of the List which created them. Since for-comprehensions with yield use these very functions, the use of Stream inside the prevent unnecessary copies of data.

Now, suppose you wrote something like this:

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

In this case you aren't gaining anything. After assigning the Stream to kvs, the data hasn't been copied yet. Once the second line is executed, though, kvs will have computed each of its elements, and, therefore, will hold a complete copy of the data.

Now consider the original form::

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

In this case, the Stream is used at the same time it is computed. Let's briefly look at how foldLeft for a Stream is defined:

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

If the Stream is empty, just return the accumulator. Otherwise, compute a new accumulator (f(z, head)) and then pass it and the function to the tail of the Stream.

Once f(z, head) has executed, though, there will be no remaining reference to the head. Or, in other words, nothing anywhere in the program will be pointing to the head of the Stream, and that means the garbage collector can collect it, thus freeing memory.

The end result is that each element produced by the for-comprehension will exist just briefly, while you use it to compute the accumulator. And this is how you save keeping a copy of your whole data.

Finally, there is the question of why the third algorithm does not benefit from it. Well, the third algorithm does not use yield, so no copy of any data whatsoever is being made. In this case, using projection only adds an indirection layer.

这篇关于Scala:可变与不可变对象性能-OutOfMemoryError的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！