Specialize Order Distinct Iterator in LINQ

[henriquewr]

The current implementation of Distinct uses a HashSet to verify if the item exists, on collections that we know that is "pure ordered" this approach is a little bit memory inefficient

"Pure ordering" means that always equal elements will be side by side, like [1,1,2,2,3,3,3,3,4], and instead of the "costly" HashSet implementation, we can simply verify if the last element returned is different than the current

Like that:

public static IEnumerable<T> PureOrderedDistinct<T>(IOrderedEnumerable<T> pureOrdered)
{
    using var enumerator = pureOrdered.GetEnumerator();

    if (!enumerator.MoveNext())
    {
        yield break;
    }

    var lastReturnedItem = enumerator.Current;
    yield return lastReturnedItem;

    while (enumerator.MoveNext())
    {
        var currentItem = enumerator.Current;
        if (!EqualityComparer<T>.Default.Equals(lastReturnedItem, currentItem))
        {
            lastReturnedItem = currentItem;
            yield return lastReturnedItem;
        }
    }
}

[dotnet-policy-service]

Tagging subscribers to this area: @dotnet/area-system-linq
See info in area-owners.md if you want to be subscribed.

[Clockwork-Muse]

There's no guarantee of any relationship between ordering and object equality/identity based on the presence of IOrderedEnumerable.
Consider:

using System;
using System.Linq;
					
public class Program
{
	public static void Main()
	{
		IOrderedEnumerable<int> o = new[] { 1, 2, 3, 2, 1 }.OrderBy(i => i % 2);
		// prints 2, 2, 1, 3, 1
		Console.WriteLine(string.Join(", ", o));
	}
}

[henriquewr]

There's no guarantee of any relationship between ordering and object equality/identity based on the presence of IOrderedEnumerable. Consider:

using System;
using System.Linq;

public class Program
{
public static void Main()
{
IOrderedEnumerable o = new[] { 1, 2, 3, 2, 1 }.OrderBy(i => i % 2);
// prints 2, 2, 1, 3, 1
Console.WriteLine(string.Join(", ", o));
}
}

That was my initial idea, but I realized that for this optimization work, it can not touch anything in the "outside world", so it can only be applied on Order/OrderDescending

[Clockwork-Muse]

Consider:

using System;
using System.Collections.Generic;
using System.Linq;
					
public class Program
{
	public static void Main()
	{
		IOrderedEnumerable<int> o = new[] { 1, 2, 3, 2, 1 }.Order(Comparer<int>.Create((a, b) => (a % 2) - (b % 2)));
		// prints 2, 2, 1, 3, 1
		Console.WriteLine(string.Join(", ", o));
	}
}

You could maybe special-case where the comparer is the default one for a primitive, but I'm not sure how common that is, compared to any custom comparison/ordering (especially for complex types).

[henriquewr]

For this optimization to work, it needs to meet this requirements
#120131 (comment)

So it can only be applied in some specific types that we know that wont ever not meet the requirements, with the default comparer and default equality comparer

But at least, they are the most common types to order

[eiriktsarpalis]

While this optimization provides genuine performance improvements, per the discussion in #120131 (review) the covered scenario seems somewhat unlikely to warrant the added static footprint that it incurs.