8000 [backport] Hash table getOrElseUpdate and indexing by adriaanm · Pull Request #5626 · scala/scala · GitHub
[go: up one dir, main page]
Skip to content

[backport] Hash table getOrElseUpdate and indexing #5626

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 7 commits into from
Jan 6, 2017
Merged

[backport] Hash table getOrElseUpdate and indexing #5626

merged 7 commits into from
Jan 6, 2017

Conversation

adriaanm
Copy link
Contributor
@adriaanm adriaanm commented Jan 4, 2017

Rebase #5566 to include #5612, which should side-step scala/scala-dev#251.

@scala-jenkins scala-jenkins added this to the 2.11.9 milestone Jan 4, 2017
@adriaanm adriaanm mentioned this pull request Jan 4, 2017
Closed
@adriaanm adriaanm changed the title Rebase #5566 [backport] Hash table getOrElseUpdate and indexing Jan 4, 2017
@adriaanm
Copy link
Contributor Author
adriaanm commented Jan 4, 2017

Forgot to bump starr. Will push again

@adriaanm adriaanm force-pushed the rebase-5566 branch 2 times, most recently from f718430 to 94e4e36 Compare January 4, 2017 20:35
adriaanm and others added 7 commits January 5, 2017 13:26
@adriaanm
Restarr on 2.11.8-18269ea
cb7192c
@adriaanm
SI-8774 Null link fields in mutable hash maps on removal.
f31745a 
(cherry picked from commit 9a24860)
@l0rinc @adriaanm
Optimized HashTable.index
5fd422b 
(`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)
(cherry picked from commit a501444)
@l0rinc @adriaanm
Changed modulo to bitwise AND in hash calculation
26ad9cc 
(cherry picked from commit 7952525)
@l0rinc @adriaanm
Changed hashing bit rotation to use Integer.rotateRight
276db03 
(cherry picked from commit bc91223)
@l0rinc @adriaanm
Changed HashMap.getOrElseUpdate to only calculate the index once
02c30a1 
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)
@l0rinc @adriaanm
Simplify HashTable.index further
1e82a92 
(cherry picked from commit 26c87f1)
@adriaanm
Copy link
Contributor Author
adriaanm commented Jan 6, 2017

One benign spurious test failure (reflection mem check)

@adriaanm adriaanm merged commit 1b6b19b into scala:2.11.x Jan 6, 2017
@SethTisue SethTisue mentioned this pull request Jan 14, 2017
Merged
This was referenced Feb 15, 2017
Merged
Merged
@SethTisue SethTisue modified the milestones: 2.11.11, 2.11.9 May 1, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
2.11.11
Development

Successfully merging this pull request may close these issues.
4 participants
@adriaanm @SethTisue @scala-jenkins @l0rinc
0