Sort<T, TComparer> extensions performance

[jkotas]

Sort overloads that take TComparer as a generic argument were approved in #19969 . However, the implementation did not take advantage of the generic TComparer and the TComparer overload is actually the less efficient option.

This issue tracks fixing the implementation of Sort<T, TComparer> to take full advantage of the generic TComparer.

Full context: #37941 (comment)

Tagging subscribers to this area: @eiriktsarpalis
Notify danmosemsft if you want to be subscribed.

[jkotas]

cc @nietras

[nietras]

@jkotas thanks. Moving conversation from #37941 (comment) here :)

For time line, I do not expect we would be able to get this change into .NET 5.

I was really hoping we could get this in. The changes shouldn't be that big. As far as I understood, from a standup video I think, "feature freeze"/branch for .NET 5 RC might happen around 8th of August. That's doable in my view. Could you perhaps expand on why you think it won't be possible? What's the deadline? :)

"unsafe" cast of Comparison<T> to Comparison<object>
Why would that be needed?

The idea here is to replace the Comparison<T> C# code path with a TComparer path e.g.

    internal partial class ComparerArraySortHelper<T, TComparer>
        where TComparer : IComparer<T>
    {
        public void Sort(Span<T> keys, TComparer comparer)
        {

we then need to support Comparison<T> via e.g.

    internal readonly struct ComparisonComparer<T> : IComparer<T>
    {
        private readonly Comparison<T> _comparison;

        public ComparisonComparer(Comparison<T> comparison) =>
            _comparison = comparison;

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public int Compare([AllowNull] T x, [AllowNull] T y) =>
            _comparison(x, y);
    }

Compare can now be inlined for value types via #10048. 👍

However, this won't work for reference types. At least not to my knowledge. Inlining and generics and all. The idea then would be to support reference types via internal trickery (if needed!) and use below for all reference types:

    internal readonly struct ObjectComparisonComparer : IComparer<object>
    {
        private readonly Comparison<object> _comparison;

        public ObjectComparisonComparer(Comparison<object> comparison) =>
            _comparison = comparison;

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public int Compare([AllowNull] object x, [AllowNull] object y) =>
            _comparison(x, y);
    }

If the runtime can be changed to not having to have this, that would be great and would solve a long standing issue for me.

whether it would make sense to delete the TComparer overloads from the public surface for now until we can get the right implementation for them in place.

Very much hope we can get the implementation in and not change the public surface. The actual changes to the sorting code as such are minimal. :)

[jkotas]

I was really hoping we could get this in. The changes shouldn't be that big

I agree for functional correctness. I suspect that this work will uncover codegen issues that we won't have time to fix in next 3 weeks.

[nietras]

will uncover codegen issues that we won't have time to fix in next 3 weeks.

That is of course a possibility/concern, given my experience with codegen here incl. net5 previews I am pretty optimistic, though. :) We should try at least. But I need guidance on how to refactor the whole ArraySortHelper stuff and whether the Comparison trick is viable/acceptable. My guess would be that if you, @jkotas, did this you could do the code changes in a couple of hours. 😉

[jkotas]

Comparison trick is viable/acceptable

If it was the only workaround for the codegen issues in the change, I think it would be acceptable. I suspect that the problem that it is trying to workaround is going to be present in more situations that are not possible to workaround.