スカラ：不変オブジェクト性能対変更可能な - のOutOfMemoryError

Question

私は（つまり、単一のものに多くのマップをマージ同様の操作のためのScalaでimmutable.Mapとmutable.Mapの性能特性を比較したかった。<のhref = "https://stackoverflow.com/questionsを参照してください。 / 1262741 /スカラ座-方法・ツー・マージ・コレクション・オブ・マップ ">この質問の）。私は可変と不変マップ（下記参照）の両方で同様の実装のように見えるものを持っています。

試験として、私は1,000,000単一アイテムマップ[INT、のInt]を含むリストを生成し、私がテストした関数にこのリストを渡します。そこに大きな違いを占めているかわから、それに気軽ない - 〜mutable.Mapを使用して不可欠な実装のための750ms mutable.Mapについて〜1200ms、immutable.Mapについて〜1800ms、および：十分なメモリを使用すると、結果は驚くましたあまりにも、それについてはコメントしています。

私は少し厚めのものだせいか、私には少し驚きました何、IntelliJの8.1のデフォルトの実行構成、で変更可能な実装の両方が、OutOfMemoryErrorが発生を打つが、不変コレクションがなかったということです。不変のテストが完了するまで実行さでしたが、それはとてもゆっくりやった - それは約28秒かかります。私は、最大JVMのメモリを増加させた場合には（200メガバイト程度に、しきい値がどこにあるかわからない）、私が得た上記の結果ます。

とにかく、ここで私が本当に知りたいものです。

？

のなぜ変更可能な実装では、メモリが不足するが、不変の実装にはないんの私は不変のバージョンは、ガベージコレクタが実行され、変更可能な実装を行う前に、メモリを解放することを可能にすると思われます - それらのガベージコレクションの全ては不変低メモリの実行の遅さを説明する - 私はそれよりも詳細な説明が欲しい。

。

以下の実装。 （注：。。私は、これらが最良の実装が可能であることを主張しない改善点を提案する自由を感じる）

  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

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.