Changed HashMap.getOrElseUpdate to only calculate the index once

l0rinc · l0rinc · commit 47cffd3c47ba · 2016-11-15T18:40:58.000+02:00
Since groupBy uses this method extensively and suffered a measurable slowdown in 2.12, this modification restores (and exceeds) its original speed, i.e.

2.11.8  30915 ops/s
2.12.0  28268 ops/s
2.12.1  37931 ops/s

 i.e. this commit is 30% faster than 2.12.0 and 20% faster than 2.11.8, according to a JMH benchmark performing a vector.groupBy(Integer.bitCount)

---

(ns/op -&gt; smaller is better)

before:
    Benchmark                                             (size)  Mode  Cnt     Score     Error  Units
    s.c.immutable.VectorMapBenchmark.groupBy                 100  avgt   20  4369.275 ± 346.054  ns/op
    s.c.mutable.HashMapBenchmark.getOrElseUpdate_found       100  avgt   20  3604.498 ±  25.567  ns/op
    s.c.mutable.HashMapBenchmark.getOrElseUpdate_missing     100  avgt   20  4022.128 ±  27.152  ns/op

after:
    Benchmark                                             (size)  Mode  Cnt     Score     Error  Units
    s.c.immutable.VectorMapBenchmark.groupBy                 100  avgt   20  3062.642 ±  36.108  ns/op
    s.c.mutable.HashMapBenchmark.getOrElseUpdate_found       100  avgt   20  2829.737 ±  45.172  ns/op
    s.c.mutable.HashMapBenchmark.getOrElseUpdate_missing     100  avgt   20  2212.019 ± 153.345  ns/op
diff --git a/src/library/scala/collection/mutable/HashMap.scala b/src/library/scala/collection/mutable/HashMap.scala
@@ -72,6 +72,18 @@ extends AbstractMap[A, B]
     else Some(e.value)
   }
 
+  override def getOrElseUpdate(key: A, defaultValue: => B): B = {
+    val i = index(elemHashCode(key))
+    val entry = findEntry0(key, i)
+    if (entry != null)
+      entry.value
+    else {
+      val newEntry = createNewEntry(key, defaultValue)
+      addEntry0(newEntry, i)
+      newEntry.value
+    }
+  }
+
   override def put(key: A, value: B): Option[B] = {
     val e = findOrAddEntry(key, value)
     if (e eq null) None
diff --git a/src/library/scala/collection/mutable/HashTable.scala b/src/library/scala/collection/mutable/HashTable.scala
@@ -131,7 +131,7 @@ trait HashTable[A, Entry >: Null <: HashEntry[A, Entry]] extends HashTable.HashU
   protected def findEntry(key: A): Entry =
     findEntry0(key, index(elemHashCode(key)))
 
-  private[this] def findEntry0(key: A, h: Int): Entry = {
+  protected[this] final def findEntry0(key: A, h: Int): Entry = {
     var e = table(h).asInstanceOf[Entry]
     while (e != null && !elemEquals(e.key, key)) e = e.next
     e
@@ -145,7 +145,7 @@ trait HashTable[A, Entry >: Null <: HashEntry[A, Entry]] extends HashTable.HashU
     addEntry0(e, index(elemHashCode(e.key)))
   }
 
-  private[this] def addEntry0(e: Entry, h: Int) {
+  protected[this] final def addEntry0(e: Entry, h: Int) {
     e.next = table(h).asInstanceOf[Entry]
     table(h) = e
     tableSize = tableSize + 1
