Skip to content

TreeMap#keySet does no copying by only transferring inner Tree to TreeSet #7579

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 13, 2019
Merged

TreeMap#keySet does no copying by only transferring inner Tree to TreeSet #7579

Ichoran merged 1 commit into from
Jan 13, 2019

Conversation

@joshlemer
Copy link
Contributor

@joshlemer joshlemer commented Dec 27, 2018 •
edited
Loading

TreeMap#keySet currently will create a new Set which, when modified, will trigger a full deep copy of the map keys into a new Set.

Instead, we change TreeSet to have an underlying tree of type Tree[A, Any] rather than Tree[A, Null], and simply ignore any values stored in the Anys. This essentially turns TreeMap#keySet into a no-op.

Potential reasons not to allow this

  • Since the values are not being "zeroed out", they will not be garbage collected. Though if this is a serious concern, maybe we could add a scaladoc explaining that if you want the values to be GC'd, do something like treeMap.iterator.to(TreeSet)

Benchmarks!

  • the following benchmarks benchmark the behaviour of:
    • treeMap.keySet - existingValue
    • treeMap.keySet + newValue
    • treeMap.oldKeySet - existingValue
    • treeMap.oldKeySet + newValue
[info] Benchmark                      (size)  Mode  Cnt        Score        Error  Units
[info] MapBenchmark.keyset_excl            0  avgt    6       19.006 ±      2.532  ns/op
[info] MapBenchmark.keyset_excl           10  avgt    6       75.278 ±      9.936  ns/op
[info] MapBenchmark.keyset_excl         1000  avgt    6      179.175 ±     23.782  ns/op
[info] MapBenchmark.keyset_excl        10000  avgt    6      237.307 ±     23.803  ns/op
[info] MapBenchmark.keyset_excl       100000  avgt    6      298.336 ±     59.395  ns/op
[info] MapBenchmark.keyset_excl      1000000  avgt    6      370.251 ±     56.013  ns/op
[info] MapBenchmark.keyset_incl            0  avgt    6       22.552 ±      0.750  ns/op
[info] MapBenchmark.keyset_incl           10  avgt    6       35.853 ±      2.382  ns/op
[info] MapBenchmark.keyset_incl         1000  avgt    6       87.752 ±      6.868  ns/op
[info] MapBenchmark.keyset_incl        10000  avgt    6      114.505 ±      2.039  ns/op
[info] MapBenchmark.keyset_incl       100000  avgt    6      141.777 ±      2.068  ns/op
[info] MapBenchmark.keyset_incl      1000000  avgt    6      170.921 ±      2.001  ns/op
[info] MapBenchmark.old_keyset_excl        0  avgt    6       84.470 ±      3.612  ns/op
[info] MapBenchmark.old_keyset_excl       10  avgt    6      261.250 ±     13.085  ns/op
[info] MapBenchmark.old_keyset_excl     1000  avgt    6     7920.724 ±     51.274  ns/op
[info] MapBenchmark.old_keyset_excl    10000  avgt    6    97249.755 ±   1040.499  ns/op
[info] MapBenchmark.old_keyset_excl   100000  avgt    6  1053655.934 ±  20767.632  ns/op
[info] MapBenchmark.old_keyset_excl  1000000  avgt    6  9570122.164 ± 224791.632  ns/op
[info] MapBenchmark.old_keyset_incl        0  avgt    6       90.871 ±      2.222  ns/op
[info] MapBenchmark.old_keyset_incl       10  avgt    6      172.646 ±      2.270  ns/op
[info] MapBenchmark.old_keyset_incl     1000  avgt    6     7787.613 ±    279.998  ns/op
[info] MapBenchmark.old_keyset_incl    10000  avgt    6    96754.475 ±   3025.751  ns/op
[info] MapBenchmark.old_keyset_incl   100000  avgt    6  1162963.769 ±  35115.460  ns/op
[info] MapBenchmark.old_keyset_incl  1000000  avgt    6  9498622.033 ± 116221.941  ns/op

@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 27, 2018
@joshlemer joshlemer mentioned this pull request Dec 27, 2018
Merged
1 task
@NthPortal NthPortal mentioned this pull request Dec 27, 2018
Closed
@joshlemer joshlemer changed the title TreeMap#keySet creates a TreeSet TreeMap#keySet does no copying by only transferring inner Tree to TreeSet Dec 27, 2018
@adriaanm

This comment has been minimized.

Sign in to view
@adriaanm

This comment has been minimized.

Sign in to view
@scala-jenkins scala-jenkins added this to the 2.13.0-RC1 milestone Dec 27, 2018
@adriaanm

This comment has been minimized.

Sign in to view
2 similar comments
@adriaanm

This comment has been minimized.

Sign in to view
@adriaanm

This comment has been minimized.

Sign in to view
szeiger
szeiger approved these changes Jan 4, 2019
View reviewed changes
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.

The existing semantics of when to drop the values are very much an implementation detail. Most importantly, the default implementation does not drop the values when you create the key set, only on some subsequent modifications of that set, so this implementation is not too different.

@Ichoran Ichoran self-assigned this Jan 10, 2019
Ichoran
Ichoran approved these changes Jan 13, 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.

This is arguably how it should have been done anyway (any map is viewable as a set), and the implementation is simple. LGTM!

@Ichoran Ichoran merged commit a6c09e5 into scala:2.13.x Jan 13, 2019
@joshlemer joshlemer deleted the treemap-keyset branch January 13, 2019 01:23
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@julienrf julienrf Awaiting requested review from julienrf

2 more reviewers

@szeiger szeiger szeiger approved these changes

@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.

Projects

None yet

Milestone

2.13.0-RC1

Development

Successfully merging this pull request may close these issues.

5 participants

@joshlemer @adriaanm @szeiger @Ichoran @scala-jenkins