diff options
author | Pap Lőrinc <paplorinc@gmail.com> | 2016-11-16 17:27:36 +0200 |
---|---|---|
committer | Pap Lőrinc <paplorinc@gmail.com> | 2016-11-18 12:48:59 +0200 |
commit | b67ca7dc6bb84758f9c9f64d68b0b11c20995aa0 (patch) | |
tree | 955e595327a7bbca4527642a908d42696af7aa0f /src/library | |
parent | 5c93cd2431276fe3c712cb60e8a7a696c1776f10 (diff) | |
download | scala-b67ca7dc6bb84758f9c9f64d68b0b11c20995aa0.tar.gz scala-b67ca7dc6bb84758f9c9f64d68b0b11c20995aa0.tar.bz2 scala-b67ca7dc6bb84758f9c9f64d68b0b11c20995aa0.zip |
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`
Diffstat (limited to 'src/library')
-rw-r--r-- | src/library/scala/collection/mutable/HashMap.scala | 31 |
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 |