eamonnerbonne/anoprsst

Sorts Span<T> and arrays more quickly than Array.Sort

anoprsst

Sorts Span<T> and T[] more quickly than Array.Sort. It's around 45% faster in serial mode, and upto a core-count-based parallelisation speedup for large arrays, though details matter: it's no faster for strings, just 20% faster for integral builtins, but more than 100% faster for structs with custom orderings.

Usage:

• Add a reference to Anoprsst on nuget
• Implement IOrdering with a struct, which defines a LessThan method to compare to elements.
• Call someSpan.WithOrder(new MyOrdering()).Sort(), which uses an insertion sort for small arrays, quicksort for medium size arrays, and parallel quick sort for large arrays.
• If you're sorting arrays, the same methods are available there too, but it's worth pointing out the someArray.AsSpan(start, length) extension method in System.Memory that makes slicing really easy.
• If the element type is an IComparable struct, you can instead use someSpan.WithIComparableOrder().Sort(), which is often no slower, and thereby avoid implementing IOrdering<T>. This uses efficient special-cased orderings for common types like double or int.
• If you have specific needs concerning the sorting algorithm, numerous alternatives to .Sort() are implemented as extension methods in the Anoprsst.Uncommon namespace, include a merge sort (stable, without implausible O(N²) behavior) and a serial quick sort.
• Bug reports, pull requests, chatter: all welcome, just give a shout in the issues here on github.
• Finally: this is thoroughly tried, but still fairly new, and uses unsafe constructs heavily. Nasty bugs are a possibility; use at your own risk. The benchmark included checks the correctness after each sort; and the full run includes millions or random subsequences of a larger randomly filled test array: these subsequences in effect form a test set.

In terms of performance: Anorpsst's QuickSort outperforms Array.Sort in all cases I tried. The difference is small for large arrays of primitive types such as an int (Array.Sort: 64.1 ns/item vs. QuickSort: 56.8 ns/item, ParallelQuickSort 10.3 ns/item), considerably larger for reference types (203 vs. 140 vs. 34.5 ns/item) and structs (147 vs. 88.1 vs. 16.3 ns/item). Smaller arrays/spans benefit more, such as for arrays of ints of approximately 128 elements: (Array.Sort: 17.861 ns/item vs. QuickSort: 13.373 ns/item, ParallelQuickSort 13.786 ns/item). All measurements done on .net core2.2; Custom IComparable implementations are particularly slow on the full .net framework, making the performance advantages particularly stark on the .net framework.

Feedback; PRs; bug reports; questions or plain cheers & jeers: please post in the issues on github.

anoprsst's Issues

QuickSort_Inclusive_ParallelArgs.Impl fails to pass ordering as child param

By not passing ordering, a default(TOrder) is used and any context in the structure that implements IOrdering<> needed for comparison is lost.

As an example, in the below refDictionary is null at the point that LessThan is called.

internal readonly struct SubDictionaryOrder<K,V> : IOrdering<int>
        where K : struct, IReputationKey, IRefEquatable<K>
        where V : struct, IReputationValuePointer
    {
        private readonly RefDictionary<K, V> refDictionary;
        internal SubDictionaryOrder(in RefDictionary<K, V> items)
        {
            System.Diagnostics.Debug.Assert(items != null);
            this.refDictionary = items;
        }
        bool IOrdering<int>.LessThan(int a, int b)
        {
            return refDictionary.CompareIndexValues(a, b) < 0;
        }
    }

Add BlockQuickSort, and MultiPivot QuickSort.

Add utility overloads to more efficiently sort common special cases

i.e. to sort doubles via a < b || !(a >= b) instead of IComparable, which is considerably faster.

Possible future work

Perhaps a better spot to continue this than DotNetCross/Sorting#3 (@dzmitry-lahoda)

Why are the sort algorithms not faster for strings? and does this mean they are even slower or only as Equaly fast as : Array.Sort(string[]]?

Title.

OrderedAlgorithms.cs won't compile on 2.2

Two precompiler #if statements check for NETCOREAPP2_1 || NET47, both need NETCOREAPP2_2 added.