twitter/storehaus — pull request #117 by ryanlecompte (2013-06-01 02:42:42+00:00)
Title: Improve performance of pivotMap and combineMaps

The `CollectionOps.pivotMap` and `CollectionOps.combineMaps` methods both currently use `mapValues`, which unfortunately returns a lazy `view`. This means that each time you perform an operation on the returned lazy view, the closure will be re-evaluated. In the case of `pivotMap` and `combineMaps`, it's not desirable to recompute their operations. This pull request addresses that by replacing `mapValues` with `map` along with `scala.collection.breakOut`. I've micro-benchmarked the two new implementations here:

```scala
➜ ~ scala measure.scala
combineMaps: 1646
combineMaps w/ breakOut: 201
pivotMaps: 7120
pivotMaps w/ breakOut: 2329

CODE:

object Bench {
import scala.collection.breakOut

def main(args: Array[String]) {
def measure(f: => Unit): Long = { val t = System.currentTimeMillis; f; System.currentTimeMillis - t }

def combineMaps[K, V](m: Seq[Map[K, V]]): Map[K, Seq[V]] =
m.foldLeft(Map[K, List[V]]()) { (oldM, mkv) =>
mkv.foldLeft(oldM) { (seqm, kv) =>
seqm + (kv._1 -> (kv._2 :: seqm.getOrElse(kv._1, Nil)))
}
}.mapValues { _.reverse }

def combineMapsWithBreakout[K, V](m: Seq[Map[K, V]]): Map[K, Seq[V]] =
m.foldLeft(Map[K, List[V]]()) { (oldM, mkv) =>
mkv.foldLeft(oldM) { (seqm, kv) =>
seqm + (kv._1 -> (kv._2 :: seqm.getOrElse(kv._1, Nil)))
}
}.map { case (k, v) => k -> v.reverse }(breakOut)

def pivotMap[K, OuterK, InnerK, V](pairs: Map[K, V])(split: K => (OuterK, InnerK)): Map[OuterK, Map[InnerK, V]] =
pairs.toList.map {
case (k, v) =>
val (outerK, innerK) = split(k)
(outerK -> (innerK -> v))
}
.groupBy { _._1 }
.mapValues { _.map { _._2 }.toMap }

def pivotMapWithBreakout[K, OuterK, InnerK, V](pairs: Map[K, V])(split: K => (OuterK, InnerK)): Map[OuterK, Map[InnerK, V]] =
pairs.toList.map {
case (k, v) =>
val (outerK, innerK) = split(k)
(outerK -> (innerK -> v))
}
.groupBy { _._1 }
.map { case (k, v) => k -> v.map { _._2 }.toMap }(breakOut)

val m = Vector.tabulate(100000) { i => Map(1 -> i) }
val mm1 = combineMaps(m)
println("combineMaps: " + measure {
for (_ <- 0 to 1000) mm1.values.map { _.size }.sum
})

val mm2 = combineMapsWithBreakout(m)
println("combineMaps w/ breakOut: " + measure {
for (_ <- 0 to 1000) mm2.values.map { _.size }.sum
})

val map = Vector.tabulate(10000) { i => i -> i }.toMap
val pivoted1 = pivotMap(map) { k => (k, k) }
println("pivotMaps: " + measure {
for (_ <- 0 to 1000) pivoted1.values.map { _.size }.sum
})

val pivoted2 = pivotMapWithBreakout(map) { k => (k, k) }
println("pivotMaps w/ breakOut: " + measure {
for (_ <- 0 to 1000) pivoted2.values.map { _.size }.sum
})
}
}
```