diff options
author | Pap Lőrinc <paplorinc@gmail.com> | 2016-11-22 14:42:48 +0200 |
---|---|---|
committer | Pap Lőrinc <paplorinc@gmail.com> | 2016-11-24 12:47:02 +0200 |
commit | a5014447861a5678c8b595e235019bb8fec098a7 (patch) | |
tree | 1177734bce459bd7c6363855fc0bdd56badab4b5 /src | |
parent | 7952525e7119282ec8308a0076db54923f95dc21 (diff) | |
download | scala-a5014447861a5678c8b595e235019bb8fec098a7.tar.gz scala-a5014447861a5678c8b595e235019bb8fec098a7.tar.bz2 scala-a5014447861a5678c8b595e235019bb8fec098a7.zip |
Optimized HashTable.index
(`ops/s`, smaller is better)
`Before (9c5d3f8)`:
```scala
[info] # Run complete. Total time: 00:08:15
[info]
[info] Benchmark (size) Mode Cnt Score Error Units
[info] s.c.immutable.VectorMapBenchmark.groupBy 10 avgt 20 645.594 ± 9.435 ns/op
[info] s.c.immutable.VectorMapBenchmark.groupBy 100 avgt 20 2084.216 ± 37.814 ns/op
[info] s.c.immutable.VectorMapBenchmark.groupBy 1000 avgt 20 19878.481 ± 262.404 ns/op
[info] s.c.mutable.HashMapBenchmark.get 10 avgt 20 689.941 ± 5.850 ns/op
[info] s.c.mutable.HashMapBenchmark.get 100 avgt 20 7357.330 ± 45.956 ns/op
[info] s.c.mutable.HashMapBenchmark.get 1000 avgt 20 95767.200 ± 1550.771 ns/op
[info] s.c.mutable.HashMapBenchmark.getOrElseUpdate 10 avgt 20 509.181 ± 2.683 ns/op
[info] s.c.mutable.HashMapBenchmark.getOrElseUpdate 100 avgt 20 5563.301 ± 32.335 ns/op
[info] s.c.mutable.HashMapBenchmark.getOrElseUpdate 1000 avgt 20 71965.365 ± 1809.738 ns/op
[info] s.c.mutable.HashMapBenchmark.put 10 avgt 20 247.270 ± 3.972 ns/op
[info] s.c.mutable.HashMapBenchmark.put 100 avgt 20 5646.185 ± 106.172 ns/op
[info] s.c.mutable.HashMapBenchmark.put 1000 avgt 20 81303.663 ± 954.938 ns/op
```
`Changed modulo to bitwise and in hash calculation (4c729fe)`:
```scala
[info] Benchmark (size) Mode Cnt Score Error Units
[info] s.c.immutable.VectorMapBenchmark.groupBy 10 avgt 20 631.291 ± 9.269 ns/op
[info] s.c.immutable.VectorMapBenchmark.groupBy 100 avgt 20 2077.885 ± 59.737 ns/op
[info] s.c.immutable.VectorMapBenchmark.groupBy 1000 avgt 20 15458.278 ± 317.347 ns/op
[info] s.c.mutable.HashMapBenchmark.get 10 avgt 20 678.013 ± 4.453 ns/op
[info] s.c.mutable.HashMapBenchmark.get 100 avgt 20 7258.522 ± 76.088 ns/op
[info] s.c.mutable.HashMapBenchmark.get 1000 avgt 20 94748.845 ± 1226.120 ns/op
[info] s.c.mutable.HashMapBenchmark.getOrElseUpdate 10 avgt 20 498.042 ± 5.006 ns/op
[info] s.c.mutable.HashMapBenchmark.getOrElseUpdate 100 avgt 20 5243.154 ± 110.372 ns/op
[info] s.c.mutable.HashMapBenchmark.getOrElseUpdate 1000 avgt 20 68194.752 ± 655.436 ns/op
[info] s.c.mutable.HashMapBenchmark.put 10 avgt 20 257.275 ± 1.411 ns/op
[info] s.c.mutable.HashMapBenchmark.put 100 avgt 20 5318.532 ± 152.923 ns/op
[info] s.c.mutable.HashMapBenchmark.put 1000 avgt 20 79607.160 ± 651.779 ns/op
```
`Optimized HashTable.index (6cc1504)`:
```scala
[info] Benchmark (size) Mode Cnt Score Error Units
[info] s.c.immutable.VectorMapBenchmark.groupBy 10 avgt 20 616.164 ± 4.712 ns/op
[info] s.c.immutable.VectorMapBenchmark.groupBy 100 avgt 20 2034.447 ± 14.495 ns/op
[info] s.c.immutable.VectorMapBenchmark.groupBy 1000 avgt 20 14712.164 ± 119.983 ns/op
[info] s.c.mutable.HashMapBenchmark.get 10 avgt 20 679.046 ± 6.872 ns/op
[info] s.c.mutable.HashMapBenchmark.get 100 avgt 20 7242.097 ± 41.244 ns/op
[info] s.c.mutable.HashMapBenchmark.get 1000 avgt 20 95342.919 ± 1521.328 ns/op
[info] s.c.mutable.HashMapBenchmark.getOrElseUpdate 10 avgt 20 488.034 ± 4.554 ns/op
[info] s.c.mutable.HashMapBenchmark.getOrElseUpdate 100 avgt 20 4883.123 ± 59.268 ns/op
[info] s.c.mutable.HashMapBenchmark.getOrElseUpdate 1000 avgt 20 65174.034 ± 496.759 ns/op
[info] s.c.mutable.HashMapBenchmark.put 10 avgt 20 267.983 ± 1.797 ns/op
[info] s.c.mutable.HashMapBenchmark.put 100 avgt 20 5097.351 ± 104.538 ns/op
[info] s.c.mutable.HashMapBenchmark.put 1000 avgt 20 78772.540 ± 543.935 ns/op
```
Summary, i.e. the effect of this PR, according to the benchmarks:
* `groupBy` has a `~35%` speedup
* `get` didn't change
* `getOrElseUpdate` has a `~10%` speedup
* `put` has a `~3%` speedup
Note: caching the `exponent` to a local private field (`Byte` or `Int`) didn't have any performance advantage (only a minor slowdown was measured, possibly because it's accessed via an interface now)
Diffstat (limited to 'src')
-rw-r--r-- | src/library/scala/collection/mutable/HashTable.scala | 14 |
1 files changed, 7 insertions, 7 deletions
diff --git a/src/library/scala/collection/mutable/HashTable.scala b/src/library/scala/collection/mutable/HashTable.scala index 9cb40e3f50..776eafaccc 100644 --- a/src/library/scala/collection/mutable/HashTable.scala +++ b/src/library/scala/collection/mutable/HashTable.scala @@ -360,14 +360,14 @@ trait HashTable[A, Entry >: Null <: HashEntry[A, Entry]] extends HashTable.HashU protected def elemEquals(key1: A, key2: A): Boolean = (key1 == key2) - // Note: - // we take the most significant bits of the hashcode, not the lower ones - // this is of crucial importance when populating the table in parallel - protected final def index(hcode: Int) = { + /** + * Note: we take the most significant bits of the hashcode, not the lower ones + * this is of crucial importance when populating the table in parallel + */ + protected final def index(hcode: Int): Int = { val ones = table.length - 1 - val improved = improve(hcode, seedvalue) - val shifted = (improved >> (32 - java.lang.Integer.bitCount(ones))) & ones - shifted + val exponent = Integer.numberOfLeadingZeros(ones) + (improve(hcode, seedvalue) >>> exponent) & ones } protected def initWithContents(c: HashTable.Contents[A, Entry]) = { |