8000 Improve List.mapConserve to avoid ListBuffer creation (from @retronym) by mkeskells · Pull Request #5650 · scala/scala · GitHub
[go: up one dir, main page]
Skip to content

Improve List.mapConserve to avoid ListBuffer creation (from @retronym) #5650

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
Closed
wants to merge 2 commits into from
Closed

Improve List.mapConserve to avoid ListBuffer creation (from @retronym) #5650

wants to merge 2 commits into from

Conversation

mkeskells
Copy link
Contributor

No description provided.

@scala-jenkins scala-jenkins added this to the 2.11.9 milestone Jan 18, 2017
@Ichoran
Copy link
Contributor
Ichoran commented Jan 18, 2017

Does this change bring this code up to date with map2conserve or make them out of sync? (I.e. does it fix the comment at the top, or ignore it?)

@retronym
Copy link
Member
retronym commented Jan 20, 2017 •
edited
Loading

I've added a benchmark (which should be included in this PR) and compared results.

image

Before:

[info] Benchmark                            (size)  Mode  Cnt     Score     Error  Units
[info] ListBenchmark.mapConserve_identity        0  avgt   20     2.656 ±   0.354  ns/op
[info] ListBenchmark.mapConserve_identity       10  avgt   20    15.589 ±   0.145  ns/op
[info] ListBenchmark.mapConserve_identity      100  avgt   20   195.498 ±   2.324  ns/op
[info] ListBenchmark.mapConserve_identity     1000  avgt   20  2165.814 ±  89.139  ns/op
[info] ListBenchmark.mapConserve_modifyAll       0  avgt   20     2.445 ±   0.066  ns/op
[info] ListBenchmark.mapConserve_modifyAll      10  avgt   20    68.260 ±   0.838  ns/op
[info] ListBenchmark.mapConserve_modifyAll     100  avgt   20   524.424 ±   4.945  ns/op
[info] ListBenchmark.mapConserve_modifyAll    1000  avgt   20  7067.128 ± 519.275  ns/op
[info] ListBenchmark.mapConserve_modifyMid       0  avgt   20     3.350 ±  0.019  ns/op
[info] ListBenchmark.mapConserve_modifyMid      10  avgt   20    71.952 ±  0.280  ns/op
[info] ListBenchmark.mapConserve_modifyMid     100  avgt   20   657.063 ±  8.856  ns/op
[info] ListBenchmark.mapConserve_modifyMid    1000  avgt   20  6858.718 ± 54.507  ns/op

After:

[info] ListBenchmark.mapConserve_identity       0  avgt   20     3.340 ±   0.017  ns/op
[info] ListBenchmark.mapConserve_identity      10  avgt   20    21.260 ±   0.196  ns/op
[info] ListBenchmark.mapConserve_identity     100  avgt   20   275.763 ±   5.076  ns/op
[info] ListBenchmark.mapConserve_identity    1000  avgt   20  3065.572 ± 111.127  ns/op
[info] ListBenchmark.mapConserve_modifyMid       0  avgt   20     3.482 ±  0.164  ns/op
[info] ListBenchmark.mapConserve_modifyMid      10  avgt   20    65.579 ±  1.154  ns/op
[info] ListBenchmark.mapConserve_modifyMid     100  avgt   20   597.998 ± 12.235  ns/op
[info] ListBenchmark.mapConserve_modifyMid    1000  avgt   20  5304.799 ± 39.923  ns/op
[info] ListBenchmark.mapConserve_modifyAll       0  avgt   20     3.350 ±   0.019  ns/op
[info] ListBenchmark.mapConserve_modifyAll      10  avgt   20    60.710 ±   0.641  ns/op  
[info] ListBenchmark.mapConserve_modifyAll     100  avgt   20   517.202 ±   4.432  ns/op
[info] ListBenchmark.mapConserve_modifyAll    1000  avgt   20  5048.643 ± 136.316  ns/op  0.736x

This suggests a worthwhile improvement in the case where we avoid the ListBuffer use in favour of direct :: construction and tail mutation. But it also seems to show a slowdown in the case when an identity map is performed. We need to analyze why that happens.

@retronym
Copy link
Member

To run these benchmarks:

% cd /code/scala
% sbt 'set scalacOptions in Compile in ThisBuild += "-optimise"' dist/mkPack

% cd test/benchmark
% sbt 'jmh:run ListBenchmark.mapConserve.*'

test/benchmark contains a standalone SBT project, which can be imported into your IDE to make editing the benchmarks more pleasant.

@retronym retronym mentioned this pull request Jan 20, 2017
Closed
@rorygraves
Copy link
Contributor
rorygraves commented Jan 20, 2017 •
edited by SethTisue
Loading

@som-snytt No it does not update map2conserve at the moment - I will add that

@rorygraves rorygraves mentioned this pull request Jan 20, 2017
Closed
3 tasks
@szeiger
Copy link
Contributor
szeiger commented Jan 25, 2017

/rebuild

@szeiger
Copy link
Contributor
szeiger commented Jan 25, 2017

FYI: We intend to cut 2.11.9 on Friday. Any PR that hasn't been merged until then will get pushed down to 2.12.x. The build failure looks spurious so I have restarted the build. Judging by the benchmark results it seems we need further improvement or a better explanation of the results before we can merge this in order to avoid performance regressiosn.

@szeiger
Copy link
Contributor
szeiger commented Jan 26, 2017

I reran the benchmark on my machine with Java 1.8.0_102 and wasn't able to reproduce the large performance degradation for the identity case:

Before:

[info] Benchmark                            (size)  Mode  Cnt     Score    Error  Units
[info] ListBenchmark.mapConserve_identity        0  avgt   20     2.915 ±  0.038  ns/op
[info] ListBenchmark.mapConserve_identity       10  avgt   20    19.689 ±  0.183  ns/op
[info] ListBenchmark.mapConserve_identity      100  avgt   20   226.003 ±  1.811  ns/op
[info] ListBenchmark.mapConserve_identity     1000  avgt   20  2259.258 ± 27.563  ns/op
[info] ListBenchmark.mapConserve_modifyAll       0  avgt   20     2.914 ±  0.038  ns/op
[info] ListBenchmark.mapConserve_modifyAll      10  avgt   20    75.701 ±  0.431  ns/op
[info] ListBenchmark.mapConserve_modifyAll     100  avgt   20   706.565 ±  6.181  ns/op
[info] ListBenchmark.mapConserve_modifyAll    1000  avgt   20  6317.144 ± 48.521  ns/op
[info] ListBenchmark.mapConserve_modifyMid       0  avgt   20     2.934 ±  0.040  ns/op
[info] ListBenchmark.mapConserve_modifyMid      10  avgt   20    67.632 ±  0.848  ns/op
[info] ListBenchmark.mapConserve_modifyMid     100  avgt   20   547.612 ±  5.357  ns/op
[info] ListBenchmark.mapConserve_modifyMid    1000  avgt   20  5784.497 ± 52.744  ns/op

After:

[info] Benchmark                            (size)  Mode  Cnt     Score    Error  Units
[info] ListBenchmark.mapConserve_identity        0  avgt   20     2.944 ±  0.044  ns/op
[info] ListBenchmark.mapConserve_identity       10  avgt   20    18.813 ±  0.165  ns/op
[info] ListBenchmark.mapConserve_identity      100  avgt   20   227.325 ±  2.533  ns/op
[info] ListBenchmark.mapConserve_identity     1000  avgt   20  2371.588 ± 17.938  ns/op
[info] ListBenchmark.mapConserve_modifyAll       0  avgt   20     2.938 ±  0.039  ns/op
[info] ListBenchmark.mapConserve_modifyAll      10  avgt   20    49.515 ±  0.433  ns/op
[info] ListBenchmark.mapConserve_modifyAll     100  avgt   20   444.501 ±  4.037  ns/op
[info] ListBenchmark.mapConserve_modifyAll    1000  avgt   20  4010.906 ± 39.419  ns/op
[info] ListBenchmark.mapConserve_modifyMid       0  avgt   20     2.911 ±  0.029  ns/op
[info] ListBenchmark.mapConserve_modifyMid      10  avgt   20    50.977 ±  0.280  ns/op
[info] ListBenchmark.mapConserve_modifyMid     100  avgt   20   474.397 ±  2.767  ns/op
[info] ListBenchmark.mapConserve_modifyMid    1000  avgt   20  4238.298 ± 25.473  ns/op

I also tried some alternative implementations that were all slower than the one proposed here.

I think we should merge this (including the benchmark).

@rorygraves
Copy link
Contributor

@szeiger
Thanks
The benchmark file will conflict with the one in List.filter/filterNot - should I
a) wait until that has been merged and add the changes to the same file
b) put the benchmark in a separate file?

@szeiger
Copy link
Contributor
szeiger commented Jan 27, 2017

Let's use the same file name, it makes sense for both test cases. Once we merge this PR you can rebase the other one (which needs another update anyway) on top of it.

@adriaanm
Copy link
Contributor
adriaanm commented Jan 27, 2017 •
edited
Loading

I've bumped the deadline by a few days until Jan 31st. I would like to see as many of these 2.11.9 PRs merged as we can, but we do have to concentrate our efforts on 2.13 and 2.12 after that.

@rorygraves
Copy link
Contributor

great, i will try and get both my changes progressed over the weekend

@adriaanm adriaanm mentioned this pull request Jan 28, 2017
Merged
@adriaanm
Copy link
Contributor
adriaanm commented Jan 28, 2017 •
edited
Loading

See #5664 for a consolidated version with test and mima (coming next) fixes

@adriaanm
Copy link
Contributor

added your benchmark commit to #5664

@adriaanm
Copy link
Contributor
adriaanm commented Feb 2, 2017

Commits moved to #5664. Thanks!

@adriaanm adriaanm closed this Feb 2, 2017
@SethTisue SethTisue removed this from the 2.11.9 milestone Feb 17, 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
No milestone
Development

Successfully merging this pull request may close these issues.
8 participants
@mkeskells @Ichoran @retronym @rorygraves @szeiger @adriaanm @SethTisue @scala-jenkins
0