Merge pull request #5755 from rorygraves/2.12.x_map4

Improve the performance of Map4 to HashMap and Set4 to HashSet transitions

5 files changed, 64 insertions, 8 deletions

diff --git a/src/library/scala/collection/immutable/Map.scala b/src/library/scala/collection/immutable/Map.scala
index cbdf7b39f5..4107b6414d 100644
--- a/src/library/scala/collection/immutable/Map.scala
+++ b/src/library/scala/collection/immutable/Map.scala
@@ -198,7 +198,7 @@ object Map extends ImmutableMapFactory[Map] {
       else if (key == key2) new Map4(key1, value1, key2, value, key3, value3, key4, value4)
       else if (key == key3) new Map4(key1, value1, key2, value2, key3, value, key4, value4)
       else if (key == key4) new Map4(key1, value1, key2, value2, key3, value3, key4, value)
-      else new HashMap + ((key1, value1), (key2, value2), (key3, value3), (key4, value4), (key, value))
+      else (new HashMap).updated(key1,value1).updated(key2, value2).updated(key3, value3).updated(key4, value4).updated(key, value)
     def + [V1 >: V](kv: (K, V1)): Map[K, V1] = updated(kv._1, kv._2)
     def - (key: K): Map[K, V] =
       if (key == key1)      new Map3(key2, value2, key3, value3, key4, value4)
diff --git a/src/library/scala/collection/immutable/Set.scala b/src/library/scala/collection/immutable/Set.scala
index 047ea736bd..0f16f97cb0 100644
--- a/src/library/scala/collection/immutable/Set.scala
+++ b/src/library/scala/collection/immutable/Set.scala
@@ -193,7 +193,7 @@ object Set extends ImmutableSetFactory[Set] {
       elem == elem1 || elem == elem2 || elem == elem3 || elem == elem4
     def + (elem: A): Set[A] =
       if (contains(elem)) this
-      else new HashSet[A] + (elem1, elem2, elem3, elem4, elem)
+      else new HashSet[A] + elem1 + elem2 + elem3 + elem4 + elem
     def - (elem: A): Set[A] =
       if (elem == elem1) new Set3(elem2, elem3, elem4)
       else if (elem == elem2) new Set3(elem1, elem3, elem4)
diff --git a/test/benchmarks/src/main/scala/scala/collection/immutable/ListBenchmark.scala b/test/benchmarks/src/main/scala/scala/collection/immutable/ListBenchmark.scala
index 94844dcae2..36e2518993 100644
--- a/test/benchmarks/src/main/scala/scala/collection/immutable/ListBenchmark.scala
+++ b/test/benchmarks/src/main/scala/scala/collection/immutable/ListBenchmark.scala
@@ -23,12 +23,14 @@ class ListBenchmark {
   var values: List[Content] = _
   var mid: Content = _
   var last: Content = _
+  var replacement: Content = _
 
 
   @Setup(Level.Trial) def initKeys(): Unit = {
     values = List.tabulate(size)(v => Content(v))
     mid = Content(size / 2)
     last = Content(Math.max(0,size -1))
+    replacement = Content(size * 2 + 1)
   }
 
   @Benchmark def filter_includeAll: Any = {
@@ -55,18 +57,14 @@ class ListBenchmark {
     values.filter(v => v.value == last.value)
   }
 
-  @Setup(Level.Trial) def initKeys(): Unit = {
-    values = List.tabulate(size)(n => if (n == size / 2) "mid" else "")
-  }
-
   @Benchmark def mapConserve_identity: Any = {
     values.mapConserve(x => x)
   }
 
   @Benchmark def mapConserve_modifyAll: Any = {
-    values.mapConserve(x => "replace")
+    values.mapConserve(x => replacement)
   }
   @Benchmark def mapConserve_modifyMid: Any = {
-    values.mapConserve(x => if (x == "mid") "replace" else x)
+    values.mapConserve(x => if (x == mid) replacement else x)
   }
 }
diff --git a/test/benchmarks/src/main/scala/scala/collection/immutable/MapBenchmark.scala b/test/benchmarks/src/main/scala/scala/collection/immutable/MapBenchmark.scala
new file mode 100644
index 0000000000..a0358d6a1a
--- /dev/null
+++ b/test/benchmarks/src/main/scala/scala/collection/immutable/MapBenchmark.scala
@@ -0,0 +1,29 @@
+package scala.collection.immutable
+
+import java.util.concurrent.TimeUnit
+
+import org.openjdk.jmh.annotations._
+import org.openjdk.jmh.infra._
+
+@BenchmarkMode(Array(Mode.AverageTime))
+@Fork(2)
+@Threads(1)
+@Warmup(iterations = 10)
+@Measurement(iterations = 10)
+@OutputTimeUnit(TimeUnit.NANOSECONDS)
+@State(Scope.Benchmark)
+class MapBenchmark {
+
+  var base: Map[String,String] = _
+
+
+  @Setup(Level.Trial) def initKeys(): Unit = {
+    base = Map("a" -> "a", "b" -> "b", "c" -> "c", "d" -> "d")
+  }
+
+  // immutable map is implemented as EmptyMap -> Map1 -> Map2 -> Map3 -> Map4 -> Hashmap
+  // add an extra entry to Map4 causes a lot of work, benchmark the transition
+  @Benchmark def map4AddElement(bh: Blackhole): Unit = {
+    bh.consume(base.updated("e", "e"))
+  }
+}
diff --git a/test/benchmarks/src/main/scala/scala/collection/immutable/SetBenchmark.scala b/test/benchmarks/src/main/scala/scala/collection/immutable/SetBenchmark.scala
new file mode 100644
index 0000000000..9330626691
--- /dev/null
+++ b/test/benchmarks/src/main/scala/scala/collection/immutable/SetBenchmark.scala
@@ -0,0 +1,29 @@
+package scala.collection.immutable
+
+import java.util.concurrent.TimeUnit
+
+import org.openjdk.jmh.annotations._
+import org.openjdk.jmh.infra._
+
+@BenchmarkMode(Array(Mode.AverageTime))
+@Fork(2)
+@Threads(1)
+@Warmup(iterations = 10)
+@Measurement(iterations = 10)
+@OutputTimeUnit(TimeUnit.NANOSECONDS)
+@State(Scope.Benchmark)
+class SetBenchmark {
+
+  var base: Set[String] = _
+
+
+  @Setup(Level.Trial) def initKeys(): Unit = {
+    base = Set("a", "b", "c", "d")
+  }
+  
+  // immutable map is implemented as EmptySet -> Set1 -> Set2 -> Set3 -> Set4 -> HashSet
+  // add an extra entry to Set4 causes a lot of work, benchmark the transition
+  @Benchmark def set4AddElement(bh: Blackhole): Unit = {
+    bh.consume(base + "e")
+  }
+}