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`

1 files changed, 31 insertions, 0 deletions

diff --git a/src/library/scala/collection/mutable/HashMap.scala b/src/library/scala/collection/mutable/HashMap.scala
index eab4202353..11ff1f0893 100644
--- 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