Skip to content

[11296] implement mutating VectorMapBuilder #7508

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
Ichoran merged 1 commit into from
Jan 12, 2019
Merged

[11296] implement mutating VectorMapBuilder #7508

Ichoran merged 1 commit into from
Jan 12, 2019

Conversation

@joshlemer
Copy link
Contributor

@joshlemer joshlemer commented Dec 9, 2018 •
edited
Loading

This is a partial fix for scala/bug#11296

Summary:

  • MapBuilderImpl and HashMapBuilder expose

    • def getOrElse[V0 >: V](key: K, value: V0): V0
      • this method is used in VectorMapBuilder
    • def addOne(key: K, value: V): this.type
      • also used in VectorMapBuilder
    • Both of these classes are private[immutable] so public api is not changed

  • new private[immutable] VectorMapBuilder is implemented which delegates to an underlying VectorBuilder and MapBuilder, then builds the result on result() calls. After one result call is made, further additions to the VectorBuilder fall back to immutable updates.

Benchmarks


[info] # Run complete. Total time: 00:07:52
[info] Benchmark                       (size)  Mode  Cnt           Score           Error  Units
[info] VectorMapBenchmark.newBuilder        1  avgt   20         194.294 ±        48.158  ns/op
[info] VectorMapBenchmark.newBuilder       10  avgt   20        1310.853 ±        70.853  ns/op
[info] VectorMapBenchmark.newBuilder      100  avgt   20       17957.492 ±      3096.264  ns/op
[info] VectorMapBenchmark.newBuilder     1000  avgt   20      285058.415 ±     74489.514  ns/op
[info] VectorMapBenchmark.newBuilder  1000000  avgt   20   994031624.475 ±  35092489.752  ns/op
[info] VectorMapBenchmark.oldBuilder        1  avgt   20         508.492 ±         8.691  ns/op
[info] VectorMapBenchmark.oldBuilder       10  avgt   20        5405.426 ±      5472.874  ns/op
[info] VectorMapBenchmark.oldBuilder      100  avgt   20      419727.318 ±    378794.168  ns/op
[info] VectorMapBenchmark.oldBuilder     1000  avgt   20      560260.095 ±     50140.120  ns/op
[info] VectorMapBenchmark.oldBuilder  1000000  avgt   20  1822695595.250 ± 144192596.555  ns/op

Benchmark TL;DR

Typically ~ 60% reduction in CPU time.

@scala-jenkins scala-jenkins added this to the 2.13.0-RC1 milestone Dec 9, 2018
@joshlemer joshlemer force-pushed the issue/11297-seqmap-builders branch 3 times, most recently from 565859e to 62452b4 Compare December 9, 2018 22:44
@joshlemer joshlemer added performance the need for speed. usually compiler performance, sometimes runtime performance. library:collections PRs involving changes to the standard collection library labels Dec 10, 2018
@joshlemer joshlemer force-pushed the issue/11297-seqmap-builders branch from 62452b4 to a7fc6df Compare December 10, 2018 04:24
@joshlemer joshlemer changed the title [11297] implement mutating VectorMapBuilder [11296] implement mutating VectorMapBuilder Dec 10, 2018
@joshlemer joshlemer mentioned this pull request Jan 3, 2019
Merged
@joshlemer joshlemer requested a review from szeiger January 8, 2019 13:59
@Ichoran Ichoran self-assigned this Jan 10, 2019
@joshlemer joshlemer added prio:blocker release blocker (used only by core team, only near release time) prio:hi high priority (used only by core team, only near release time) labels Jan 11, 2019
@joshlemer
Copy link
Contributor Author

joshlemer commented Jan 11, 2019

I hope @SethTisue won't mind that I've labeled this is high priority, because it is currently blocking the pretty major decision of which SeqMap implementation should be default or even included, in 2.13

Why? Because this speedup is of such high magnitude and affects so many transformations (map, filter, etc etc) that the previously measured benchmarks are going to probably have very different results.

@Ichoran
Copy link
Contributor

Ichoran commented Jan 11, 2019

I'll get to it as soon as I can (which is Saturday). I agree it's critical.

Ichoran
Ichoran approved these changes Jan 12, 2019
View reviewed changes
Copy link
Contributor

@Ichoran Ichoran left a comment

Choose a reason for hiding this comment

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

Looks fine to me. The code looks good; I could come up with fiddly changes that might make it slightly better but it's well over the bar of "good to merge" so it's better to just go with it, following the principle of "the great should not be the enemy of the good".

@Ichoran Ichoran merged commit 105c187 into scala:2.13.x Jan 12, 2019
@joshlemer joshlemer deleted the issue/11297-seqmap-builders branch January 14, 2019 18:41
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@szeiger szeiger Awaiting requested review from szeiger

1 more reviewer

@Ichoran Ichoran Ichoran approved these changes

Reviewers whose approvals may not affect merge requirements

Assignees

@Ichoran Ichoran

Labels

library:collections PRs involving changes to the standard collection library performance the need for speed. usually compiler performance, sometimes runtime performance. prio:blocker release blocker (used only by core team, only near release time) prio:hi high priority (used only by core team, only near release time)

Projects

None yet

Milestone

2.13.0-RC1

Development

Successfully merging this pull request may close these issues.

3 participants

@joshlemer @Ichoran @scala-jenkins