Changed HashMap.getOrElseUpdate to only calculate the index once

Fixes https://issues.scala-lang.org/browse/SI-10049 Since `groupBy` uses this method extensively and suffered a measurable slowdown in `2.12.0`, this modification restores (and exceeds) its original speed. --- included benchmarks: (`ns/op` → smaller is better) `before (2.12.0):` ```java Benchmark (size) Mode Cnt Score Error Units s.c.immutable.VectorMapBenchmark.groupBy 10 avgt 20 865.693 ± 7.869 ns/op s.c.immutable.VectorMapBenchmark.groupBy 100 avgt 20 3095.657 ± 56.438 ns/op s.c.immutable.VectorMapBenchmark.groupBy 1000 avgt 20 28247.005 ± 470.513 ns/op s.c.mutable.HashMapBenchmark.get 10 avgt 20 679.448 ± 11.809 ns/op s.c.mutable.HashMapBenchmark.get 100 avgt 20 7240.178 ± 61.734 ns/op s.c.mutable.HashMapBenchmark.get 1000 avgt 20 95725.127 ± 2373.458 ns/op s.c.mutable.HashMapBenchmark.getOrElseUpdate 10 avgt 20 836.561 ± 20.085 ns/op s.c.mutable.HashMapBenchmark.getOrElseUpdate 100 avgt 20 7891.368 ± 56.808 ns/op s.c.mutable.HashMapBenchmark.getOrElseUpdate 1000 avgt 20 97478.629 ± 1782.497 ns/op s.c.mutable.HashMapBenchmark.put 10 avgt 20 243.422 ± 2.915 ns/op s.c.mutable.HashMapBenchmark.put 100 avgt 20 5810.927 ± 60.054 ns/op s.c.mutable.HashMapBenchmark.put 1000 avgt 20 82175.539 ± 1690.296 ns/op ``` `after:` ```java Benchmark (size) Mode Cnt Score Error Units s.c.immutable.VectorMapBenchmark.groupBy 10 avgt 20 627.007 ± 9.718 ns/op s.c.immutable.VectorMapBenchmark.groupBy 100 avgt 20 2086.955 ± 19.042 ns/op s.c.immutable.VectorMapBenchmark.groupBy 1000 avgt 20 19515.234 ± 173.647 ns/op s.c.mutable.HashMapBenchmark.get 10 avgt 20 683.977 ± 11.843 ns/op s.c.mutable.HashMapBenchmark.get 100 avgt 20 7345.675 ± 41.092 ns/op s.c.mutable.HashMapBenchmark.get 1000 avgt 20 95085.926 ± 1702.997 ns/op s.c.mutable.HashMapBenchmark.getOrElseUpdate 10 avgt 20 503.208 ± 2.643 ns/op s.c.mutable.HashMapBenchmark.getOrElseUpdate 100 avgt 20 5526.483 ± 28.262 ns/op s.c.mutable.HashMapBenchmark.getOrElseUpdate 1000 avgt 20 69265.900 ± 674.958 ns/op s.c.mutable.HashMapBenchmark.put 10 avgt 20 252.481 ± 7.597 ns/op s.c.mutable.HashMapBenchmark.put 100 avgt 20 5708.034 ± 110.360 ns/op s.c.mutable.HashMapBenchmark.put 1000 avgt 20 82051.378 ± 1432.009 ns/op ``` i.e. for the given benchmark conditions `~40%` faster `groupBy` and `getOrElseUpdate` (cherry picked from commit b67ca7d)
scala · adriaanm · Jan 6, 2017 · Jan 5, 2017 · Jul 21, 2016 · Nov 22, 2016
commit 02c30a174de3032e377b3bea8854a9588d374dfb
diff --git a/src/library/scala/collection/mutable/HashMap.scala b/src/library/scala/collection/mutable/HashMap.scala
@@ -72,6 +72,37 @@ extends AbstractMap[A, B]
     else Some(e.value)
   }
 
+  override def getOrElseUpdate(key: A, defaultValue: => B): B = {
+    val i = index(elemHashCode(key))
+    val entry = findEntry(key, i)
+    if (entry != null) entry.value
+    else addEntry(createNewEntry(key, defaultValue), i)
+  }
+
+  /* inlined HashTable.findEntry0 to preserve its visibility */
+  private[this] def findEntry(key: A, h: Int): Entry = {
+    var e = table(h).asInstanceOf[Entry]
+    while (notFound(key, e))
+      e = e.next
+    e
+  }
+  private[this] def notFound(key: A, e: Entry): Boolean = (e != null) && !elemEquals(e.key, key)
+
+  /* inlined HashTable.addEntry0 to preserve its visibility */
+  private[this] def addEntry(e: Entry, h: Int): B = {
+    if (tableSize >= threshold) addEntry(e)
+    else addEntry0(e, h)
+    e.value
+  }
+
+  /* extracted to make addEntry inlinable */
+  private[this] def addEntry0(e: Entry, h: Int) {
+    e.next = table(h).asInstanceOf[Entry]
+    table(h) = e
+    tableSize += 1
+    nnSizeMapAdd(h)
+  }
+
   override def put(key: A, value: B): Option[B] = {
     val e = findOrAddEntry(key, value)
     if (e eq null) None