✨ Implement SegmentedHashSet<T> by sharwell · Pull Request #54574 · dotnet/roslyn

sharwell · 2021-07-02T21:56:55Z

This is a drop-in replacement for HashSet<T>, with equivalent semantics and algorithmic complexity but does not require the use of the Large Object Heap.

These files are based on dotnet/runtime@556582d9 (v5.0.7).

… and non-randomized string comparers

sharwell · 2021-08-13T16:15:57Z

@dotnet/roslyn-compiler for reviews

sharwell · 2021-08-23T16:28:40Z

@dotnet/roslyn-compiler for reviews

sharwell · 2021-08-25T23:01:15Z

@dotnet/roslyn-compiler for reviews

sharwell · 2021-10-15T15:26:25Z

@dotnet/roslyn-compiler for reviews

Therzok · 2021-10-15T22:44:11Z

src/Dependencies/Collections/Internal/SegmentedHashSetEqualityComparer`1.cs

+
+        public int GetHashCode(SegmentedHashSet<T>? obj)
+        {
+            var hashCode = 0; // default to 0 for null/empty set


Would System.HashCode be a good fit here here?

➡️ This implementation is taken from the link at the top of the file, and only changed where necessary to build in Roslyn. The original code for this method does not use System.HashCode, so this question is probably better for dotnet/runtime.

Youssef1313 · 2022-01-22T10:11:46Z

src/Dependencies/Collections/SegmentedHashSet`1.cs

+        {
+            if (collection == null)
+            {
+                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);


Why this is not nameof(collection) (applies to all ExceptionArgument usages)

➡️ This implementation is taken from the link at the top of the file, and only changed where necessary to build in Roslyn. The original code for this method does not use nameof(collection), so this question is probably better for dotnet/runtime.

Youssef1313 · 2022-01-22T13:08:13Z

src/Dependencies/Collections/Internal/SegmentedHashSetEqualityComparer`1.cs

+        }
+
+        // Equals method for the comparer itself.
+        public override bool Equals(object? obj) => obj is SegmentedHashSetEqualityComparer<T>;


Suggested change

public override bool Equals(object? obj) => obj is SegmentedHashSetEqualityComparer<T>;

public override bool Equals([NotNullWhen(true)] object? obj) => obj is SegmentedHashSetEqualityComparer<T>;

This was added in dotnet/runtime:

https://github.com/dotnet/runtime/blob/64245ab3966abde394767fbd6531e7edbea2802e/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/HashSetEqualityComparer.cs#L75

Note: requires using System.Diagnostics.CodeAnalysis;

➡️ This implementation is taken from the link at the top of this file. The 5.0.7 tag does not contain this attribute; it will be added during the update step if/when a newer version is adopted.

RikkiGibson · 2022-01-29T01:29:47Z

src/Dependencies/Collections/SegmentedHashSet`1.cs

-                }
-                else if (ReferenceEquals(_comparer, StringComparer.OrdinalIgnoreCase))
-                {
-                    _comparer = (IEqualityComparer<T>)NonRandomizedStringEqualityComparer.WrappedAroundStringComparerOrdinalIgnoreCase;


Why were these special cases eliminated?

They require porting a huge amount of platform-specific culture code. The same change was adopted for SegmentedDictionary<TKey, TValue>.

RikkiGibson · 2022-01-29T01:42:52Z

It looks like the important commit here is c0c39b1.

sharwell · 2022-05-11T19:52:55Z

@dotnet/roslyn-compiler for second review

jaredpar · 2022-05-11T21:59:56Z

src/Dependencies/Collections/Internal/SegmentedHashSetEqualityComparer`1.cs

+                return false;
+            }
+
+            var defaultComparer = EqualityComparer<T>.Default;


Could move this to line 33 to avoid .Default on unnecessary code paths

I would typically avoid this primarily so we can keep the file as close to the reference source as possible (i.e. if the code changes in dotnet/runtime, we would adopt that change in the next update here per the link in the comment at the top of the file).

jaredpar · 2022-05-11T22:01:23Z

src/Dependencies/Collections/Internal/SegmentedHashSetEqualityComparer`1.cs

+                }
+            }
+
+            return true;


What if x has every element in y and one additional element? That will pass the test above and fall through to return true even though the x has more elements.

I'm not sure what the expected behavior here. This is not documented on docs.microsoft.com for HashSet<T>.CreateSetComparer(), and is the same behavior seen here:
https://github.com/dotnet/runtime/blob/6ca8c9bc0c4a5fc1082c690b6768ab3be8761b11/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/HashSetEqualityComparer.cs#L25-L51

This just seems like a bug in the original source code.

dotnet/runtime#69218

Can we reference that bug here? If they decide to fix that in their source we can follow up with a fix here.

See dotnet/runtime#69218

sharwell added 11 commits July 2, 2021 14:54

Add HashSet<T> and supporting files

9c0e051

These files are based on dotnet/runtime@556582d9 (v5.0.7).

Add origin notes

fa322ff

Rename type to SegmentedHashSet<T>

17617c7

Remove serialization support

3fd3edf

Remove requirement that the runtime support comparer devirtualization…

1687001

… and non-randomized string comparers

Fix code style diagnostics (except naming)

e1ed6d7

Fix naming code style diagnostics

57f3561

Clean up remaining build errors

88fb7f4

Assume TARGET_64BIT for performance

677b2be

Use segmented arrays internally

c0c39b1

Update tests for SegmentedHashSet<T>

0bbcabb

sharwell requested a review from a team as a code owner July 2, 2021 21:56

ghost added the Area-Compilers label Jul 2, 2021

sharwell mentioned this pull request Jul 9, 2021

✨ Implement ImmutableSegmentedHashSet<T> #54719

Merged

dotnet deleted a comment from azure-pipelines bot Jul 30, 2021

dotnet deleted a comment from azure-pipelines bot Aug 13, 2021

sharwell mentioned this pull request Aug 17, 2021

Enable Microsoft.CodeAnalysis.Collections dotnet/msbuild#6595

Merged

RikkiGibson self-assigned this Aug 25, 2021

Therzok reviewed Oct 15, 2021

View reviewed changes

Youssef1313 reviewed Jan 22, 2022

View reviewed changes

RikkiGibson reviewed Jan 29, 2022

View reviewed changes

RikkiGibson approved these changes Jan 29, 2022

View reviewed changes

dotnet deleted a comment from azure-pipelines bot May 11, 2022

jaredpar reviewed May 11, 2022

View reviewed changes

jaredpar approved these changes May 11, 2022

View reviewed changes

Add link to runtime bug regarding non-symmetry of set comparer

ff93309

See dotnet/runtime#69218

sharwell enabled auto-merge May 12, 2022 14:16

sharwell merged commit ef54147 into dotnet:main May 12, 2022

ghost added this to the Next milestone May 12, 2022

sharwell deleted the segmented-hashset branch May 12, 2022 18:43

Cosifne modified the milestones: Next, 17.3 P2 May 31, 2022

	public override bool Equals(object? obj) => obj is SegmentedHashSetEqualityComparer<T>;
	public override bool Equals([NotNullWhen(true)] object? obj) => obj is SegmentedHashSetEqualityComparer<T>;

Conversation

sharwell commented Jul 2, 2021

Uh oh!

sharwell commented Aug 13, 2021

Uh oh!

sharwell commented Aug 23, 2021

Uh oh!

sharwell commented Aug 25, 2021

Uh oh!

sharwell commented Oct 15, 2021

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

RikkiGibson commented Jan 29, 2022

Uh oh!

sharwell commented May 11, 2022

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

jaredpar May 11, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

jaredpar May 11, 2022 •

edited

Loading