Optimize Enumerable.Distinct<T>() for HashSet<T> #112630
-
SummaryThis proposal suggests an optimization for the While this proposed optimization cannot be generally applied to all types that implement Current ImplementationThe existing implementation of public static IEnumerable<TSource> Distinct<TSource>(this IEnumerable<TSource> source, IEqualityComparer<TSource>? comparer)
{
if (source == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.source);
}
return new DistinctIterator<TSource>(source, comparer);
}Proposed ChangeModify Enumerable.Distinct() to recognize when source implements HashSet and doesn't supply a non-default IEqualityComparer, and return the argument directly, avoiding redundant operations when a custom comparer is not provided: public static IEnumerable<T> Distinct<T>(this IEnumerable<T> values, IEqualityComparer<T> comparer = null)
{
if(values == null)
throw new ArgumentNullException(nameof(values));
if(values is ISet<T>)
{
if(values is HashSet<T> hashset &&
hashset.Comparer == (comparer ?? HashSetComparer<T>.Default))
{
return hashset;
}
if(values is ImmutableHashSet<T> hashSet2 &&
hashSet2.KeyComparer == (comparer ?? ImmutableHashSet<T>.Empty.KeyComparer))
{
return hashSet2;
}
/// Anything else?
}
return new DistinctIterator<TSource>(source, comparer);
}
// Avoid redundant allocations:
static class HashSetComparer<T>
{
// HashSet<T> deviates when T is string:
public static readonly IEqualityComparer<T> Default = new HashSet<T>().Comparer;
}Benefits
Potential ConsiderationsIf a custom IEqualityComparer is provided and it is not the same comparer used by the HashSet, the method should still apply the distinct operation instead of returning the HashSet as-is. ConclusionThis small change enhances performance and efficiency in scenarios where Enumerable.Distinct() is called on an existing HashSet without a custom comparer. By preventing redundant work, it aligns with .NET’s performance-oriented principles and provides a better developer experience. We welcome feedback on the feasibility and potential edge cases of this enhancement. |
Beta Was this translation helpful? Give feedback.
Replies: 2 comments 15 replies
-
It can't do that. The ISet itself may be using a non-default notion of equality, which means there could be duplicates according to var set = new HashSet<int>(EqualityComparer<int>.Create((x, y) => false, x => 0))
{
1, 1, 1, 1, 1
};
foreach (int i in set.Distinct())
{
Console.WriteLine(i);
}but with the proposed change, it would print out five |
Beta Was this translation helpful? Give feedback.
-
That can also be viewed as a deficiency of |
Beta Was this translation helpful? Give feedback.
-
|
That's true since public static IEnumerable<T> Distinct<T>(this IEnumerable<T> values, IEqualityComparer<T> comparer = null)
{
if(values == null)
throw new ArgumentNullException(nameof(values));
if(values is HashSet<T> hashset &&
hashset.Comparer == (comparer ?? HashSetComparer<T>.Default))
{
return hashset;
}
return new DistinctIterator<TSource>(source, comparer);
}
static class HashSetComparer<T>
{
public static readonly IEqualityComparer<T> Default = new HashSet<T>().Comparer;
} |
Beta Was this translation helpful? Give feedback.
-
|
I see the overhead of discriminating in the same way that I see various internal tests that are fairly common in Linq, that check to see if an This proposal arose because my own instrumenting of my APIs revealed that there were cases where HashSets were ending up being passed to Distinct(), and with the exception of I don't have the means to determine how widespread the practice of passing hashsets to Distinct is, but I don't see the overhead of a check in any case as being a particularly good defense against not adopting such an optimization. IOW, you don't see the cost of the test adequately justified given the potential benefit of avoiding a redundant iteration on a potentially large collection? |
Beta Was this translation helpful? Give feedback.
-
Such special-casing is added where such inputs are expected to be very common for those particular operators, based on usage data. |
Beta Was this translation helpful? Give feedback.
-
Right, but the gains are not the same. The potential gain achieved by this proposal is far greater than those achieved by most of those special-casing optimizations that currently exist. That lends to an argument supporting it even if the optimal path is rarely taken. Consider this alternative to ToArray() (which I use in cases where I know the result isn't going to be modified, and which most likely violates some basic rule): public static T[] AsArray<T>(this IEnumerable<T> source)
{
return source as T[] ?? source.ToArray();
}The type of gain achieved by this proposal is along the same lines. |
Beta Was this translation helpful? Give feedback.
-
They certainly can be. Many of them avoid significant amounts of work, and even ones that are smaller matter much more because they're much, much, much more common. Demonstrate that this special-casing would be valuable en mass, and we can consider it. In the meantime, you can do it yourself in your own impls for your own use. |
Beta Was this translation helpful? Give feedback.
-
|
Without the means to demonstrate how this optimization would be worth the cost, I'll just implement it in an extension method. |
Beta Was this translation helpful? Give feedback.
-
Do you want something like this? public static IEnumerable<T> Distinct<T>(this I-ReadOnly-Set<T> source)
{
if(source is HashSet<T> hS && hS.Comparer == EqualityComparer<T>.Default)
return hS;
if(source is ImmutableHashSet<T> iHS && iHS.KeyComparer == EqualityComparer<T>.Default)
return iHS;
return source.Distinct();
}benchs
BenchmarkDotNet v0.14.0, Windows 10 (10.0.19045.5487/22H2/2022Update) There are some diffs special distinct vs linq distinct. But as I stated before, there are no differences between special and no distinct. If Distinct will be the first method called in the query, just check if comparer is default and use HashSet as source. If your problem is "Distinct will not be the first method called", then this is another problem, because I think, how Linq have been optimized and Iterator's have been wired inside, you never will get the original HashSet as source if is not in the first call. This will need not only to modify distinct, also to modify Iterator's behavior. Just create your special distinct, use IReadOnlySet (or ISet), put an overload priority attribute if you want to feel safe, and don't create HashSetComparer class. |
Beta Was this translation helpful? Give feedback.
-
The use case is an API that takes Distinct() as it stands can be extremely wasteful if the input is already distinct. The question of what percentage of use cases would benefit from the special-casing optimization is not the criteria that should determine if the optimization should be adopted. The criteria for determining if the optimization should be adopted is what percentage of use cases would be impaired by the overhead (5-10 clock cycles per call to Distinct(), by my estimation). IOW, the percentage of use cases that would benefit from the optimization (regardless of how rare that is), is greater than the percentage of use cases that would be impaired by its overhead. For the overhead of the optimization to have any significance whatsoever, it would require Distinct() to be called at a very high frequency within a hot loop. That is exceptionally-rare, and I would venture to guess that it's even rarer than Distinct() being passed a Hashset, but I have no usage data to quantify that. So, I don't agree with the idea put forth by @stephentoub, that the optimization needs to be beneficial en-mass, and that is quite simply because the the optimization would not be detrimental 'en-mass', and most-likely benefit a greater percentage of use cases than it would impair. Of course I have no usage data to back up that assertion, it is just a reasonable expectation. |
Beta Was this translation helpful? Give feedback.
-
After a recent code review, the group discussed this topic, and the consensus is that the logic underlying the above criteria for adoption is flawed. See this reply below for the rationale. |
Beta Was this translation helpful? Give feedback.
They certainly can be. Many of them avoid significant amounts of work, and even ones that are smaller matter much more because they're much, much, much more common.
Demonstrate that this special-casing would be valuable en mass, and we can consider it. In the meantime, you can do it yourself in your own impls for your own use.