Proposal: Add Array.Sort<T>(T[], int, int, Comparison<T>) overload

[stephentoub]

The PR dotnet/coreclr#8504 changed Array.Sort to be based internally on the Comparison<T> delegate rather than on the IComparer<T> interface, as delegate dispatch is faster than interface dispatch and it enabled consolidating two implementations. That means if an IComparer<T> is provided, its Compare method is wrapped in a Comparison<T> delegate.

However, there is no overload of Array.Sort that takes the array, offset, length, and comparison delegate (the only overload that takes a delegate is Sort(T[], Comparison<T>):
https://github.com/dotnet/corefx/blob/155a46c0c59fddefc009c2a4affd0fd2b3bac2b3/src/System.Runtime/ref/System.Runtime.cs#L305-L309
so if you have a delegate and need to provide offset+length, you first need to allocate an object implementing IComparer<T> to wrap it so you can call the right overload, and then the implementation will wrap that with an allocated Comparison<T>; that's two allocations and multiple levels of indirection when none of that is necessary.

Instead, we should just add this overload:

public static void Sort<T>(T[] array, int index, int length, Comparison<T> comparer);

cc: @mikedn, @jkotas, @joperezr, @AlexGhiondea

[stephentoub]

Instead, we should just add this overload

In addition, we could look to see what the impact would be of changing:
https://github.com/dotnet/coreclr/blob/ebda0e66df0dd19688cf8a88375bb31c184f5037/src/mscorlib/src/System/Collections/Generic/ArraySortHelper.cs#L104

IntrospectiveSort(keys, index, length, comparer.Compare);

to instead be:

IntrospectiveSort(keys, index, length, comparer is ComparisonComparer<T> cc ? cc._comparison : comparer.Compare);

and the same for other such occurrences. Worst case this should cost a type check for no gain, but best case when Comparer<T>.Create was used to create the passed in IComparer<T>, we'd save the allocation and per compare a delegate dispatch and interface dispatch.

[mikedn]

Worst case this should cost a type check for no gain

Fortunately ComparisonComparer is sealed so the type check should fast. Might be a useful change.

[justinvp]

public static void Sort<T>(T[] array, int index, int length, Comparison<T> comparer);

Nit: The parameter should be named comparison.

[mikedn]

Fortunately ComparisonComparer is sealed so the type check should fast

Not quite true. This is generic code so it's fast only when T is a value type. Still, it should be faster than creating a new delegate.

[terrajobst]

Video

Looks good to us, but we should probably add the same API to List<T>

[karelz]

FYI: The API review discussion was recorded - see https://youtu.be/b96co3sNzNI?t=2193 (4 min duration)

[mikedn]

Note that currently Array.Sort(foo, 0, 42, null) is valid, a null results in the default comparer being used. After this addition such code won't compiler anymore.

[stephentoub]

Ugh. That's probably a deal breaker.

[terrajobst]

Video

Seems like it 😢

[karelz]

The API was rejected after all based on the concerns raised above.

FYI: Next round of the API review discussion was also recorded - see https://youtu.be/OZnaGV2omvI?t=360 (4 min duration)