Map monoid performance

[travisbrown]

Cats's monoid instance for maps is extremely slow for the common use case where you're foldMap-ing over e.g. a collection of documents. For example, here's a simple benchmark where we add up 1000 singleton maps with 500 distinct keys:

import cats.instances.list._, cats.instances.int._, cats.instances.map._
import org.openjdk.jmh.annotations.{ Benchmark, Scope, State }
import scalaz.std.anyVal._, scalaz.std.list._, scalaz.std.map._

@State(Scope.Benchmark)
class MapMonoidBench {
  val words: List[String] = for {
    c <- List("a", "b", "c", "d", "e")
    t <- 1 to 100
  } yield c * t

  val maps: List[Map[String, Int]] = (words ++ words).map(s => Map(s -> 1))

  @Benchmark def combineAllCats: Map[String, Int] =
    cats.Monoid[Map[String, Int]].combineAll(maps)

  @Benchmark def combineCats: Map[String, Int] = maps.foldLeft(Map.empty[String, Int]) {
    case (acc, m) => cats.Monoid[Map[String, Int]].combine(acc, m)
  }

  @Benchmark def combineScalaz: Map[String, Int] = maps.foldLeft(Map.empty[String, Int]) {
    case (acc, m) => scalaz.Monoid[Map[String, Int]].append(acc, m)
  }

  @Benchmark def combineNeither: Map[String, Int] = maps.foldLeft(Map.empty[String, Int]) {
    case (acc, m) => m.foldLeft(acc) {
      case (m, (k, v)) => m.updated(k, v + m.getOrElse(k, 0))
    }
  }

  @Benchmark def foldMapCats: Map[String, Int] = cats.Foldable[List].foldMap(maps)(identity)
  @Benchmark def foldMapScalaz: Map[String, Int] = scalaz.Foldable[List].foldMap(maps)(identity)
}

And Scalaz has ~100 times the throughput:

[info] Benchmark                       Mode  Cnt     Score     Error  Units
[info] MapMonoidBench.combineAllCats  thrpt   20    68.481 ±   1.521  ops/s
[info] MapMonoidBench.combineCats     thrpt   20    54.264 ±   3.205  ops/s
[info] MapMonoidBench.combineNeither  thrpt   20  8742.891 ± 125.203  ops/s
[info] MapMonoidBench.combineScalaz   thrpt   20  6624.394 ±  68.323  ops/s
[info] MapMonoidBench.foldMapCats     thrpt   20    59.143 ±   0.445  ops/s
[info] MapMonoidBench.foldMapScalaz   thrpt   20  5581.814 ±  52.048  ops/s

[kailuowang]

For reference
scalaz uses map.valuesIterator.foldLeft and map.updated to build a new Map

Cats creates a new mutable map and then wrap it as an immutable Map
It looks like (not 100% sure though) that in this case, the allocation and wrapping of mutable Map is taking a performance toll higher than it gained from immutable map (if any)

[johnynek]

Algebird optimized this, but we seem to have misapplied the learnings here:

https://github.com/twitter/algebird/blob/develop/algebird-core/src/main/scala/com/twitter/algebird/MapAlgebra.scala#L58

we should only use the mutable map in the combineAll, which should be specific, not the generic one from combine.

Note algebird uses the immutable style for combine, but starts a new mutable map and updates that one for combineAll (sumOption).

[adelbertc]

fixed by #1300