Proposal: Add Sort(...) extension methods for Span<T>

[nietras]

Currently, there is no way to sort native or fixed memory (e.g. coming from a pointer) in .NET, this proposal intends to fix that by adding sorting extension methods to Span<T>, but also proposes some different overloads than seen on Array to allow for inlined comparisons via the possibility to use value type comparers.

Proposed API

Add a set of Sort extension methods to Span<T> in SpanExtensions:

public static class SpanExtensions
{
     public static void Sort<T>(this Span<T> span);

     public static void Sort<T, TComparer>(this Span<T> span, TComparer comparer) 
        where TComparer : IComparer<T>;

     public static void Sort<T>(this Span<T> span, System.Comparison<T> comparison);
     
     public static void Sort<TKey, TValue>(this Span<TKey> keys, Span<TValue> items);

     public static void Sort<TKey, TValue, TComparer>(this Span<TKey> keys, 
        Span<TValue> items, TComparer comparer) 
        where TComparer : IComparer<TKey>;
        
     public static void Sort<TKey, TValue>(this Span<TKey> keys, 
        Span<TValue> items, System.Comparison<TKey> comparison);
}

Rationale and Usage

Provide a safe yet fast way of sorting of any type of contiguous memory; managed or unmanaged.

Sorting Native Memory

var span = new Span<int>(ptr, length);
span.Sort(); // Sort elements in native memory

Sorting with Inlineable Comparer

struct ReverseComparer : IComparer<int>
{
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public int Compare(int a, int b)
    {
        if (a == b) { return 0; }
        if (a > b) { return -1; }
        return 1;
    }
}

Span<int> span = GetSomeSpan();
// Sort elements, in reverse order with inlined Compare,
// without heap allocation for comparer
span.Sort(new ReverseComparer()); 

Sorting based on Lambda

Span<int> span = GetSomeSpan();
// Sort elements, in reverse order with lambda/delegate
span.Sort((a, b) => a == b ? 0 : (a > b ? -1 : 1)); 

Sorting Compound Type

struct Compound
{
    public float FeatureValue;
    public int FeatureIndex;
    public object Payload;
}

struct InlineableFeatureValueComparer : IComparer<Compound>
{
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public int Compare(Compound a, Compound b)
    {
        if (a.FeatureValue == b.FeatureValue) { return 0; }
        if (a.FeatureValue < b.FeatureValue) { return -1; }
        return 1;
    }
}

var span = new Span<Compound>();

span.Sort();

// Inlineable struct comparer
var comparer = new InlineableFeatureValueComparer();
span.Sort(comparer);

// Lambda comparer
span.Sort((a, b) => a.FeatureValue == b.FeatureValue ? 0 : 
    (a.FeatureValue < b.FeatureValue ? -1 : 1));

The argumentation for adding this is:

• To increase the efficiency of code doing sorting and prevent people from reinventing the wheel.
• Allow performance optimizations depending on memory type and contents.
• Allow sorting on contiguous memory of any kind.

Use Cases

In almost any domain where a high volume of data is processed with sorting being one operation and memory management (e.g. memory recycling, buffer pooling, native memory) is a must to achieve high performance with minimal latency, these sorts would be useful. Example domains are database engines (think indexing), computer vision, artificial intelligence etc.

A concrete example could be in the training of Random Forests some methods employ feature sorting (with indeces) to find decision boundaries on. This involves a lot of data and data that can originate from unmanaged memory.

Open Questions

An important question regarding this proposal is whether the pattern with generic parameter TComparer (e.g. constrained to where TComparer : IComparer<T>) is a pattern that can be approved. This pattern allows for inlineable comparers at the cost of increased code size, if no value type comparers are used, there should be no difference. This pattern is also used in the proposal for BinarySearch in https://github.com/dotnet/corefx/issues/15818

The API relies on being able to depend upon System.Collections.Generic, could this be an issue?

@karelz @jkotas @jamesqo

Updates

UPDATE 1: Change API to be defined as extension methods.
UPDATE 2: Add compounded type usage.
UPDATE 3: Add link to BinarySearch and point on the pattern used.

Existing Sort APIs

A non-exhaustive list of existing sorting APIs is given below for comparison.

Array.Sort Static Methods

Found in ref/System.Runtime.cs

public static void Sort(System.Array array) { }
public static void Sort(System.Array keys, System.Array items) { }
public static void Sort(System.Array keys, System.Array items, System.Collections.IComparer comparer) { }
public static void Sort(System.Array keys, System.Array items, int index, int length) { }
public static void Sort(System.Array keys, System.Array items, int index, int length, System.Collections.IComparer comparer) { }
public static void Sort(System.Array array, System.Collections.IComparer comparer) { }
public static void Sort(System.Array array, int index, int length) { }
public static void Sort(System.Array array, int index, int length, System.Collections.IComparer comparer) { }
public static void Sort<T>(T[] array) { }
public static void Sort<T>(T[] array, System.Collections.Generic.IComparer<T> comparer) { }
public static void Sort<T>(T[] array, System.Comparison<T> comparison) { }
public static void Sort<T>(T[] array, int index, int length) { }
public static void Sort<T>(T[] array, int index, int length, System.Collections.Generic.IComparer<T> comparer) { }
public static void Sort<TKey, TValue>(TKey[] keys, TValue[] items) { }
public static void Sort<TKey, TValue>(TKey[] keys, TValue[] items, System.Collections.Generic.IComparer<TKey> comparer) { }
public static void Sort<TKey, TValue>(TKey[] keys, TValue[] items, int index, int length) { }
public static void Sort<TKey, TValue>(TKey[] keys, TValue[] items, int index, int length, System.Collections.Generic.IComparer<TKey> comparer) { }

List<T>.Sort Member Methods

Found in ref/System.Collections.cs

public partial class List<T> : System.Collections.Generic.ICollection<T>, System.Collections.Generic.IEnumerable<T>, System.Collections.Generic.IList<T>, System.Collections.Generic.IReadOnlyCollection<T>, System.Collections.Generic.IReadOnlyList<T>, System.Collections.ICollection, System.Collections.IEnumerable, System.Collections.IList
{
    public void Sort() { }
    public void Sort(System.Collections.Generic.IComparer<T> comparer) { }
    public void Sort(System.Comparison<T> comparison) { }
    public void Sort(int index, int count, System.Collections.Generic.IComparer<T> comparer) { }
}

LINQ OrderBy Extension Methods

Found in ref/System.Linq.cs

public static System.Linq.IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(this System.Collections.Generic.IEnumerable<TSource> source, System.Func<TSource, TKey> keySelector) { throw null; }
public static System.Linq.IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(this System.Collections.Generic.IEnumerable<TSource> source, System.Func<TSource, TKey> keySelector, System.Collections.Generic.IComparer<TKey> comparer) { throw null; }
public static System.Linq.IOrderedEnumerable<TSource> OrderByDescending<TSource, TKey>(this System.Collections.Generic.IEnumerable<TSource> source, System.Func<TSource, TKey> keySelector) { throw null; }
public static System.Linq.IOrderedEnumerable<TSource> OrderByDescending<TSource, TKey>(this System.Collections.Generic.IEnumerable<TSource> source, System.Func<TSource, TKey> keySelector, System.Collections.Generic.IComparer<TKey> comparer) { throw null; }

[jkotas]

Or perhaps as extension methods.

These should be extension methods. They are in same category as the other similar methods being added: dotnet/corefx#15080
dotnet/corefx#15123

cc @KrzysztofCwalina

[nietras]

These should be extension methods.

Ok, would this not mean any optimizations specific to native/managed memory would not be possible as directly as when they are members? Not sure it has such big a relevance since sorting can be done on refs, but not everything is possible with refs as with pointers. Anyway, if you think this should not be an issue I will update the proposal.

[nietras]

Another concern, is generic type inference which in C# is not always working so well with many generic parameters... not that I can think of a specific case for the proposed API though, but in the face of implicit conversions or similar it is often lacking.

[jamesqo]

@nietras IMHO, I don't know if this is really a needed API. What scenarios are there in which someone would want to sort a Span? It's mostly going to be used to hold byte/char buffers, where sorting won't make much sense. Also, things like equality comparers are high-level and don't really fit in with low-level constructs like Span.

[nietras]

What scenarios are there in which someone would want to sort a Span?

@jamesqo plenty! 😃 Ranging from database engines, computer vision to artificial intelligence. In the latter cases, the types will also range fully from byte to double. And in these fields memory recycling, buffer pooling is paramount to archieving reliable performance. And performance in general important so inlining the compare is important too.

things like equality comparers are high-level

Not sure I get that, but is the issue with the "default" comparers needed for Sort() without parameters? I could live with removing the overloads that do not take a TComparer if that is the concern?

[svick]

public void Sort<TKey, TValue, TComparer>(this Span<TKey> keys, Span<TValue> items, TComparer comparer) where TComparer : IComparer<T>;
public void Sort<TKey, TValue>(this Span<TKey> keys, Span<TValue> items, System.Comparison<T> comparison); // Convenience overload

Nitpick: the Ts in the two lines above should be TKey:

public void Sort<TKey, TValue, TComparer>(this Span<TKey> keys, Span<TValue> items, TComparer comparer) where TComparer : IComparer<TKey>;
public void Sort<TKey, TValue>(this Span<TKey> keys, Span<TValue> items, System.Comparison<TKey> comparison); // Convenience overload

[nietras]

@svick thanks I also forgot static

[jamesqo]

@nietras

Ranging from database engines, computer vision to artificial intelligence. In the latter cases, the types will also range fully from byte to double. And in these fields memory recycling, buffer pooling is paramount to archieving reliable performance. And performance in general important so inlining the compare is important too.

Do you have a concrete example where a sort function would be needed, though? I think the 95% use case for this API would be passing around byte buffers/char buffers. In those scenarios, sorting isn't a function that would be needed, and would only be more API bloat.

Not sure I get that, but is the issue with the "default" comparers needed for Sort() without parameters? I could live with removing the overloads that do not take a TComparer if that is the concern?

The issue, actually, is with the overloads with the comparers. Making them generic on the type of the comparer won't improve perf because everyone passes around comparers as IEqualityComparer<T>. So you will still have virtual calls.

[nietras]

concrete example where a sort function would be needed, though?

@jamesqo I tried giving a more concrete in the proposal regarding machine learning.

95% use case for this API would be passing around byte buffers/char buffers

If .NET Core and Span<T> only target audience is web developers, where shuffling bytes to/from text/chars, then perhaps you are right. But IMHO it is a very limited target audience and misses the fact that in a cloud/mobile first world that is going to be infused with artificial intelligence everywhere, handling massive amounts of data/measurements is a must. This includes all data types, byte to double. Pure sales talk, uff 🙄

because everyone passes around comparers as IEqualityComparer

I don't and never have. 😉 Passing comparers around is not something we do and it does not have any impact on the design of this API. It still works as a "non-generic" API and if it is only used with reference type comparers there will be no code bloat or anything. So I do not see the downside here, the overloads are there for convenience and flexibility just as with the existing APIs incl. Array.Sort.

The implementation can forward to the same single implementation, for example. However, by having the possibility for using a value type comparer we allow developers that need the perf and understand that this will cause code to be generated specifically for that case to do what they need. No virtual calls. In the domain of numerical processing that is what we need.

[KrzysztofCwalina]

We could do Sort(TComparer comparer) where TComparer : IComparer. This would be devirtualized.

[jamesqo]

@KrzysztofCwalina It will not unless you pass in a custom struct comparer. For example, Sort(Comparer<T>.Default) will have TComparer == Comparer<T> and you will be making virtual calls to Comparer<T>.Compare.

[jamesqo]

There is another thing-- I don't think the overloads accepting TComparer will even compile. See here. I ran into this issue a few months ago when I was trying to use generics in a similar fashion.