Skip to content

✨ Implement ImmutableSegmentedHashSet<T>#54719

Merged
sharwell merged 9 commits intodotnet:mainfrom
sharwell:immutable-segmented-hashset
Jun 28, 2022
Merged

✨ Implement ImmutableSegmentedHashSet<T>#54719
sharwell merged 9 commits intodotnet:mainfrom
sharwell:immutable-segmented-hashset

Conversation

@sharwell
Copy link
Copy Markdown
Contributor

@sharwell sharwell commented Jul 9, 2021

Builds on #54574

@ghost ghost added the Area-Compilers label Jul 9, 2021
@sharwell sharwell force-pushed the immutable-segmented-hashset branch from a3df5bf to 0ca55e6 Compare July 9, 2021 20:38
@sharwell sharwell mentioned this pull request Aug 17, 2021
Merged
@sharwell sharwell marked this pull request as ready for review May 13, 2022 22:19
@sharwell sharwell requested a review from a team as a code owner May 13, 2022 22:19
@sharwell
Copy link
Copy Markdown
Contributor Author

sharwell commented May 13, 2022

@dotnet/roslyn-compiler this is now ready for review

333fred
333fred reviewed May 17, 2022
View reviewed changes
src/Dependencies/Collections/ImmutableSegmentedHashSet`1.cs
}
else
{
// TODO: Avoid the builder allocation
Copy link
Copy Markdown
Member

@333fred 333fred May 17, 2022

Choose a reason for hiding this comment

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

Are these todo's from the original source?

Copy link
Copy Markdown
Contributor Author

@sharwell sharwell May 17, 2022

Choose a reason for hiding this comment

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

No, these are ways the current implementation could theoretically be improved. My hope is that if someone sees allocations of certain types in the future, they are directed to the most straightforward way to eliminate those allocations.

Copy link
Copy Markdown
Contributor Author

@sharwell sharwell May 17, 2022 •
edited
Loading

Choose a reason for hiding this comment

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

Here's an example of how I broke out a ValueBuilder nested type to reduce builder allocations in ImmutableSegmentedList<T>:
#54424
https://github.com/dotnet/roslyn/blob/main/src/Dependencies/Collections/ImmutableSegmentedList%601%2BValueBuilder.cs

@sharwell
Copy link
Copy Markdown
Contributor Author

sharwell commented May 19, 2022

@dotnet/roslyn-compiler for second review

4 similar comments
@sharwell
Copy link
Copy Markdown
Contributor Author

sharwell commented Jun 3, 2022

@dotnet/roslyn-compiler for second review

@sharwell
Copy link
Copy Markdown
Contributor Author

sharwell commented Jun 6, 2022

@dotnet/roslyn-compiler for second review

@sharwell
Copy link
Copy Markdown
Contributor Author

sharwell commented Jun 22, 2022 •
edited
Loading

@dotnet/roslyn-compiler for second review

@sharwell
Copy link
Copy Markdown
Contributor Author

sharwell commented Jun 27, 2022

@dotnet/roslyn-compiler for second review

@jaredpar
Copy link
Copy Markdown
Member

jaredpar commented Jun 27, 2022

How can we see the delta from what the BCL sources were to what you added as a part of moving to Roslyn? I'm less interested in reviewing the BCL sources (battle tested, already reviewed, etc ...). Think it's more interesting for us to look at the delta to see what has changed and evaluate that.

@sharwell
Copy link
Copy Markdown
Contributor Author

sharwell commented Jun 27, 2022 •
edited
Loading

@jaredpar There is no exact mirror for this type in the BCL. The closest we have is the AVL-backed ImmutableHashSet<T>, so a close review would involve comparing the API defined in 1126d19 against the related original type (to show it's a drop-in replacement). In this case, the sources copied from runtime are the test cases for ImmutableHashSet<T> which were updated in 03c2ae7 to execute against the new data type and followed by a2023ec to get the tests fully passing against the new structure.

Note that I followed the pattern from earlier immutable types in this library and made ImmutableSegmentedHashSet<T> a value type to avoid a significant number of small allocations in common use cases.

jaredpar
jaredpar approved these changes Jun 28, 2022
View reviewed changes
src/Dependencies/Collections/ImmutableSegmentedHashSet`1.cs
/// <inheritdoc cref="ImmutableHashSet{T}.Clear()"/>
public ImmutableSegmentedHashSet<T> Clear()
{
var self = this;
Copy link
Copy Markdown
Member

@jaredpar jaredpar Jun 28, 2022

Choose a reason for hiding this comment

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

Unsure what the goal of this pattern is here. Can you elaborate?

I can only see this being of value if you're protecting against mixed read / writes of this value in a location. Don't think we generally protect against incorrect uses like that.

Copy link
Copy Markdown
Contributor Author

@sharwell sharwell Jun 28, 2022

Choose a reason for hiding this comment

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

Good catch. This type appears to be missing the equivalent of this notice which is applied to ImmutableSegmentedList<T>:

roslyn/src/Dependencies/Collections/ImmutableSegmentedList`1.cs

Lines 59 to 69 in 519058e

/// <para><strong>IMPORTANT NOTICE FOR MAINTAINERS AND REVIEWERS:</strong></para>
///
/// <para>This type should be thread-safe. As a struct, it cannot protect its own fields from being changed from one
/// thread while its members are executing on other threads because structs can change <em>in place</em> simply by
/// reassigning the field containing this struct. Therefore it is extremely important that <strong>⚠⚠ Every member
/// should only dereference <c>this</c> ONCE ⚠⚠</strong>. If a member needs to reference the
/// <see cref="_list"/> field, that counts as a dereference of <c>this</c>. Calling other instance members
/// (properties or methods) also counts as dereferencing <c>this</c>. Any member that needs to use <c>this</c> more
/// than once must instead assign <c>this</c> to a local variable and use that for the rest of the code instead.
/// This effectively copies the one field in the struct to a local variable so that it is insulated from other
/// threads.</para>

Copy link
Copy Markdown
Contributor Author

@sharwell sharwell Jun 28, 2022

Choose a reason for hiding this comment

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

I'll file a follow-up issue to add this documentation and implement the value builder.

@sharwell sharwell merged commit 9f9599c into dotnet:main Jun 28, 2022
@sharwell sharwell deleted the immutable-segmented-hashset branch June 28, 2022 15:45
@ghost ghost added this to the Next milestone Jun 28, 2022
@RikkiGibson RikkiGibson modified the milestones: Next, 17.3 P3 Jun 28, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@jaredpar jaredpar jaredpar approved these changes

@333fred 333fred 333fred approved these changes

Assignees

No one assigned

Labels

Area-Compilers

Projects

None yet

Milestone

17.3 P3

Development

Successfully merging this pull request may close these issues.

4 participants

@sharwell @jaredpar @333fred @RikkiGibson