Skip to content

[nomerge] HashMap#transform reuses structure#8630

Merged
lrytz merged 2 commits intoscala:2.12.xfrom
hrhino:topic/hashmap-transform
Feb 5, 2020
Merged

[nomerge] HashMap#transform reuses structure#8630
lrytz merged 2 commits intoscala:2.12.xfrom
hrhino:topic/hashmap-transform

Conversation

@hrhino
Copy link
Contributor

@hrhino hrhino commented Jan 8, 2020

(2.12.x only, of course)

The keys in the resulting map are the same, so the internal structure will also be the same, and that can be used to avoid allocating tuples and going through MapBuilder and other such convolutions.

Benchmark results:

  • 2.12.x:
[info] Benchmark                                                            (size)  Mode  Cnt       Score      Error   Units
[info] HashMapBenchmark.transform                                               10  avgt   20     656.603 ±    2.354   ns/op
[info] HashMapBenchmark.transform:·gc.alloc.rate                                10  avgt   20    1355.348 ±    4.860  MB/sec
[info] HashMapBenchmark.transform:·gc.alloc.rate.norm                           10  avgt   20    1400.001 ±    0.002    B/op
[info] HashMapBenchmark.transform:·gc.churn.PS_Eden_Space                       10  avgt   20    1362.048 ±   52.022  MB/sec
[info] HashMapBenchmark.transform:·gc.churn.PS_Eden_Space.norm                  10  avgt   20    1406.807 ±   50.904    B/op
[info] HashMapBenchmark.transform:·gc.churn.PS_Survivor_Space                   10  avgt   20       0.143 ±    0.028  MB/sec
[info] HashMapBenchmark.transform:·gc.churn.PS_Survivor_Space.norm              10  avgt   20       0.147 ±    0.029    B/op
[info] HashMapBenchmark.transform:·gc.count                                     10  avgt   20     241.000             counts
[info] HashMapBenchmark.transform:·gc.time                                      10  avgt   20     181.000                 ms
[info] HashMapBenchmark.transform                                              100  avgt   20    5664.033 ±   20.978   ns/op
[info] HashMapBenchmark.transform:·gc.alloc.rate                               100  avgt   20    2280.462 ±    8.412  MB/sec
[info] HashMapBenchmark.transform:·gc.alloc.rate.norm                          100  avgt   20   20320.009 ±    0.018    B/op
[info] HashMapBenchmark.transform:·gc.churn.PS_Eden_Space                      100  avgt   20    2275.425 ±   98.654  MB/sec
[info] HashMapBenchmark.transform:·gc.churn.PS_Eden_Space.norm                 100  avgt   20   20275.297 ±  878.556    B/op
[info] HashMapBenchmark.transform:·gc.churn.PS_Survivor_Space                  100  avgt   20       0.114 ±    0.036  MB/sec
[info] HashMapBenchmark.transform:·gc.churn.PS_Survivor_Space.norm             100  avgt   20       1.012 ±    0.325    B/op
[info] HashMapBenchmark.transform:·gc.count                                    100  avgt   20     249.000             counts
[info] HashMapBenchmark.transform:·gc.time                                     100  avgt   20     186.000                 ms
[info] HashMapBenchmark.transform                                             1000  avgt   20  111883.999 ± 2776.556   ns/op
[info] HashMapBenchmark.transform:·gc.alloc.rate                              1000  avgt   20    1519.829 ±   37.714  MB/sec
[info] HashMapBenchmark.transform:·gc.alloc.rate.norm                         1000  avgt   20  267298.361 ±    6.651    B/op
[info] HashMapBenchmark.transform:·gc.churn.PS_Eden_Space                     1000  avgt   20    1512.921 ±   66.094  MB/sec
[info] HashMapBenchmark.transform:·gc.churn.PS_Eden_Space.norm                1000  avgt   20  266064.016 ± 9137.317    B/op
[info] HashMapBenchmark.transform:·gc.churn.PS_Survivor_Space                 1000  avgt   20       0.170 ±    0.048  MB/sec
[info] HashMapBenchmark.transform:·gc.churn.PS_Survivor_Space.norm            1000  avgt   20      29.943 ±    8.709    B/op
[info] HashMapBenchmark.transform:·gc.count                                   1000  avgt   20     239.000             counts
[info] HashMapBenchmark.transform:·gc.time                                    1000  avgt   20     182.000                 ms
[info] HashMapBenchmark.transformConserve                                       10  avgt   20     619.002 ±    4.256   ns/op
[info] HashMapBenchmark.transformConserve:·gc.alloc.rate                        10  avgt   20    1437.758 ±    9.867  MB/sec
[info] HashMapBenchmark.transformConserve:·gc.alloc.rate.norm                   10  avgt   20    1400.001 ±    0.002    B/op
[info] HashMapBenchmark.transformConserve:·gc.churn.PS_Eden_Space               10  avgt   20    1431.354 ±   43.512  MB/sec
[info] HashMapBenchmark.transformConserve:·gc.churn.PS_Eden_Space.norm          10  avgt   20    1393.801 ±   42.144    B/op
[info] HashMapBenchmark.transformConserve:·gc.churn.PS_Survivor_Space           10  avgt   20       0.114 ±    0.029  MB/sec
[info] HashMapBenchmark.transformConserve:·gc.churn.PS_Survivor_Space.norm      10  avgt   20       0.111 ±    0.028    B/op
[info] HashMapBenchmark.transformConserve:·gc.count                             10  avgt   20     244.000             counts
[info] HashMapBenchmark.transformConserve:·gc.time                              10  avgt   20     181.000                 ms
[info] HashMapBenchmark.transformConserve                                      100  avgt   20    5459.810 ±   30.177   ns/op
[info] HashMapBenchmark.transformConserve:·gc.alloc.rate                       100  avgt   20    2365.863 ±   13.078  MB/sec
[info] HashMapBenchmark.transformConserve:·gc.alloc.rate.norm                  100  avgt   20   20320.009 ±    0.018    B/op
[info] HashMapBenchmark.transformConserve:·gc.churn.PS_Eden_Space              100  avgt   20    2360.973 ±   69.873  MB/sec
[info] HashMapBenchmark.transformConserve:·gc.churn.PS_Eden_Space.norm         100  avgt   20   20278.754 ±  607.945    B/op
[info] HashMapBenchmark.transformConserve:·gc.churn.PS_Survivor_Space          100  avgt   20       0.111 ±    0.033  MB/sec
[info] HashMapBenchmark.transformConserve:·gc.churn.PS_Survivor_Space.norm     100  avgt   20       0.957 ±    0.283    B/op
[info] HashMapBenchmark.transformConserve:·gc.count                            100  avgt   20     255.000             counts
[info] HashMapBenchmark.transformConserve:·gc.time                             100  avgt   20     190.000                 ms
[info] HashMapBenchmark.transformConserve                                     1000  avgt   20  100900.656 ±  621.356   ns/op
[info] HashMapBenchmark.transformConserve:·gc.alloc.rate                      1000  avgt   20    1684.007 ±   10.358  MB/sec
[info] HashMapBenchmark.transformConserve:·gc.alloc.rate.norm                 1000  avgt   20  267290.290 ±    4.321    B/op
[info] HashMapBenchmark.transformConserve:·gc.churn.PS_Eden_Space             1000  avgt   20    1685.846 ±   53.919  MB/sec
[info] HashMapBenchmark.transformConserve:·gc.churn.PS_Eden_Space.norm        1000  avgt   20  267592.455 ± 8666.193    B/op
[info] HashMapBenchmark.transformConserve:·gc.churn.PS_Survivor_Space         1000  avgt   20       0.159 ±    0.039  MB/sec
[info] HashMapBenchmark.transformConserve:·gc.churn.PS_Survivor_Space.norm    1000  avgt   20      25.298 ±    6.220    B/op
[info] HashMapBenchmark.transformConserve:·gc.count                           1000  avgt   20     244.000             counts
[info] HashMapBenchmark.transformConserve:·gc.time                            1000  avgt   20     188.000                 ms
  • This PR:
[info] Benchmark                                                            (size)  Mode  Cnt      Score      Error   Units
[info] HashMapBenchmark.transform                                               10  avgt   20    110.214 ±    0.501   ns/op
[info] HashMapBenchmark.transform:·gc.alloc.rate                                10  avgt   20   2768.441 ±   12.595  MB/sec
[info] HashMapBenchmark.transform:·gc.alloc.rate.norm                           10  avgt   20    480.000 ±    0.001    B/op
[info] HashMapBenchmark.transform:·gc.churn.PS_Eden_Space                       10  avgt   20   2770.594 ±  121.884  MB/sec
[info] HashMapBenchmark.transform:·gc.churn.PS_Eden_Space.norm                  10  avgt   20    480.376 ±   21.031    B/op
[info] HashMapBenchmark.transform:·gc.churn.PS_Survivor_Space                   10  avgt   20      0.138 ±    0.044  MB/sec
[info] HashMapBenchmark.transform:·gc.churn.PS_Survivor_Space.norm              10  avgt   20      0.024 ±    0.008    B/op
[info] HashMapBenchmark.transform:·gc.count                                     10  avgt   20    235.000             counts
[info] HashMapBenchmark.transform:·gc.time                                      10  avgt   20    179.000                 ms
[info] HashMapBenchmark.transform                                              100  avgt   20   1314.796 ±   10.701   ns/op
[info] HashMapBenchmark.transform:·gc.alloc.rate                               100  avgt   20   2490.990 ±   19.863  MB/sec
[info] HashMapBenchmark.transform:·gc.alloc.rate.norm                          100  avgt   20   5152.002 ±    0.004    B/op
[info] HashMapBenchmark.transform:·gc.churn.PS_Eden_Space                      100  avgt   20   2490.424 ±   71.604  MB/sec
[info] HashMapBenchmark.transform:·gc.churn.PS_Eden_Space.norm                 100  avgt   20   5151.372 ±  157.034    B/op
[info] HashMapBenchmark.transform:·gc.churn.PS_Survivor_Space                  100  avgt   20      0.142 ±    0.033  MB/sec
[info] HashMapBenchmark.transform:·gc.churn.PS_Survivor_Space.norm             100  avgt   20      0.293 ±    0.068    B/op
[info] HashMapBenchmark.transform:·gc.count                                    100  avgt   20    254.000             counts
[info] HashMapBenchmark.transform:·gc.time                                     100  avgt   20    199.000                 ms
[info] HashMapBenchmark.transform                                             1000  avgt   20  14301.752 ±   69.119   ns/op
[info] HashMapBenchmark.transform:·gc.alloc.rate                              1000  avgt   20   2225.222 ±   10.718  MB/sec
[info] HashMapBenchmark.transform:·gc.alloc.rate.norm                         1000  avgt   20  50064.024 ±    0.047    B/op
[info] HashMapBenchmark.transform:·gc.churn.PS_Eden_Space                     1000  avgt   20   2227.828 ±   69.428  MB/sec
[info] HashMapBenchmark.transform:·gc.churn.PS_Eden_Space.norm                1000  avgt   20  50122.329 ± 1533.214    B/op
[info] HashMapBenchmark.transform:·gc.churn.PS_Survivor_Space                 1000  avgt   20      0.173 ±    0.028  MB/sec
[info] HashMapBenchmark.transform:·gc.churn.PS_Survivor_Space.norm            1000  avgt   20      3.888 ±    0.630    B/op
[info] HashMapBenchmark.transform:·gc.count                                   1000  avgt   20    252.000             counts
[info] HashMapBenchmark.transform:·gc.time                                    1000  avgt   20    188.000                 ms
[info] HashMapBenchmark.transformConserve                                       10  avgt   20     72.495 ±    0.174   ns/op
[info] HashMapBenchmark.transformConserve:·gc.alloc.rate                        10  avgt   20    911.916 ±    2.184  MB/sec
[info] HashMapBenchmark.transformConserve:·gc.alloc.rate.norm                   10  avgt   20    104.000 ±    0.001    B/op
[info] HashMapBenchmark.transformConserve:·gc.churn.PS_Eden_Space               10  avgt   20    909.602 ±   26.879  MB/sec
[info] HashMapBenchmark.transformConserve:·gc.churn.PS_Eden_Space.norm          10  avgt   20    103.740 ±    3.143    B/op
[info] HashMapBenchmark.transformConserve:·gc.churn.PS_Survivor_Space           10  avgt   20      0.117 ±    0.030  MB/sec
[info] HashMapBenchmark.transformConserve:·gc.churn.PS_Survivor_Space.norm      10  avgt   20      0.013 ±    0.003    B/op
[info] HashMapBenchmark.transformConserve:·gc.count                             10  avgt   20    255.000             counts
[info] HashMapBenchmark.transformConserve:·gc.time                              10  avgt   20    193.000                 ms
[info] HashMapBenchmark.transformConserve                                      100  avgt   20    949.201 ±    1.603   ns/op
[info] HashMapBenchmark.transformConserve:·gc.alloc.rate                       100  avgt   20   1269.699 ±    2.140  MB/sec
[info] HashMapBenchmark.transformConserve:·gc.alloc.rate.norm                  100  avgt   20   1896.002 ±    0.003    B/op
[info] HashMapBenchmark.transformConserve:·gc.churn.PS_Eden_Space              100  avgt   20   1267.611 ±   29.572  MB/sec
[info] HashMapBenchmark.transformConserve:·gc.churn.PS_Eden_Space.norm         100  avgt   20   1892.899 ±   44.587    B/op
[info] HashMapBenchmark.transformConserve:·gc.churn.PS_Survivor_Space          100  avgt   20      0.156 ±    0.035  MB/sec
[info] HashMapBenchmark.transformConserve:·gc.churn.PS_Survivor_Space.norm     100  avgt   20      0.233 ±    0.053    B/op
[info] HashMapBenchmark.transformConserve:·gc.count                            100  avgt   20    254.000             counts
[info] HashMapBenchmark.transformConserve:·gc.time                             100  avgt   20    189.000                 ms
[info] HashMapBenchmark.transformConserve                                     1000  avgt   20   9524.194 ±  111.590   ns/op
[info] HashMapBenchmark.transformConserve:·gc.alloc.rate                      1000  avgt   20   1202.089 ±   14.115  MB/sec
[info] HashMapBenchmark.transformConserve:·gc.alloc.rate.norm                 1000  avgt   20  18008.016 ±    0.031    B/op
[info] HashMapBenchmark.transformConserve:·gc.churn.PS_Eden_Space             1000  avgt   20   1201.171 ±   40.637  MB/sec
[info] HashMapBenchmark.transformConserve:·gc.churn.PS_Eden_Space.norm        1000  avgt   20  17995.335 ±  594.724    B/op
[info] HashMapBenchmark.transformConserve:·gc.churn.PS_Survivor_Space         1000  avgt   20      0.137 ±    0.039  MB/sec
[info] HashMapBenchmark.transformConserve:·gc.churn.PS_Survivor_Space.norm    1000  avgt   20      2.056 ±    0.565    B/op
[info] HashMapBenchmark.transformConserve:·gc.count                           1000  avgt   20    253.000             counts
[info] HashMapBenchmark.transformConserve:·gc.time                            1000  avgt   20    190.000                 ms
REG (with conserve)
[info] Benchmark                                                    (size)  Mode  Cnt      Score      Error   Units
[info] HashMapBenchmark.transform                                       10  avgt   20    114.979 ±    0.622   ns/op
[info] HashMapBenchmark.transform:·gc.alloc.rate                        10  avgt   20   2653.780 ±   14.209  MB/sec
[info] HashMapBenchmark.transform:·gc.alloc.rate.norm                   10  avgt   20    480.000 ±    0.001    B/op
[info] HashMapBenchmark.transform:·gc.churn.PS_Eden_Space               10  avgt   20   2649.555 ±   65.764  MB/sec
[info] HashMapBenchmark.transform:·gc.churn.PS_Eden_Space.norm          10  avgt   20    479.241 ±   11.759    B/op
[info] HashMapBenchmark.transform:·gc.churn.PS_Survivor_Space           10  avgt   20      0.141 ±    0.038  MB/sec
[info] HashMapBenchmark.transform:·gc.churn.PS_Survivor_Space.norm      10  avgt   20      0.025 ±    0.007    B/op
[info] HashMapBenchmark.transform:·gc.count                             10  avgt   20    252.000             counts
[info] HashMapBenchmark.transform:·gc.time                              10  avgt   20    190.000                 ms
[info] HashMapBenchmark.transform                                      100  avgt   20   1369.913 ±    6.994   ns/op
[info] HashMapBenchmark.transform:·gc.alloc.rate                       100  avgt   20   2390.664 ±   12.162  MB/sec
[info] HashMapBenchmark.transform:·gc.alloc.rate.norm                  100  avgt   20   5152.002 ±    0.004    B/op
[info] HashMapBenchmark.transform:·gc.churn.PS_Eden_Space              100  avgt   20   2393.799 ±   78.711  MB/sec
[info] HashMapBenchmark.transform:·gc.churn.PS_Eden_Space.norm         100  avgt   20   5158.951 ±  172.124    B/op
[info] HashMapBenchmark.transform:·gc.churn.PS_Survivor_Space          100  avgt   20      0.152 ±    0.037  MB/sec
[info] HashMapBenchmark.transform:·gc.churn.PS_Survivor_Space.norm     100  avgt   20      0.328 ±    0.080    B/op
[info] HashMapBenchmark.transform:·gc.count                            100  avgt   20    256.000             counts
[info] HashMapBenchmark.transform:·gc.time                             100  avgt   20    192.000                 ms
[info] HashMapBenchmark.transform                                     1000  avgt   20  14520.254 ±   73.534   ns/op
[info] HashMapBenchmark.transform:·gc.alloc.rate                      1000  avgt   20   2191.753 ±   11.074  MB/sec
[info] HashMapBenchmark.transform:·gc.alloc.rate.norm                 1000  avgt   20  50064.024 ±    0.047    B/op
[info] HashMapBenchmark.transform:·gc.churn.PS_Eden_Space             1000  avgt   20   2185.506 ±   86.944  MB/sec
[info] HashMapBenchmark.transform:·gc.churn.PS_Eden_Space.norm        1000  avgt   20  49919.103 ± 1925.011    B/op
[info] HashMapBenchmark.transform:·gc.churn.PS_Survivor_Space         1000  avgt   20      0.160 ±    0.056  MB/sec
[info] HashMapBenchmark.transform:·gc.churn.PS_Survivor_Space.norm    1000  avgt   20      3.664 ±    1.275    B/op
[info] HashMapBenchmark.transform:·gc.count                           1000  avgt   20    244.000             counts
[info] HashMapBenchmark.transform:·gc.time                            1000  avgt   20    182.000                 ms
[info] HashMapBenchmark.transformConserve                               10  avgt   20     15.104 ±    0.013   ns/op
[info] HashMapBenchmark.transformConserve:·gc.alloc.rate                10  avgt   20      0.001 ±    0.002  MB/sec
[info] HashMapBenchmark.transformConserve:·gc.alloc.rate.norm           10  avgt   20     ≈ 10⁻⁵               B/op
[info] HashMapBenchmark.transformConserve:·gc.count                     10  avgt   20        ≈ 0             counts
[info] HashMapBenchmark.transformConserve                              100  avgt   20    176.766 ±    0.472   ns/op
[info] HashMapBenchmark.transformConserve:·gc.alloc.rate               100  avgt   20      0.001 ±    0.002  MB/sec
[info] HashMapBenchmark.transformConserve:·gc.alloc.rate.norm          100  avgt   20     ≈ 10⁻⁴               B/op
[info] HashMapBenchmark.transformConserve:·gc.count                    100  avgt   20        ≈ 0             counts
[info] HashMapBenchmark.transformConserve                             1000  avgt   20   3624.239 ±   59.248   ns/op
[info] HashMapBenchmark.transformConserve:·gc.alloc.rate              1000  avgt   20      0.001 ±    0.002  MB/sec
[info] HashMapBenchmark.transformConserve:·gc.alloc.rate.norm         1000  avgt   20      0.006 ±    0.012    B/op
[info] HashMapBenchmark.transformConserve:·gc.count                   1000  avgt   20        ≈ 0             counts

@mkeskells

@hrhino hrhino added the performance the need for speed. usually compiler performance, sometimes runtime performance. label Jan 8, 2020
@scala-jenkins scala-jenkins added this to the 2.12.11 milestone Jan 8, 2020
@hrhino hrhino changed the title [nomerge] HashMap#transform reuses structure HashMap#transform reuses structure Jan 8, 2020
@diesalbla diesalbla added the library:collections PRs involving changes to the standard collection library label Jan 9, 2020
@hrhino hrhino force-pushed the topic/hashmap-transform branch from a3ac91f to bad3956 Compare January 12, 2020 00:47
m
}
protected override def transformImpl[W](f: (A, B) => W): HashMap[A, W] = {
new HashMapCollision1[A, W](hash, kvs map { case (k, v) => (k, f(k, v)) })
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

How about kvs.transform(f) since it's also a Map?

@lrytz
Copy link
Member

lrytz commented Jan 31, 2020

Needs a rebase (and there's an open review suggestion)

@hrhino
Copy link
Contributor Author

hrhino commented Jan 31, 2020

Thanks -- I'll see if I can get to this over the weekend

@hrhino hrhino force-pushed the topic/hashmap-transform branch from bad3956 to 6ea8da4 Compare January 31, 2020 22:49
@lrytz lrytz requested a review from szeiger February 3, 2020 09:04
@lrytz lrytz assigned szeiger and unassigned hrhino Feb 3, 2020
Copy link
Contributor

@szeiger szeiger left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

MiMa excludes need rebasing (as usual)

@hrhino
Copy link
Contributor Author

hrhino commented Feb 3, 2020

Aw, I just did that, too.

The keys in the resulting map are the same, so the internal structure
will also be the same, and that can be used to avoid allocating tuples
and going through `MapBuilder` and other such convolutions.
I thought som-snytt had recently gone on some sort of warning-cleanup
mission, but nowadays I can't compile 2.12.x without seeing scala tell
me off for these. Well, now I can.
@hrhino hrhino force-pushed the topic/hashmap-transform branch from b4c009d to 1cd3e74 Compare February 3, 2020 22:18
@SethTisue SethTisue changed the title HashMap#transform reuses structure [nomerge] HashMap#transform reuses structure Feb 4, 2020
@lrytz lrytz merged commit f15c544 into scala:2.12.x Feb 5, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

library:collections PRs involving changes to the standard collection library performance the need for speed. usually compiler performance, sometimes runtime performance.

Projects

None yet

Development

Successfully merging this pull request may close these issues.

5 participants