Skip to content

Optimize immutable.HashMap builder (inspired by the 2.13 implementation) #8726

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
retronym merged 2 commits into from
Apr 16, 2020
Merged

Optimize immutable.HashMap builder (inspired by the 2.13 implementation) #8726

retronym merged 2 commits into from
Apr 16, 2020

Conversation

@mkeskells
Copy link
Contributor

@mkeskells mkeskells commented Feb 18, 2020 •
edited by retronym
Loading

The builder allows TrieHashMap to be mutated in place until it is visible this reduces the memory churn while building Maps.

@scala-jenkins scala-jenkins added this to the 2.12.12 milestone Feb 18, 2020
@SethTisue SethTisue added the performance the need for speed. usually compiler performance, sometimes runtime performance. label Feb 18, 2020
@mkeskells mkeskells force-pushed the mike/2.12.x_hashMapBuilder branch from e397489 to f2d37cc Compare February 18, 2020 07:36
@mkeskells mkeskells changed the title [WIP] create a HashMap builder inspired by the 2.13 builder create a HashMap builder inspired by the 2.13 builder Feb 18, 2020
@diesalbla diesalbla added the library:collections PRs involving changes to the standard collection library label Feb 20, 2020
@mkeskells mkeskells force-pushed the mike/2.12.x_hashMapBuilder branch from 06af356 to 9ffb971 Compare February 20, 2020 14:54
retronym
retronym reviewed Feb 25, 2020
View reviewed changes
src/library/scala/collection/immutable/HashMap.scala

protected def filter0(p: ((A, B)) => Boolean, negate: Boolean, level: Int, buffer: Array[HashMap[A, B @uV]], offset0: Int): HashMap[A, B] = null

protected def elemHashCode(key: A) = key.##
Copy link
Member

@retronym retronym Feb 25, 2020

Choose a reason for hiding this comment

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

User defined element hashing was removed in 2.13 with a migration suggestion to use use wrapper classes for keys. But I don't think we can remove this in a minor release. Did you intend to include this diff in this PR?

Copy link
Contributor Author

@mkeskells mkeskells Feb 25, 2020

Choose a reason for hiding this comment

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

I didn't change the functionality her, just moved it to be in the object, as I needed the hashing from the builder

Is your concern the binary compat, or the functionality?
If the former, the methods can remain but be unused?

Copy link
Member

@retronym retronym Feb 26, 2020

Choose a reason for hiding this comment

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

The functionality. Admittedly it does not have test coverage but it is used a few times in the wild: https://github.com/search?q=%22override+def+elemHashCode%22&type=Code

Copy link
Contributor Author

@mkeskells mkeskells Mar 3, 2020

Choose a reason for hiding this comment

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

i have restored the extension point

@retronym
Copy link
Member

retronym commented Feb 26, 2020

Echoing my comments on #8722, this change will be targetted to 2.12.12.

retronym
retronym reviewed Mar 2, 2020
View reviewed changes
src/library/scala/collection/immutable/HashMap.scala
trie
}
case _ => hs
}
Copy link
Member

@retronym retronym Mar 2, 2020

Choose a reason for hiding this comment

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

We should call ScalaRuntime.releaseFence (which will itself need to be backported but made private[scala]) here.

Copy link
Member

@retronym retronym Mar 20, 2020

Choose a reason for hiding this comment

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

@mkeskells I just merged #8779 so you could now add s.c.i.VM.releaseFence() to this and #8722 in the same places as 2.13.x.

@retronym retronym mentioned this pull request Mar 2, 2020
Merged
@mkeskells mkeskells mentioned this pull request Mar 3, 2020
Closed
@mkeskells mkeskells force-pushed the mike/2.12.x_hashMapBuilder branch from 828b587 to 7c147e2 Compare March 4, 2020 00:28
@mkeskells
Copy link
Contributor Author

mkeskells commented Mar 9, 2020

squashed

@mkeskells mkeskells force-pushed the mike/2.12.x_hashMapBuilder branch from 7c147e2 to b830eab Compare March 9, 2020 18:12
@mkeskells mkeskells force-pushed the mike/2.12.x_hashMapBuilder branch from b830eab to 0e310c3 Compare March 22, 2020 18:54
@retronym retronym force-pushed the mike/2.12.x_hashMapBuilder branch from 0e310c3 to 0a18c32 Compare April 15, 2020 01:04
@mkeskells @retronym
Create a HashMap builder with limited mutability
f38b35a 
The builder allows TrieHashMap to be mutated in place until it is visible
this reduces the memory churn while building Maps
@mkeskells @retronym
Add a releaseFence before the builder publishes result
9460890
@retronym retronym force-pushed the mike/2.12.x_hashMapBuilder branch from 0a18c32 to 9460890 Compare April 15, 2020 01:20
@retronym retronym merged commit bfa40a5 into scala:2.12.x Apr 16, 2020
@sjrd sjrd mentioned this pull request Apr 25, 2020
Closed
@retronym retronym mentioned this pull request Apr 28, 2020
Merged
@retronym retronym mentioned this pull request Jul 2, 2020
Closed
65 tasks
@retronym retronym changed the title create a HashMap builder inspired by the 2.13 builder Optimize HashMap builder inspired by the 2.13 builder Jul 2, 2020
@retronym retronym changed the title Optimize HashMap builder inspired by the 2.13 builder Optimize HashMap builder (inspired by the 2.13 implementation) Jul 2, 2020
@retronym retronym changed the title Optimize HashMap builder (inspired by the 2.13 implementation) Optimize immutable.HashMap builder (inspired by the 2.13 implementation) Jul 2, 2020
@retronym retronym added the release-notes worth highlighting in next release notes label Jul 2, 2020
@retronym retronym mentioned this pull request Oct 2, 2020
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@retronym retronym retronym approved these changes

Assignees

No one assigned

Labels

library:collections PRs involving changes to the standard collection library performance the need for speed. usually compiler performance, sometimes runtime performance. release-notes worth highlighting in next release notes

Projects

None yet

Milestone

2.12.12

Development

Successfully merging this pull request may close these issues.

5 participants

@mkeskells @retronym @SethTisue @scala-jenkins @diesalbla