Skip to content

Apply consistent rules for key & value identities to maps and sets#7481

Merged
lrytz merged 1 commit intoscala:2.13.xfrom
szeiger:issue/10415
Dec 13, 2018
Merged

Apply consistent rules for key & value identities to maps and sets#7481
lrytz merged 1 commit intoscala:2.13.xfrom
szeiger:issue/10415

Conversation

@szeiger
Copy link
Contributor

@szeiger szeiger commented Nov 30, 2018

The rules are listed in SetMapRulesTest. All collections changes
are necessary to comply with rule 3 (key identity). The other rules
were not violated by any of the tested collections.

Fixes scala/bug#10415

There may be more elegant or efficient ways to fix some of the collections but I wanted to get this out before the weekend for some feedback. I fixed the following collections:

  • immutable.HashMap and immutable.HashSet may be slightly faster now
  • mutable.ListMap, mutable.AnyRefMap and immutable.ListMap could be slightly slower
  • concurrent.TrieMap and immutable.TreeMap should not show any effects on performance

Someone should look over the changes I made to TrieMap and AnyRefMap because I am not very familiar with these. The rest was quite straight-forward.

@scala-jenkins scala-jenkins added this to the 2.13.0-RC1 milestone Nov 30, 2018
@szeiger
Copy link
Contributor Author

szeiger commented Dec 3, 2018

@Ichoran I've added an inline annotation to seekEntryOrOpen. I considered manually inlining this method into put and update but the new inliner does a great job eliminating the tupling:

Original:

[info] Benchmark                (size)  (useMissingValues)  Mode  Cnt      Score     Error  Units
[info] AnyRefMapBenchmark.fill      10                true  avgt   20    234.641 ±   2.576  ns/op
[info] AnyRefMapBenchmark.fill     100                true  avgt   20   2328.181 ±  19.862  ns/op
[info] AnyRefMapBenchmark.fill    1000                true  avgt   20  23676.248 ± 272.549  ns/op

inline seekEntryOrOpen:

[info] Benchmark                (size)  (useMissingValues)  Mode  Cnt      Score     Error  Units
[info] AnyRefMapBenchmark.fill      10                true  avgt   20    227.960 ±   2.043  ns/op
[info] AnyRefMapBenchmark.fill     100                true  avgt   20   2311.559 ±  23.751  ns/op
[info] AnyRefMapBenchmark.fill    1000                true  avgt   20  23401.286 ± 392.441  ns/op

Simple fix (from the old version of this PR):

[info] Benchmark                (size)  (useMissingValues)  Mode  Cnt      Score      Error  Units
[info] AnyRefMapBenchmark.fill      10                true  avgt   20    308.712 ±    4.337  ns/op
[info] AnyRefMapBenchmark.fill     100                true  avgt   20   2735.503 ±   43.035  ns/op
[info] AnyRefMapBenchmark.fill    1000                true  avgt   20  29704.216 ± 2351.367  ns/op

Simple fix with inline seekEntryOrOpen:

[info] Benchmark                (size)  (useMissingValues)  Mode  Cnt      Score     Error  Units
[info] AnyRefMapBenchmark.fill      10                true  avgt   20    227.303 ±   1.501  ns/op
[info] AnyRefMapBenchmark.fill     100                true  avgt   20   2311.302 ±  18.597  ns/op
[info] AnyRefMapBenchmark.fill    1000                true  avgt   20  24248.815 ± 760.500  ns/op

@Ichoran
Copy link
Contributor

Ichoran commented Dec 3, 2018

That's encouraging! I'm not sure the tupling clarifies rather than confuses the logic, though, given the other places that bit inspection is used. The various ._1 are not terribly accessible because you have to go see what ._1 is, while the returned index always has bits set in it.

@szeiger szeiger added the library:collections PRs involving changes to the standard collection library label Dec 11, 2018
lrytz
lrytz approved these changes Dec 12, 2018
View reviewed changes
Copy link
Member

@lrytz lrytz left a comment

Choose a reason for hiding this comment

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

Looks good!

@szeiger
Apply consistent rules for key & value identities to maps and sets
df69eb8 
The rules are listed in `SetMapRulesTest`. All collections changes
are necessary to comply with rule 3 (key identity). The other rules
were not violated by any of the tested collections.

Fixes scala/bug#10415
@szeiger
Copy link
Contributor Author

szeiger commented Dec 12, 2018

@Ichoran I think I understand what you mean. I didn't really look at the various bits too closely before. I've updated the code to make use of the returned bits so we don't need to get the old key at all.

lrytz
lrytz reviewed Dec 13, 2018
View reviewed changes
@lrytz lrytz merged commit ca209e9 into scala:2.13.x Dec 13, 2018
@lrytz lrytz mentioned this pull request May 2, 2019
Closed
szeiger added a commit to szeiger/scala that referenced this pull request Mar 3, 2020
@szeiger
Don't check key equality in RedBlackTree
529e0e4 
This was left over from 2.12 when they old key would be overwritten.
The behavior changed in scala#7481 to
comply with the new map/set rules in
scala/bug#10415 (comment).

I would also call it wrong in 2.12 because equality should be defined
exclusively by the Ordering, but we should keep the current behavior
for compatibility reasons.
@szeiger szeiger mentioned this pull request Mar 3, 2020
Merged
retronym added a commit to retronym/scala that referenced this pull request May 20, 2020
@retronym
[nomerge] Revert backported RBTree changes that are 2.13.x only
8e95fea 
Changes from:

   scala#7481
   scala#8783

Backported in:

scala@b87dd51#diff-f99536a3327e638dcf239518f2c3f0ceR195
scala@93afae7#diff-f99536a3327e638dcf239518f2c3f0ceL214

... are reverted. I've added a test for the legacy behaviour
that we don't want to break.
@retronym retronym mentioned this pull request May 20, 2020
Merged
hamzaremmal pushed a commit to hamzaremmal/scala3 that referenced this pull request May 2, 2025
@szeiger
Don't check key equality in RedBlackTree
1cb8440 
This was left over from 2.12 when they old key would be overwritten.
The behavior changed in scala/scala#7481 to
comply with the new map/set rules in
scala/bug#10415 (comment).

I would also call it wrong in 2.12 because equality should be defined
exclusively by the Ordering, but we should keep the current behavior
for compatibility reasons.
hamzaremmal pushed a commit to hamzaremmal/scala3 that referenced this pull request May 2, 2025
@retronym
[nomerge] Revert backported RBTree changes that are 2.13.x only
00c31a7 
Changes from:

   scala/scala#7481
   scala/scala#8783

Backported in:

scala/scala@3b637df#diff-f99536a3327e638dcf239518f2c3f0ceR195
scala/scala@1b39caf#diff-f99536a3327e638dcf239518f2c3f0ceL214

... are reverted. I've added a test for the legacy behaviour
that we don't want to break.
hamzaremmal pushed a commit to scala/scala3 that referenced this pull request May 7, 2025
@szeiger
Don't check key equality in RedBlackTree
7264856 
This was left over from 2.12 when they old key would be overwritten.
The behavior changed in scala/scala#7481 to
comply with the new map/set rules in
scala/bug#10415 (comment).

I would also call it wrong in 2.12 because equality should be defined
exclusively by the Ordering, but we should keep the current behavior
for compatibility reasons.
hamzaremmal pushed a commit to scala/scala3 that referenced this pull request May 7, 2025
@retronym
[nomerge] Revert backported RBTree changes that are 2.13.x only
d93c379 
Changes from:

   scala/scala#7481
   scala/scala#8783

Backported in:

scala/scala@9bfb183#diff-f99536a3327e638dcf239518f2c3f0ceR195
scala/scala@48809df#diff-f99536a3327e638dcf239518f2c3f0ceL214

... are reverted. I've added a test for the legacy behaviour
that we don't want to break.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@lrytz lrytz lrytz approved these changes

Assignees

No one assigned

Labels

library:collections PRs involving changes to the standard collection library

Projects

None yet

Milestone

2.13.0-RC1

Development

Successfully merging this pull request may close these issues.

Immutable maps have inconsistent behaviour on update

4 participants

@szeiger @Ichoran @lrytz @scala-jenkins